プログラミングのお題スレ Part10

**デフォルトの名無しさん** · 2018/01/01(月) 11:15:04.40

プログラミングのお題スレです。

前スレ
プログラミングのお題スレ Part9
https://mevius.5ch.net/test/read.cgi/tech/1480579110/

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
http://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
http://runnable.com/
http://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

**デフォルトの名無しさん** · 2018/04/12(木) 03:43:27.29

>>691-695
立方体の展開図は、384 通り。
同型のものを1つとして数えると、11 通りになる

この本に書いてある

超高速グラフ列挙アルゴリズム－〈フカシギの数え方〉が拓く，
組合せ問題への新アプローチ
ERATO 湊離散構造処理系プロジェクト・湊真一、2015

計算時間が何百億年も掛かるのが、数秒で解けた
「おねえさんの問題」で有名な、
湊真一の超高速グラフ列挙アルゴリズム ZDD

**デフォルトの名無しさん** · 2018/04/12(木) 05:28:52.38

おねえさんの問題作った人？ｗ
すげえバズったよなアレｗｗｗｗ

**720** · 2018/04/12(木) 07:11:40.78

>>720
https://ideone.com/4YO0hK
回転処理を修正
べた塗り(全白,全黒)を除外
8通り

**デフォルトの名無しさん** · 2018/04/12(木) 07:53:54.58

お題
正20面体の3色の塗り分けの全種類を展開図で示せ

**611** · 2018/04/12(木) 08:56:31.07

>>611
>2種類の数字だけでできている、N桁の数字は、いくつあるか？

これを馬鹿正直にnested loop すると、N=4, 5 では、4・5階層と、
Nの数によって、階層が異なってくるから難しい

Nが幾つでも、ループの階層が同じになるように、作らなければならない

**611** · 2018/04/12(木) 10:59:42.57

>>611
Ruby で作った

DIGITS = [4, 5] # number of digits 桁数
# 答え、567, 1,215

DIGITS.each do |digit|
count = 0
wrapper = Array.new digit - 1
# [*0..9] で、配列にする
[*0..9].combination(2) do |ary|
(digit - 1).times { |i| wrapper[i] = ary }

# 先頭が0 のものと、1つの数字だけを使ったものを排除する
# *wrapper で、外側の[ ] をはずす
count += ary.product(*wrapper)
.reject { |item| item[0] == 0 }
.reject { |item| item.uniq.length == 1 }.length
end
puts count
end

**デフォルトの名無しさん** · 2018/04/12(木) 12:56:22.91

>>611の通りに単純な数値計算をすればいいだけ

**デフォルトの名無しさん** · 2018/04/12(木) 13:52:20.61

数学で解くのと、プログラミングで解くのは、異なる。
理論と実践。机上と現実

両方で解いて、確かめたものだけが、現実でも正しい

**デフォルトの名無しさん** · 2018/04/12(木) 14:01:35.93

うん？つまりコンピュータが存在しない時代の数学者はすべて間違えていると？

**デフォルトの名無しさん** · 2018/04/12(木) 14:03:11.18

簡単すぎる性質を使わないのはバカだと思う
N=10000の場合は？

**デフォルトの名無しさん** · 2018/04/12(木) 21:33:52.89

>>710は要するにN=197が無い
ttps://ideone.com/wVBe61
このリストで初めての欠品がN=197だ

N=197は計算しきれないような余りにもバカでかい円になるのか、そもそも数学的に存在しないのか、円が存在できないのか、分からない
N=197の円が存在できないとすれば、無いものを延々と探し続けることになる

ついでに、例えばN=320ともなると、この円が数学的に本当に存在してるのか、
それとも計算の誤差でOKが出てるのか、分からない

**デフォルトの名無しさん** · 2018/04/12(木) 21:44:36.64

数学的にはどんなNの円でも存在する
http://mathworld.wolfram.com/SchinzelCircle.html
ただしこの計算で出てくる円は（一部のNを除き）最小ではない

円周上の格子点は整数で計算出来るから誤差はないし検算も難しいものではない

**デフォルトの名無しさん** · 2018/04/12(木) 21:47:30.14

へぇ……
もはや数式まであるのかよ

**デフォルトの名無しさん** · 2018/04/12(木) 21:55:34.08

ということで>>712が何を言ってるのかがわからんわけですよ

**デフォルトの名無しさん** · 2018/04/12(木) 22:04:42.99

円が存在することと最小値が存在することは全く別だがな
十分に大きいnに対してはその辺微妙だと思うんだけどどう？

**デフォルトの名無しさん** · 2018/04/12(木) 22:10:25.49

最小は存在はするだろ。
計算や探索で出た数値が本当に最小かどうかは（俺には）わからんが。

**デフォルトの名無しさん** · 2018/04/12(木) 22:18:36.57

>>735
>>715

**デフォルトの名無しさん** · 2018/04/12(木) 22:35:20.29

N個の格子点を通る円は、
x, y方向に1移動してもN個の格子点を通る為
原点を通る円に限定しても一般性を失わない

N≧3とする
原点を通りちょうどN個の格子点を通る半径r未満の円は、原点からr未満の距離にある格子点しか通らない
原点からr未満の距離にある格子点は有限個であり、この中からN個の格子点を選ぶ選び方も当然有限個
特定のN個の格子点を通る円は1個しか存在しない為、原点を通りちょうどN個の格子点を通る半径r未満の円も有限個である

よって、ちょうどN個の格子点を通る(半径rの)円が存在すれば、最小値は存在する

**デフォルトの名無しさん** · 2018/04/12(木) 22:39:01.75

おお、わかりやすいな、サンクス

**デフォルトの名無しさん** · 2018/04/12(木) 22:55:32.88

この円の問題は何度も取り上げられるが
毎回うだうだと話が続くだけで何の進展もないみ
アプローチを変えてNを限定するとか
半径を整数にするとかしてみたら

**デフォルトの名無しさん** · 2018/04/12(木) 23:53:08.79

円問題、昔書いたコード探してみたがよくわからないことやってるから困る…

**デフォルトの名無しさん** · 2018/04/13(金) 00:58:19.54

>>738
なにをグダグタ説明してるんだ？

> よって、ちょうどN個の格子点を通る(半径rの)円が存在すれば、最小値は存在する
なんてどうみても自明だろ

**デフォルトの名無しさん** · 2018/04/13(金) 01:06:37.13

>>742
君はこの問題の格子点が「xもyも有理数の点」に問題が変わったとしても
「最小値が存在するのは自明」とか言っちゃう白痴君かな？

**デフォルトの名無しさん** · 2018/04/13(金) 01:34:00.60

>>743
バカなの？
> よって、ちょうどN個の格子点を通る(半径rの)円が存在すれば
(ちょうどN個の格子点を通る)より小さな円がなければ半径rの円が最小
より小さな円が存在するなら同様に更に小さな円が存在するかを調べればいいだけ
有理数とか関係ないだろ w

**デフォルトの名無しさん** · 2018/04/13(金) 01:35:49.41

なん有理数の点が出てくるんだよｗ　全く関係ないだろ

**デフォルトの名無しさん** · 2018/04/13(金) 01:38:36.55

ああ、本当に頭が悪いんだな
今からでも遅くないから解析学の教本くらい読んでおけ

**デフォルトの名無しさん** · 2018/04/13(金) 02:01:41.10

なんで格子点の問題を有理点の問題にしようとするん？

**デフォルトの名無しさん** · 2018/04/13(金) 04:56:48.60

>>746
あっ、逃げた w

**デフォルトの名無しさん** · 2018/04/13(金) 06:14:56.89

【問】ある数字 n までの数列ローマ数字（I、II、III、…）にしたとき、
　　　最大の長さを持つ文字列を探す関数を書け。

例：
n = 5 のとき、{I、II、III、IV、V}、したがって最大は3。
f(5) = 3

**デフォルトの名無しさん** · 2018/04/13(金) 06:32:40.44

>>742
証明とは何か
学校で習わなかった？

**デフォルトの名無しさん** · 2018/04/13(金) 06:34:53.76

「最小値が存在するかわからん」
て言ってるやつへの説明として
「自明である」

馬鹿ですね

**デフォルトの名無しさん** · 2018/04/13(金) 06:39:20.49

>>750
なにを言いたいんだ？
証明なら>>744で充分だろ

**デフォルトの名無しさん** · 2018/04/13(金) 06:42:13.54

>>751
> 馬鹿ですね
お前がな w

**デフォルトの名無しさん** · 2018/04/13(金) 07:46:29.65

コミュ障ですか？
十分かどうかなんて説明する相手次第なんだよ
ポイントの>>715だけでわからないんだから詳細の>>738が必要だろう

>>744？
証明の方針として全くセンスを感じません
回答としては0点ですね
まあじゃあ試しにその方針で証明してみてください

**デフォルトの名無しさん** · 2018/04/13(金) 07:51:07.00

類似問題としては
円を楕円、五角形などに変える例なんかが考えられますね

数学的センスがない>>744にわかるかな？

**デフォルトの名無しさん** · 2018/04/13(金) 08:03:23.71

センスとか言い出しちゃったよ w
まあ数学的な反論ができないことはわかった

**デフォルトの名無しさん** · 2018/04/13(金) 08:28:27.40

全く数学になってない>>744に反論するのは難しくないか？

**デフォルトの名無しさん** · 2018/04/13(金) 08:30:51.82

説明にも証明にもなってないし
証明の方針としても全く使えない

**デフォルトの名無しさん** · 2018/04/13(金) 08:32:16.43

っていうこと自体理解してない

試しにその方針で証明してみてください

**デフォルトの名無しさん** · 2018/04/13(金) 08:40:12.04

はい、逃げた w

**デフォルトの名無しさん** · 2018/04/13(金) 09:03:55.52

ポイントがわからない ===> 数学的知識の欠如
方針がトンチンカン ===> 数学的センスの欠如
わからない人に「自明」 ===> コミュ障

三重苦

数学的反論の対象が無いものを数学的に反論するのは無理ゲー

**デフォルトの名無しさん** · 2018/04/13(金) 11:30:23.16

結局数学的反論はできないってことな w
>>744のどこがおかしいか具体的に書いてから言えよ

**デフォルトの名無しさん** · 2018/04/13(金) 11:43:09.54

解答候補となる円が有限個に絞れることを説明できていない

**デフォルトの名無しさん** · 2018/04/13(金) 11:58:51.45

どこに無限の候補があるのん？

**デフォルトの名無しさん** · 2018/04/13(金) 12:28:44.65

数学によるマウンティングをするスレができたと聞いて高みの見物に来ました

**デフォルトの名無しさん** · 2018/04/13(金) 12:33:48.19

>>763
なんで絞る必要があるんだ？
円が無限にあったとしても半径の最小値が存在するかどうかとは関係ない

**デフォルトの名無しさん** · 2018/04/13(金) 12:37:25.51

Nが2以上で半径の最小値が存在しない状態ってのがまずわからん。
N=0や1の場合で半径0を円として認めない場合、最小値が存在しないってのはわかるけど。

**デフォルトの名無しさん** · 2018/04/13(金) 12:53:47.67

最小値が存在しないなんて主張をしてるのは>>712だけ
最小値が存在するという主張の根拠を聞かれてるのだから、素直に存在する証明をすれば良い

>>744は何の証明にも説明にもなってない
「他に小さいのがなければそれが最小値、小さいのが存在するならさらに小さいのを探す」
こんなものは今回の命題とは関係なく、全順序であれば最小値が存在しようがしまいが言えること

**デフォルトの名無しさん** · 2018/04/13(金) 12:55:03.04

最小値が存在するというポイントを1個も押さえていないので
「ああ、数学が出来ない人だ」という感想が出るだけ

**デフォルトの名無しさん** · 2018/04/13(金) 12:56:57.55

>>768
> 全順序であれば最小値が存在しようがしまいが言えること
だからそれで十分だろ

**デフォルトの名無しさん** · 2018/04/13(金) 12:58:12.86

>>769
> 最小値が存在するというポイントを1個も押さえていないので
どこからそんな頓珍漢なことを思い付いたんだ？ w

**デフォルトの名無しさん** · 2018/04/13(金) 12:59:15.87

>>770
正の実数に最小値が存在する証明
「他に小さいのがなければそれが最小値、小さいのが存在するならさらに小さいのを探す」

結果に関わらず何にでも言えますねえ

**デフォルトの名無しさん** · 2018/04/13(金) 13:08:03.29

これ実数じゃなくて整数の問題だろ

**デフォルトの名無しさん** · 2018/04/13(金) 13:14:40.36

>>766
それもそうだね、悪かった

ところで>>744のアルゴリズムが有限回で停止することは保証されてるのかな
あ、あくまで保証されてるかどうか知りたいだけなんでね

**デフォルトの名無しさん** · 2018/04/13(金) 15:59:59.85

N=1, N=2であれば有限回では止まらない
N≧3であれば有限回で止まるのは>>738の通り

**デフォルトの名無しさん** · 2018/04/13(金) 16:02:24.96

誰か>>749のお題を解いて、このどうでもいい流れを止めて。

**デフォルトの名無しさん** · 2018/04/13(金) 16:04:43.81

>>776
宿題？

**デフォルトの名無しさん** · 2018/04/13(金) 16:25:54.51

>>749 Squeak/Pharo Smalltalk

| f |
f := [:n | (1 to: n) detectMax: [:m | m printStringRoman size]].
f value: 5 "=> 3 "

**デフォルトの名無しさん** · 2018/04/13(金) 17:07:07.08

お題　五目並べ
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14188952404

Ｃ言語以外でも可能というか歓迎。
特にrubyなどで、ワンライナー的に（Javaでいうところのストリームを駆使）書くとエロいものとする

**デフォルトの名無しさん** · 2018/04/13(金) 17:23:29.89

>>779
サンプルコード出して

**デフォルトの名無しさん** · 2018/04/13(金) 19:37:34.13

>>774
無限に繰り返せるとしたら極限値は0になる
（単調減少だから）
しかし 1 < n で半径0はあり得ない
なので必ず有限回で停止する

**デフォルトの名無しさん** · 2018/04/13(金) 19:40:28.93

>>772
>>770

>>773
半径は整数とは限らない

**デフォルトの名無しさん** · 2018/04/13(金) 19:51:14.28

>>782
半径の二乗は有理数
整数倍して扱えばすべて整数として計算できる…んじゃないのん？

**デフォルトの名無しさん** · 2018/04/13(金) 20:00:29.13

>>749
https://ideone.com/9avEMe
解が複数ある場合に全部出す

**デフォルトの名無しさん** · 2018/04/13(金) 20:03:00.55

>>783
できるかも知れん...
で、それがなにか？

**デフォルトの名無しさん** · 2018/04/13(金) 21:09:21.72

おそらく最小値は存在するんだろうけど
「1/2 + 1/3 + 1/4 + …」が収束すると思ってるようなレベルのアホがそれを主張することによって
最低限の数学的素養のあるやつらから総ツッコミされてるかんじだな

**デフォルトの名無しさん** · 2018/04/13(金) 21:11:44.26

これまた頓珍漢なことを言い出したぞww

**デフォルトの名無しさん** · 2018/04/13(金) 21:15:38.41

数学で論争になるって珍しくないか？
数学って証明されたらそこで議論の余地がなくなるよな。

**デフォルトの名無しさん** · 2018/04/13(金) 21:24:20.06

>>788
すでに証明されてるのに有理数ガーとか無限の円とか必死になってる奴がいるだけ
議論じゃなくマウントとりたいだけなんだろうな

**デフォルトの名無しさん** · 2018/04/13(金) 21:28:26.35

>>749 Squeak Smalltalk で複数ある場合ぜんぶ返す版

| f |
f := [:n |
| max ans |
max := 0.
ans :=#().
(1 to: n) do: [:m |
| roman |
roman := m printStringRoman.
roman size = max ifTrue: [ans := ans, {m}].
roman size > max ifTrue: [max := roman size. ans := {m}].
].
ans size = 1 ifTrue: [ans first] ifFalse: [ans asArray]
].
f value: 5. "=> 3 "
f value: 1887. "=> #(888 1388 1788 1838 1878 1883 1887) "

**デフォルトの名無しさん** · 2018/04/13(金) 21:42:23.87

>>789
>>744が証明になってない
っていう話だぞ

存在する証明は>>738参照
これが証明

>>781
単調減少の実数列の極限が1になることも100になることもあるわけだが
当然有限回で終わらないこともある
例えばN=2の時は無限回続くことがある
N≧3の場合は>>738により有限回であることがわかるというだけ

数学の基礎がわからない人が数学の専門家に数学に関する意見を言うとはなかなか

**デフォルトの名無しさん** · 2018/04/13(金) 21:45:58.60

>>791
> 単調減少の実数列の極限が1になることも100になることもあるわけだが
で、それが最小値がないこととなんの関係があるんだ？

**デフォルトの名無しさん** · 2018/04/13(金) 21:48:26.76

マジで阿呆だな
下に有界かつ協議単調減少だからと言って最小値が存在するとは限らないのだよおバカさん

**デフォルトの名無しさん** · 2018/04/13(金) 21:49:16.12

>>793
具体例よろしく

**デフォルトの名無しさん** · 2018/04/13(金) 21:50:16.77

>>792
関係ないことを理由に最小値が存在すると主張している人がいるので

**デフォルトの名無しさん** · 2018/04/13(金) 21:51:12.93

a_n = 1 / n

**デフォルトの名無しさん** · 2018/04/13(金) 21:51:53.12

は？
f:{x:x∈R∧x>0}→R, f(x) = 1/x を考えれば自明だろ本気の阿呆かよ

**デフォルトの名無しさん** · 2018/04/13(金) 21:53:20.26

協議単調減少？

**デフォルトの名無しさん** · 2018/04/13(金) 21:54:30.00

狭義単調減少ね。誤変換は許して

**デフォルトの名無しさん** · 2018/04/13(金) 21:57:30.91

>>797
ん？
なんで列の話をしてるのにxが実数？

**デフォルトの名無しさん** · 2018/04/13(金) 21:58:43.94

あぼーんの連続w

**デフォルトの名無しさん** · 2018/04/13(金) 22:01:36.65

>>800
族集合の濃度が高々?な集合に関して証明すれば十分なんだから実数関数について言及したところで何も問題ないよね？
むしろ十分正の説明としては申し分ないと思うのだが

**デフォルトの名無しさん** · 2018/04/13(金) 22:03:22.81

>>802
落ち着け

**デフォルトの名無しさん** · 2018/04/13(金) 22:07:41.91

十分正

族集合とか濃度とかどうでもいい
列の話をしてるんだから素直に列の例を出せばいい
一般化する必要もない
アホに対して一般化しても無意味

**デフォルトの名無しさん** · 2018/04/13(金) 22:09:53.15

ごめんね、十分性ね
「アホに対して一般化しても無意味」ってのは同意だからこちらがスノビズムな嫌いがあったなら謝るよ

**デフォルトの名無しさん** · 2018/04/13(金) 22:11:33.83

「スノビズム」とか言っちゃうところがスノビズム

**デフォルトの名無しさん** · 2018/04/13(金) 22:34:53.35

可算集合と非可算集合では濃度が違うから証明にならないという主張かも知れん
というかここ数学スレだっけ？

◆QZaw55cn4c · 2018/04/13(金) 22:57:38.87

みな数学好きなんですね、うらやましい…

**デフォルトの名無しさん** · 2018/04/14(土) 08:27:58.74

>>779
https://ideone.com/f4aEQv
普通に実装してみた

**デフォルトの名無しさん** · 2018/04/14(土) 09:02:56.59

>>749
@Mathematica

https://ideone.com/uEPG3P

**デフォルトの名無しさん** · 2018/04/14(土) 21:11:32.49

>>451 J
(#:i.2^10)#"1'9876543210'

**デフォルトの名無しさん** · 2018/04/14(土) 21:30:22.59

>>811
何これ興味ある

**デフォルトの名無しさん** · 2018/04/14(土) 21:34:41.56

デザインパターンをインターフェースから説明した良心的なブログ

https://blogs.yahoo.co.jp/kamyu_2010/35417803.html

**デフォルトの名無しさん** · 2018/04/15(日) 16:50:03.82

長方形を田の字型に4つの長方形に分割したら
左上の面積が253
左下の面積が115
右下の面積が155になった
右上の面積はいくつか?

**デフォルトの名無しさん** · 2018/04/15(日) 16:58:12.07

253=23*11
115=23*5
155=31*5

**デフォルトの名無しさん** · 2018/04/15(日) 17:00:37.86

お題　半素数を小さいものから200個挙げて

**デフォルトの名無しさん** · 2018/04/15(日) 17:04:46.37

素数を200個求める
積を列挙
ソート

**デフォルトの名無しさん** · 2018/04/15(日) 17:19:22.18

素数を求めなくてもできるよ

**デフォルトの名無しさん** · 2018/04/15(日) 18:07:04.68

数学板でやれ

**デフォルトの名無しさん** · 2018/04/15(日) 18:11:02.11

>>814
数学板でやれ