X
プログラミングのお題スレ Part10
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
垢版 |
2018/01/01(月) 11:15:04.40ID:2Vr1CPKy
プログラミングのお題スレです。

前スレ
プログラミングのお題スレ 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/

宿題は宿題スレがあるのでそちらへ。
0708デフォルトの名無しさん
垢版 |
2018/04/11(水) 21:08:58.17ID:0UD5Vzkt
コンピューターじゃないと出来ない課題の方が良いと思うんだ
特に数学っぽいのは
0709デフォルトの名無しさん
垢版 |
2018/04/11(水) 21:12:18.35ID:0UD5Vzkt
数学的知識をどこまで使って良いか迷うし
ガシガシに最適化をしたら結果をテーブルで持つ
みたいになったらつまらんし
0710デフォルトの名無しさん
垢版 |
2018/04/11(水) 21:45:46.47ID:oecHnyiq
>>708
こんなんとか？

プログラミングのお題スレ Part7
https://peace.5ch.net/test/read.cgi/tech/1429195275/41
> 41 ：デフォルトの名無しさん：2015/05/01(金) 14:31:24.98 ID:9G1+bMO9
> お題：ちょうどn個(1 < n)の格子点(x座標もy座標も整数の点)を通る円の半径の
> 最小値を求める。円の中心点は格子点でなくてよい。
> 例
> n=2 -> 0.5
> n=5 -> 16.170331
> n=6 -> 2.5
※ n=5 は 5.89256 が正しい


サンプルデータ（最小ではない可能性あり）
https://ideone.com/wVBe61
0711デフォルトの名無しさん
垢版 |
2018/04/11(水) 21:52:59.57ID:5X4H9iqq
>>710
考えてみる

最小ではない可能性ありが貼られてるってことは
まだ出来た人がいないってことかな？
0712デフォルトの名無しさん
垢版 |
2018/04/11(水) 22:14:47.69ID:hSvs5cp7
まずnの値によっては最小値が存在しないから問題が破綻してる
結局数値計算するだけの問題だし
0715デフォルトの名無しさん
垢版 |
2018/04/11(水) 22:27:48.82ID:5X4H9iqq
n=1の時に最小値が存在しないことはすぐわかるが
1<nだから関係ない

n=2の時は簡単にわかる

特定の3個以上の格子点を通る円は高々1個しか存在せず
また、ある点から特定の距離以内の格子点の数は有限なので
存在するなら最小値は存在しそう
0721デフォルトの名無しさん
垢版 |
2018/04/12(木) 03:43:27.29ID:T93bDVFD
>>691-695
立方体の展開図は、384 通り。
同型のものを1つとして数えると、11 通りになる

この本に書いてある

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

計算時間が何百億年も掛かるのが、数秒で解けた
「おねえさんの問題」で有名な、
湊真一の超高速グラフ列挙アルゴリズム ZDD
0725611
垢版 |
2018/04/12(木) 08:56:31.07ID:T93bDVFD
>>611
>2種類の数字だけでできている、N桁の数字は、いくつあるか？

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

Nが幾つでも、ループの階層が同じになるように、作らなければならない
0726611
垢版 |
2018/04/12(木) 10:59:42.57ID:T93bDVFD
>>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
0728デフォルトの名無しさん
垢版 |
2018/04/12(木) 13:52:20.61ID:T93bDVFD
数学で解くのと、プログラミングで解くのは、異なる。
理論と実践。机上と現実

両方で解いて、確かめたものだけが、現実でも正しい
0729デフォルトの名無しさん
垢版 |
2018/04/12(木) 14:01:35.93ID:1gf/4w6V
うん？つまりコンピュータが存在しない時代の数学者はすべて間違えていると？
0731デフォルトの名無しさん
垢版 |
2018/04/12(木) 21:33:52.89ID:mVSzUkBa
>>710は要するにN=197が無い
ttps://ideone.com/wVBe61
このリストで初めての欠品がN=197だ

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

ついでに、例えばN=320ともなると、この円が数学的に本当に存在してるのか、
それとも計算の誤差でOKが出てるのか、分からない
0735デフォルトの名無しさん
垢版 |
2018/04/12(木) 22:04:42.99ID:vJMR7aa5
円が存在することと最小値が存在することは全く別だがな
十分に大きいnに対してはその辺微妙だと思うんだけどどう？
0736デフォルトの名無しさん
垢版 |
2018/04/12(木) 22:10:25.49ID:1gf/4w6V
最小は存在はするだろ。
計算や探索で出た数値が本当に最小かどうかは（俺には）わからんが。
0738デフォルトの名無しさん
垢版 |
2018/04/12(木) 22:35:20.29ID:iYyApZ27
N個の格子点を通る円は、
x, y方向に1移動してもN個の格子点を通る為
原点を通る円に限定しても一般性を失わない

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

よって、ちょうどN個の格子点を通る(半径rの)円が存在すれば、最小値は存在する
0740デフォルトの名無しさん
垢版 |
2018/04/12(木) 22:55:32.88ID:7+VvzBGk
この円の問題は何度も取り上げられるが
毎回うだうだと話が続くだけで何の進展もないみ
アプローチを変えてNを限定するとか
半径を整数にするとかしてみたら
0741デフォルトの名無しさん
垢版 |
2018/04/12(木) 23:53:08.79ID:1gf/4w6V
円問題、昔書いたコード探してみたがよくわからないことやってるから困る…
0742デフォルトの名無しさん
垢版 |
2018/04/13(金) 00:58:19.54ID:17c0MCsX
>>738
なにをグダグタ説明してるんだ？

> よって、ちょうどN個の格子点を通る(半径rの)円が存在すれば、最小値は存在する
なんてどうみても自明だろ
0743デフォルトの名無しさん
垢版 |
2018/04/13(金) 01:06:37.13ID:nIDp//XA
>>742
君はこの問題の格子点が「xもyも有理数の点」に問題が変わったとしても
「最小値が存在するのは自明」とか言っちゃう白痴君かな？
0744デフォルトの名無しさん
垢版 |
2018/04/13(金) 01:34:00.60ID:17c0MCsX
>>743
バカなの？
> よって、ちょうどN個の格子点を通る(半径rの)円が存在すれば
(ちょうどN個の格子点を通る)より小さな円がなければ半径rの円が最小
より小さな円が存在するなら同様に更に小さな円が存在するかを調べればいいだけ
有理数とか関係ないだろ w
0746デフォルトの名無しさん
垢版 |
2018/04/13(金) 01:38:36.55ID:nIDp//XA
ああ、本当に頭が悪いんだな
今からでも遅くないから解析学の教本くらい読んでおけ
0749デフォルトの名無しさん
垢版 |
2018/04/13(金) 06:14:56.89ID:aQMXC5LV
【問】ある数字 n までの数列ローマ数字（I、II、III、…）にしたとき、
　　　最大の長さを持つ文字列を探す関数を書け。

例：
n = 5 のとき、{I、II、III、IV、V}、したがって最大は3。
f(5) = 3
0751デフォルトの名無しさん
垢版 |
2018/04/13(金) 06:34:53.76ID:EOEX1zZI
「最小値が存在するかわからん」
て言ってるやつへの説明として
「自明である」

馬鹿ですね
0754デフォルトの名無しさん
垢版 |
2018/04/13(金) 07:46:29.65ID:EOEX1zZI
コミュ障ですか？
十分かどうかなんて説明する相手次第なんだよ
ポイントの>>715だけでわからないんだから詳細の>>738が必要だろう

>>744？
証明の方針として全くセンスを感じません
回答としては0点ですね
まあじゃあ試しにその方針で証明してみてください
0755デフォルトの名無しさん
垢版 |
2018/04/13(金) 07:51:07.00ID:EOEX1zZI
類似問題としては
円を楕円、五角形などに変える例なんかが考えられますね

数学的センスがない>>744にわかるかな？
0756デフォルトの名無しさん
垢版 |
2018/04/13(金) 08:03:23.71ID:UkpF6ptq
センスとか言い出しちゃったよ w
まあ数学的な反論ができないことはわかった
0761デフォルトの名無しさん
垢版 |
2018/04/13(金) 09:03:55.52ID:NllHkTks
ポイントがわからない ===> 数学的知識の欠如
方針がトンチンカン ===> 数学的センスの欠如
わからない人に「自明」 ===> コミュ障

三重苦

数学的反論の対象が無いものを数学的に反論するのは無理ゲー
0765デフォルトの名無しさん
垢版 |
2018/04/13(金) 12:28:44.65ID:jVGeL/Sn
数学によるマウンティングをするスレができたと聞いて高みの見物に来ました
0766デフォルトの名無しさん
垢版 |
2018/04/13(金) 12:33:48.19ID:UkpF6ptq
>>763
なんで絞る必要があるんだ？
円が無限にあったとしても半径の最小値が存在するかどうかとは関係ない
0767デフォルトの名無しさん
垢版 |
2018/04/13(金) 12:37:25.51ID:prF5m/sZ
Nが2以上で半径の最小値が存在しない状態ってのがまずわからん。
N=0や1の場合で半径0を円として認めない場合、最小値が存在しないってのはわかるけど。
0768デフォルトの名無しさん
垢版 |
2018/04/13(金) 12:53:47.67ID:aZorcSvM
最小値が存在しないなんて主張をしてるのは>>712だけ
最小値が存在するという主張の根拠を聞かれてるのだから、素直に存在する証明をすれば良い

>>744は何の証明にも説明にもなってない
「他に小さいのがなければそれが最小値、小さいのが存在するならさらに小さいのを探す」
こんなものは今回の命題とは関係なく、全順序であれば最小値が存在しようがしまいが言えること
0769デフォルトの名無しさん
垢版 |
2018/04/13(金) 12:55:03.04ID:aZorcSvM
最小値が存在するというポイントを1個も押さえていないので
「ああ、数学が出来ない人だ」という感想が出るだけ
0771デフォルトの名無しさん
垢版 |
2018/04/13(金) 12:58:12.86ID:UkpF6ptq
>>769
> 最小値が存在するというポイントを1個も押さえていないので
どこからそんな頓珍漢なことを思い付いたんだ？ w
0772デフォルトの名無しさん
垢版 |
2018/04/13(金) 12:59:15.87ID:aZorcSvM
>>770
正の実数に最小値が存在する証明
「他に小さいのがなければそれが最小値、小さいのが存在するならさらに小さいのを探す」

結果に関わらず何にでも言えますねえ
0774デフォルトの名無しさん
垢版 |
2018/04/13(金) 13:14:40.36ID:/r/W22v1
>>766
それもそうだね、悪かった

ところで>>744のアルゴリズムが有限回で停止することは保証されてるのかな
あ、あくまで保証されてるかどうか知りたいだけなんでね
0781デフォルトの名無しさん
垢版 |
2018/04/13(金) 19:37:34.13ID:UkpF6ptq
>>774
無限に繰り返せるとしたら極限値は0になる
（単調減少だから）
しかし 1 < n で半径0はあり得ない
なので必ず有限回で停止する
0786デフォルトの名無しさん
垢版 |
2018/04/13(金) 21:09:21.72ID:VaA+ol0W
おそらく最小値は存在するんだろうけど
「1/2 + 1/3 + 1/4 + …」が収束すると思ってるようなレベルのアホがそれを主張することによって
最低限の数学的素養のあるやつらから総ツッコミされてるかんじだな
0788デフォルトの名無しさん
垢版 |
2018/04/13(金) 21:15:38.41ID:+tvQkfv8
数学で論争になるって珍しくないか？
数学って証明されたらそこで議論の余地がなくなるよな。
0789デフォルトの名無しさん
垢版 |
2018/04/13(金) 21:24:20.06ID:17c0MCsX
>>788
すでに証明されてるのに有理数ガーとか無限の円とか必死になってる奴がいるだけ
議論じゃなくマウントとりたいだけなんだろうな
0790デフォルトの名無しさん
垢版 |
2018/04/13(金) 21:28:26.35ID:RiDqcW69
>>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) "
0791デフォルトの名無しさん
垢版 |
2018/04/13(金) 21:42:23.87ID:EOEX1zZI
>>789
>>744が証明になってない
っていう話だぞ

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

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

数学の基礎がわからない人が数学の専門家に数学に関する意見を言うとはなかなか
0792デフォルトの名無しさん
垢版 |
2018/04/13(金) 21:45:58.60ID:17c0MCsX
>>791
> 単調減少の実数列の極限が1になることも100になることもあるわけだが
で、それが最小値がないこととなんの関係があるんだ？
0793デフォルトの名無しさん
垢版 |
2018/04/13(金) 21:48:26.76ID:nIDp//XA
マジで阿呆だな
下に有界かつ協議単調減少だからと言って最小値が存在するとは限らないのだよおバカさん
0802デフォルトの名無しさん
垢版 |
2018/04/13(金) 22:01:36.65ID:nIDp//XA
>>800
族集合の濃度が高々?な集合に関して証明すれば十分なんだから実数関数について言及したところで何も問題ないよね？
むしろ十分正の説明としては申し分ないと思うのだが
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況