- 1 名前：デフォルトの名無しさん mailto:sageteoff [2015/10/07(水) 20:19:06.64 ID:c4LYwtKo.net]
- プログラミングのお題スレです。
前スレ
プログラミングのお題スレ Part7
peace.2ch.net/test/read.cgi/tech/1429195275/
【出題と回答例】
1 名前：デフォルトの名無しさん
お題：お題本文
2 名前：デフォルトの名無しさん
>>1 使用言語
回答本文
【ソースコードが長くなったら】 (オンラインでコードを実行できる)
ideone.com/
codepad.org/
compileonline.com/
rextester.com/runcode
runnable.com/
code.hackerearth.com/
melpon.org/wandbox
https://paiza.io/
宿題は宿題スレがあるのでそちらへ。
- 655 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 14:52:37.15 ID:nbfEIr8Y.net]
- >>642
となると、今のところbrute forceしかアイデアない
- 656 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 15:46:43.07 ID:8juwdgVG.net]
- >>618
C++で貪欲法
フィボナッチ数を小さなフィボナッチ数に分解するところはもっといいやり方があると思う
https://paiza.io/projects/4gT7Vzo3rwr-d2V0q_vK3w
- 657 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 16:13:11.72 ID:1XZ2ZUlZ.net]
- >>644
おぉ、すごいな。上手い。
- 658 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 16:59:17.93 ID:nbfEIr8Y.net]
- >>642のさらに考察してDPで問題なさそうだと思って>>636のを辞書順に選択するように変えてみたけど結果変わらなかった
https://paiza.io/projects/E3IiR1BZVilAaTnBITTY-w
https://out.paiza.io/projects/E3IiR1BZVilAaTnBITTY-w/output.txt
>>636とのdiff取った、同じと出た
https://paiza.io/projects/R-vSh83dQSqE0kq0WGagTA
- 659 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 17:06:57.99 ID:Z+VJIz/8.net]
- >>618 Squeak Smalltalk
| fn |
fn := [:N |
| fibonacciUpTo elems ans |
fibonacciUpTo := [:m |
Array streamContents: [:ss |
| a b |
ss nextPut: (a := b := 1).
[(a := b flag: (b := a + b)) < m] whileTrue: [ss nextPut: a]
]
].
ans := nil.
elems := fibonacciUpTo value: N.
[:exit |
elems size to: 1 by: -1 do: [:m |
elems combinations: m atATimeDo: [:comb |
comb sum = N ifTrue: [ans := comb. exit value]
]
]
] valueWithExit.
ans
].
^(1 to: 10), {100. 1000} collect: [:N | N -> (fn value: N)]
"=> {1->#(1) . 2->#(1 1) . 3->#(1 2) . 4->#(1 1 2) . 5->#(1 1 3) . 6->#(1 2 3) .
7->#(1 1 2 3) . 8->#(1 2 5) . 9->#(1 1 2 5) . 10->#(1 1 3 5) . 100->#(1 2 3 5 13 21 55) .
1000->#(1 1 3 8 21 34 89 233 610)} "
- 660 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 17:07:07.82 ID:nbfEIr8Y.net]
- >>644
何これめっちゃすごいな・・・
フィボナッチ数列に関する定理があるのか
- 661 名前：デフォルトの名無しさん [2016/08/23(火) 22:31:24.67 ID:xhPJKCKw.net]
- >>618
Rubyで。
https://ideone.com/3XA5Qw
- 662 名前：デフォルトの名無しさん [2016/08/24(水) 00:02:28.52 ID:hGPUmbYi.net]
- 良問まとめありますか?
- 663 名前：デフォルトの名無しさん mailto:sage [2016/08/24(水) 00:04:45.93 ID:IQL/zjWi.net]
- 競プロなんてどうでしょう
- 664 名前：デフォルトの名無しさん mailto:sage [2016/08/24(水) 06:31:48.04 ID:emWUYHC0.net]
- >>618 C言語
ideone.com/3s4puY
>>619 C言語
ideone.com/n6mblc
>>630 C言語
ideone.com/bPehld
- 665 名前：デフォルトの名無しさん mailto:sage [2016/08/24(水) 12:37:09.73 ID:IQL/zjWi.net]
- >>652
N =< f(0) + f(1) + ... +f(k) となるkを見つけたときにf(k-1)が>>618の題意を満たすフィボナッチの数の1つで再帰的にN := N - f(k-1)で貪欲法的に求められるのか
理屈が全然分からん
数学は奥が深すぎ
- 666 名前：デフォルトの名無しさん mailto:sage [2016/08/24(水) 15:34:01.41 ID:DjG9ToKL.net]
- f(0)+f(1)+...+f(k)=f(k+2)-1だから
N>=f(k+1)&&N<f(k+2)を満たすkを探してf(k-1)を選びN-f(k-1)を次のNとして再帰と言い換えたほうがわかりやすい
条件を満たす場合をちょっと式変形すると2f(k)>N-f(k-1)>=f(k)で
フィボナッチ数列の今てきとーに考えたガバ不等式だと2f(k)>=f(k+1)>=f(k)で考えたら再帰の途中で
N-f(kー1)>=f(k+1) && N-f(k-1)<f(k+2)
みたいなkが存在しててもおかしくなさそうだけど大丈夫なのかー
- 667 名前：デフォルトの名無しさん mailto:sage [2016/08/24(水) 16:45:04.33 ID:38RcxOvs.net]
- >>653 N:=N-f(k)やんか！ならf(k+1)>N-f(k)>=f(k-1)になるから帰納法で展開可能なことはすぐに証明出来そうだね
おそらく>>652はフィボナッチ数の大きい方から順に、自然数をフィボナッチ部分列で展開できるギリギリの大きさのフィボナッチ数を選んでる
- 668 名前：デフォルトの名無しさん [2016/08/24(水) 17:22:27.06 ID:hGPUmbYi.net]
- そもそも理解があやしいから確認したいが・・・
フィボナッチ数列でなるべく小さいNをとって、集合{f(1), ・・・,f(N)}で
その部分の和をある数と一致させるって話?
- 669 名前：デフォルトの名無しさん [2016/08/24(水) 17:30:24.68 ID:hGPUmbYi.net]
- >>656とすると、Nの下限は>>652のように総和を計算すればすぐ求まるな。
しかし、任意の数はフィボナッチ数列の部分集合の和で表現できるかとか、
上でf(N)を引き算した数がN-1以下の部分集合の和で表現できるとかは簡単か?
- 670 名前：651 mailto:sage [2016/08/24(水) 20:06:38.41 ID:emWUYHC0.net]
- >>655の言うように展開できるぎりぎりの数を順に選んでます。
とりあえず、f(0)+f(1)+...+f(n)=sum(n) とした場合、
1〜sum(n)の整数はf(0)〜f(n)の部分和で表すことができる
例）フィボナッチ数列の最初の6つ[0,1,1,2,3,5]を使えば1〜12までの数を表せる
というのを前提に、与えられた数がsum(n)より大きくsum(n+1)以内なら
必ずf(n+1)が含まれるということを、残りの数が0になるまで再帰的に計算しています。
最初の前提は、数列を一辺とした正方形をつなげていくというあの形から
直感的になんとなく。1〜sum(n)がf(0)〜f(n)の数列の組み合わせで表せるなら
sum(n)>=f(n+1)（n>=1の場合）
なので1〜sum(n+1)もf(0)〜f(n+1)の数列の組み合わせで表せるということに
なるんじゃないのかなぁと。正直全く自信ないです。
自分が書いたコードは、求めたフィボナッチ数列を配列に保存していたけど
その必要全くなかったですね。 ideone.com/oUIvN8
- 671 名前：デフォルトの名無しさん mailto:sage [2016/08/24(水) 20:50:39.06 ID:Gt3DCYIG.net]
- >>618
@Mathematica
ideone.com/jtWvsW
- 672 名前：デフォルトの名無しさん mailto:sage [2016/08/25(木) 19:55:54.39 ID:1lQyPTY4.net]
- >>657
>上でf(N)を引き算した数がN-1以下の部分集合の和で表現できるとかは簡単か?
f(0)=0,f(1)=1,f(2)=1,f(3)=2,...のようにインデックスを決めておく。
命題：k>=1のときf(k+2) > N >=f(k+1)を満たす任意の自然数Nは{f(0),...,f(k)}の部分集合の和で表せる。
k=1のとき自明
k>=1で成立を仮定しk+1で命題が成り立つことを示す。
書き下すとf(f+3)>N>=f(k+2)を{f(0),...,f(k+1)}の部分列の和で表せればおｋ。
そこで部分列の一番大きなf(k+1)で全体を引き算すると
f(k+3)-f(k+1)>N-f(k+1)>=f(k+2)-f(k+1) ⇔ f(k+2) >N-f(k+1) >=f(k)
となり仮定よりN-f(k+1)は{f(0),...,f(k+1)}の部分列の和で表せる。
以上から帰納法で命題は正しい。
簡単すぎｗｗｗｗ
- 673 名前：デフォルトの名無しさん mailto:sage [2016/08/25(木) 19:59:23.41 ID:1lQyPTY4.net]
- >>660
>となり仮定よりN-f(k+1)は{f(0),...,f(k+1)}の部分列の和で表せる。
×N-f(k+1)は{f(0),...,f(k+1)}
〇N-f(k+1)は{f(0),...,f(k)}
- 674 名前：デフォルトの名無しさん [2016/08/26(金) 00:23:54.59 ID:iNPRC5gr.net]
- 速度が向
- 675 名前：上したのかどうか計るためのベースとして簡単なベンチマークテスト作った。
適当にウェイトいれて、機種・コンパイラの偏りをなくすようにしてみた。
http://ideone.com/KceBs4
ここ参考にした。
http://www001.upp.so-net.ne.jp/y_yutaka/labo/math_algo/calcbench.html [] - [ここ壊れてます]
- 676 名前：661 [2016/08/26(金) 00:28:49.61 ID:iNPRC5gr.net]
- ちょい疑問がシフト演算は早いという定説はあるとおもうが。
実際、計測比較してみると足し算、引き算よりも遅い。
オーバーフローが原因で遅くなってる気はするが・・・
- 677 名前：デフォルトの名無しさん mailto:sage [2016/08/26(金) 00:34:55.42 ID:46yZwIqt.net]
- >>663
コンパイラが最適化しちゃうからじゃね？
- 678 名前：デフォルトの名無しさん [2016/08/26(金) 00:47:03.70 ID:iNPRC5gr.net]
- 最適化対策として、計算結果を引き継ぐことで、ループ無視は防止できてるはず・・・
- 679 名前：デフォルトの名無しさん [2016/08/26(金) 01:07:03.15 ID:iNPRC5gr.net]
- 計算途中で、内部でオーバーフローか型変換が起こって遅くなってると予測してみて、
整数値で扱えない範囲にならないように、足し算のところビットORで代替してみたけど同速度だった。
単純にシフト演算が遅いだけっぽい。
- 680 名前：デフォルトの名無しさん mailto:sage [2016/08/26(金) 01:29:53.53 ID:rbtqc2qT.net]
- gccのo3でコンパイルしてみたけど確かにShiftが一番遅かった
どうしてこうなるかはアセンブリみれば一瞬でわかるよ
- 681 名前：デフォルトの名無しさん mailto:sage [2016/08/26(金) 01:53:05.11 ID:rbtqc2qT.net]
- shiftも早くなるようにおまじないかけといたよ
ideone.com/t1qv2O
- 682 名前：デフォルトの名無しさん mailto:sage [2016/08/26(金) 01:54:53.90 ID:rbtqc2qT.net]
- すまんローカルだと早くなってたんだが
Shift 421.0ms → 101.0ms
- 683 名前：デフォルトの名無しさん [2016/08/26(金) 01:56:20.02 ID:iNPRC5gr.net]
- アセンブラはわからないけど。
内部で型変換がおってる説が間違いとすると、計算回数だろな・・・
シフト測定はシフト+足し算をしてて、足し算測定のほうは足し算一つだけ。
足し算測定のほうを、足し算1つ上乗せして公平にしてみる。
- 684 名前：デフォルトの名無しさん mailto:sage [2016/08/26(金) 02:01:15.45 ID:CVrNr9ea.net]
- clang 3.7のCで動かしたらこんなんなったんだがどういうことだ？
ideone.com/5Cjgpy
ちゃんと動いてないのか最適化でばっさりなのか
- 685 名前：デフォルトの名無しさん mailto:sage [2016/08/26(金) 02:02:55.47 ID:CVrNr9ea.net]
- clangの方が普通に最適化が効いて、gccの方が効いてないだけか？
- 686 名前：デフォルトの名無しさん mailto:sage [2016/08/26(金) 04:26:31.05 ID:Mbltetpr.net]
- gcc6.2.0使ってコンパイルしたらAVX2命令使いまくりで激速になった
- 687 名前：デフォルトの名無しさん [2016/08/26(金) 22:19:12.01 ID:iNPRC5gr.net]
- 良いベンチマーク考案中。
実際の問題を解いたプログラム / 基準ベンチマーク
の時間比がほぼ一定が良い。機種、コンパイラによらず。
- 688 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 01:33:01.65 ID:UE0kbjNO.net]
- >>662
最適化対策のための出力っていうのが良く分からん
あと、各々の命令の重さの係数（weight）はどうやって決めてるの？
- 689 名前：デフォルトの名無しさん [2016/08/27(土) 01:40:19.24 ID:7nFiTNgH.net]
- 必要の計算は無視される最適化に対応。、
意味はないけど最後まで計算を引き継いで出力する。各計算を和でつなぐ。
- 690 名前：デフォルトの名無しさん [2016/08/27(土) 01:42:17.34 ID:7nFiTNgH.net]
- 必要のない計算は・・・
- 691 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 02:40:42.60 ID:UE0kbjNO.net]
- なるほど、そういうことか。
シフト命令が遅いのは変数kでシフトしてるからじゃないかな。
kビットシフトするのではなく1ビットシフトをk回繰り返した方が早くなるかも？
- 692 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 11:38:15.27 ID:2qjvRKJV.net]
- つづきは個人のブログかチラシの裏でやれ
- 693 名前：デフォルトの名無しさん [2016/08/27(土) 12:50:08.51 ID:8oHlLwTt.net]
- お題: 数字が書かれたn枚の紙切れが袋に入っています。
この袋から紙切れを取り出し、数字を見て袋に戻すということをx回行います。
x回の紙切れの数字の和がmになる確率を返す関数fを定義してください。
(let ((k '(1 3 5)) (m 10) (x 4)) ; n = 3, m = 10, k = {1, 3, 5}, x = 4
(f k m x))
=> 16/81
(let ((k '(1 3 5)) (m 9) (x 4)) ; n = 3, m = 9, k = {1, 3, 5}, x = 4
(f k m x))
=> 0/81
(let ((k '(1 2 3 4 5)) (m 15) (x 5)) ; n = 5, m = 15, k = {1, 2, 3, 4, 5}, x = 5
(f k m x))
=> ?
- 694 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 14:21:38.42 ID:/lPBBpET.net]
- 同じ数字の紙は何枚あってもいいの？
全部違う数字？
入っている数字はmより小さいの？
- 695 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 14:28:53.21 ID:/lPBBpET.net]
- ああ、ごめん。忘れてｗ
- 696 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 14:54:16.82 ID:9mBmz7KO.net]
- >>680
ideone.com/6XEpQt
C++。モンテカルロ。サンプル数少なすぎて収束してない。
確立はよくわからん。
- 697 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 15:28:29.92 ID:9mBmz7KO.net]
- >>683 をちょびっと整形した。
ideone.com/l9zgpe
- 698 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 16:50:12.54 ID:FbbA5YyG.net]
- >>680 Java
ideone.com/6BEAKE
- 699 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 18:38:18.89 ID:F1nYMYS3.net]
- >>680 C(C99)
ideone.com/IRsTjt
- 700 名前：デフォルトの名無しさん mailto:sage [2016/08/27(土) 23:43:10.10 ID:8oHlLwTt.net]
- >>630 Emacs Lisp
(defun g (l s i)
(if (null l)
t
(let ((x (funcall (nth (% i 2) '(+ -)) s (car l))))
(when (<= (abs x) 10.0)
(g (cdr l) x (1+ i))))))
(defun f (l)
(g l 0 0))
f
(f '(2 4 2 4 2 4 2 4 2 4 0))
t
(f '(2 4 2 4 2 4 2 4 2 4.1 0))
nil
(f '(2 4 1 10 10 1 4 2 0))
nil
(f '(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3))
t
- 701 名前：デフォルトの名無しさん mailto:sage [2016/08/28(日) 21:20:07.72 ID:9IFYhCBA.net]
- あなたはN円分の商品を1個購入することになりました。
おサイフの中には1,5,10,50,100,500円玉がそれぞれ1000枚あります。
価値の高い硬貨を優先に支払いに回すときに、それぞれの支払いに使う硬貨の枚数を求めよ
出力はカンマ区切りで左から1,5,10,50,100,500円の順に枚数を出力しなさい
例題
N=1111
出力
1,0,1,0,1,2
1円が1枚、10円が1枚、100円が1枚、500円が2枚なのでこうなります
- 702 名前：デフォルトの名無しさん mailto:sage [2016/08/28(日) 21:22:27.37 ID:gdb/jxff.net]
- ちょっと財布を想像して吹いたｗ
- 703 名前：デフォルトの名無しさん mailto:sage [2016/08/28(日) 21:26:10.45 ID:CCZyZi8n.net]
- >>688
それ1000枚の条件いるの？
- 704 名前：デフォルトの名無しさん [2016/08/28(日) 22:06:25.06 ID:sxo5kh14.net]
- >>688
Rubyで。
https://ideone.com/fRleLH
- 705 名前：デフォルトの名無しさん mailto:sage [2016/08/28(日) 22:43:07.98 ID:FpzTx2tv.net]
- >>688 Emacs Lisp
(require 'cl-lib)
(setq purse (sort (append (make-list 1000 1) (make-list 1000 5) (make-list 1000 10) (make-list 1000 50) (make-list 1000 100) (make-list 1000 500)) #'>))
(defun f (N purse payment)
(assert (and (integerp N) (> N 0)))
(if (null purse)
""
(let ((x (car purse)))
(cond
((> x N) (f N (cl-remove-if #'(lambda (c) (= c x)) purse) payment))
((< x N) (f (- N x) (cdr purse) (cons x payment)))
((= x N) (cl-reduce #'(lambda (a b) (concat a "," b)) (mapcar #'(lambda (c) (number-to-string (count c (cons x payment)))) '(1 5 10 50 100 500))))))))
(f 1111 purse '())
"1,0,1,0,1,2"
(let ((max-lisp-eval-depth most-positive-fixnum)
(max-specpdl-size most-positive-fixnum))
(f 500500 purse '()))
"0,0,0,0,5,1000"
(let ((max-lisp-eval-depth most-positive-fixnum)
(max-specpdl-size most-positive-fixnum))
(f 666001 purse '()))
""
- 706 名前：デフォルトの名無しさん mailto:sage [2016/08/29(月) 00:10:36.80 ID:G+hsDqDY.net]
- >>688
C++で
- 707 名前：
http://ideone.com/p4dwIW
>>690
まあ本質的な意味はないけど一応1000枚の条件で答えは変わるぐらい
N=500500
0,0,0,0,5,1000 [] - [ここ壊れてます]
- 708 名前：デフォルトの名無しさん [2016/08/29(月) 10:41:31.05 ID:6rwIECPC.net]
- まえにあった問題の解法が不明。
nに対して、2次元平面の円で、その円周上の整数点がちょうどn個となる円の最小半径を求める問題。
- 709 名前：デフォルトの名無しさん mailto:sage [2016/08/29(月) 16:45:06.30 ID:fFx5B9de.net]
- >>694
問題関係のレスと自分が書いたコード見直したが、何やってるのかわけわからんくなってたから困るｗｗ
- 710 名前：デフォルトの名無しさん [2016/08/30(火) 01:05:58.62 ID:0bBTSjL7.net]
- 整数 a(0)、・・・、a(n)が与えられた時、
すべてのi に対して、 a(i) + c ≡ 0 (mod m)が成り立つような
m、c >1を求める問題。
- 711 名前：デフォルトの名無しさん mailto:sage [2016/08/30(火) 01:20:54.99 ID:XiF8vPmR.net]
- はい。
- 712 名前：デフォルトの名無しさん mailto:sage [2016/08/30(火) 03:54:00.29 ID:ccTd05WG.net]
- >>694
前スレからもってきたけど円の中心点の情報は書いてくれよ、めちゃくちゃ重要だろ
41 ：デフォルトの名無しさん：2015/05/01(金) 14:31:24.98 ID:9G1+bMO9.net
お題：ちょうどn個(1 < n)の格子点(x座標もy座標も整数の点)を通る円の半径の
最小値を求める。円の中心点は格子点でなくてよい。
例
n=2 -> 0.5
n=5 -> 16.170331
n=6 -> 2.5
- 713 名前：デフォルトの名無しさん mailto:sage [2016/08/30(火) 07:35:24.70 ID:o3zijpP7.net]
- >>680 Common Lisp
ideone.com/yyVA7g
>>688 C++11
ideone.com/rNuPAy
- 714 名前：デフォルトの名無しさん mailto:sage [2016/08/30(火) 11:00:38.72 ID:bKDKxVCe.net]
- >>698
そのn=5は間違えてるから訂正しとく
N=5 (1/6,1/6) R=5.892557 R^2=625/18
- 715 名前：デフォルトの名無しさん [2016/08/30(火) 11:59:20.10 ID:0bBTSjL7.net]
- >>698
個数4N個のときは最小半径と整数点を簡単に求める方法見つかった。 個数4、8、12、16、20、24・・・・のとき。
4で割って1余る素数を最初に求めておく。 5、13、17、29、37、41・・・・・
Nを適当に積に分解して、N = a(1) * ・・・ *a(i) 、a(1) >= a(2) >= ・・を満たすようにして。
半径2乗を5^(a(1)-1) * 13^(a(2)-1) * 17^(a(3)-1)・・・・とする原点中心の円周の格子点の数は、4N個。
最小半径をあたえるNの積分解を一発で求めるアルゴリズムはしらんが、この方針で間違いないはず。
- 716 名前：デフォルトの名無しさん [2016/08/30(火) 12:11:16.96 ID:0bBTSjL7.net]
- まちがってた・・・・これと比較してみたら。 たとえば
8個のときは (2x-1)^2 + (2y-1)^2 = 5
12個のときは、(2x-1)^2 + (2y-1)^2 = 5^2
16個のときは、(2x-1)^2 + (2y-1)^2 = 5*13
20個 のときは、(2x-1)^2 + (2y-1)^2 = 5^4
でいいらしい。
>>701を2で割ったらほぼ合ってるかと・・・
118 名前： 投稿日：2015/05/14(木) 19:56:36.53 ID:rp22TBsk
>>118
俺が計算したのではこんなん
ただし半径256以上は最小じゃないかも知れないから注意
ideone.com/2WBTbl
- 717 名前：デフォルトの名無しさん [2016/08/30(火) 12:28:56.64 ID:0bBTSjL7.net]
- >>702によると、41個の場合の方程式は、
(14x-1)^2 + (14y-1)^2 = 5^2 * 13^2 * 17^2 * 41^2 らしい。
予想するとこれはより半径を縮められるはず。
たとえば、適当に a、b、cをとれば、 ( ax + b)^2 + ( ax + c)^2 = 5^2 * 13^2 * 17^2 * 29^2
の格子点数が41個にできる可能性。
右辺はこれに限るとは言い切れないけど。
最初の右辺でもいまのでも、原点を通る円 x^2 + y^2 = ・・・としてはどちらも格子点数は4*3*3*3*3=324個のはず。
- 718 名前：デフォルトの名無しさん [2016/08/30(火) 12:45:23.63 ID:0bBTSjL7.net]
- 324/7 = 46.28、
324/8 = 40.5なので、
>>703でaは8以上だと、41点以上生成できないはず・・
aは7もしくは14で決め打ちして。2倍するのだけは特別でこれは解個数を変化させない可能性。>>702と同様。
しかし2倍しないほうがよリみつかりやすいはず・・
適当にa、bをとれば
( 7x + a)^2 + ( 7x + b)^2 = 5^2 * 13^2 * 17^2 * 29^2 の形で41点生成できると予想。
- 719 名前：デフォルトの名無しさん mailto:sage [2016/08/30(火) 13:17:27.27 ID:bKDKxVCe.net]
- 5^2 * 13^2 * 17^2 * 41^2で出てくるのは39点と42点じゃないかな？
数学の事よくわからないけど。
- 720 名前：デフォルトの名無しさん mailto:sage [2016/08/30(火) 13:23:30.96 ID:bKDKxVCe.net]
- おっと間違えた
5^2 * 13^2 * 17^2 * 29^2 の形で出てくるのが39点と42点な
- 721 名前：デフォルトの名無しさん [2016/08/30(火) 13:55:35.84 ID:0bBTSjL7.net]
- いや数学的な裏付けなどなく、たんなる予測だけど・・
いま検証コード作成中。
- 722 名前：デフォルトの名無しさん [2016/08/30(火) 15:04:25.03 ID:0bBTSjL7.net]
- >>706
そのとおりだったわ。どういう理屈?
あと、計算が間違ってなければ>>703は解なしで、41点でてくる方程式は
(7x-1)^2 + (7y)^2 = 5^2 * 13^2 * 17^2 * 41^2 だった。
- 723 名前：デフォルトの名無しさん mailto:sage [2016/08/30(火) 15:29:46.99 ID:bKDKxVCe.net]
- >>708
理屈はわからんｗ
昔書いた探索コードでそのまま格子点数出せそうな感じだったので、
5^2*13^2*17^2*29^2を突っ込んでみたら39と42が出ただけｗ
んで、半径として考えるとN=41は
(7x-1)^2 + (7y)^2 = 5^2 * 13^2 * 17^2 * 41^2ではなく、
(14x-1)^2 + (14y-1)^2 = 2 * 5^2 * 13^2 * 17^2 * 41^2になるんかな。
- 724 名前：デフォルトの名無しさん [2016/08/31(水) 16:46:14.27 ID:9ufvv7Gu.net]
- 円の格子点のやつは、P=NPとかいった計算理論の話題とみて、難しいクラスでは?
素因数分解とか、巡回セールスマン問題と較べても計算困難では?
( Ax + B)^2 + ( Ax + C)^2 = R^2は半径はR/Aだけど、RもAも無限大までしても、最小半径になる可能性があって。
一つ解けた半径が、最小値なのかすら調べられない気が・・
AかRに上限あるとでも証明できれば別だが。
- 725 名前：デフォルトの名無しさん [2016/08/31(水) 19:35:22.89 ID:9ufvv7Gu.net]
- たとえば、2点のときの最小半径は0.5らしいが・・・ 方程式は(2x)^2 + (2y-1)^2 = 1で。
a 十分大で、r/a < 0.5 を満たすとして、( ax -b )^2 + ( ay -c )^2 = r^2の格子点数が2点のみとなる場合はないのか?
- 726 名前：デフォルトの名無しさん [2016/08/31(水) 19:38:46.35 ID:9ufvv7Gu.net]
- >>711が合ってた場合、最小半径はいくらでも小さくできると予想。
>>711が合ってない事を証明できる人いる?
- 727 名前：デフォルトの名無しさん [2016/08/31(水) 19:40:33.34 ID:9ufvv7Gu.net]
- すまん。そんなわけがなかった。半径が小さすぎれば図を書いてみて格子点が発生しない。
- 728 名前：デフォルトの名無しさん mailto:sage [2016/08/31(水) 19:47:55.57 ID:p1K5Mzky.net]
- 半径が自然数で中心が原点ならピタゴラス数の数を調べればわかるんだけどな。
- 729 名前：デフォルトの名無しさん mailto:sage [2016/08/31(水) 19:49:26.51 ID:NSLbELcw.net]
- その相似形は等価？相似検出するのメンドクセーけど。
- 730 名前：デフォルトの名無しさん [2016/08/31(水) 20:41:09.29 ID:9ufvv7Gu.net]
- 円内部の格子点数を不等式で挟める式あった。
少し大きい円、少し小さい円のドーナツ型にしたら、円周上の格子点数の理想値が求まるかと・・・
ガウスの円問題
原点を中心とした半径rの円の内部(境界を含む)にある整数点の個数をR(r)で表す.
R(r)は円の面積の推定値を与える.R(100)/100＾2 = 3.1417
ガウスは |R(r)-πr＾2|<crを示したが,|R(r)-πr＾2|<cr＾k
となるkの最小値を求める問題に一般化される.
シェルピンスキーはk≦2/3を証明し,ガウスのk=1を改善.
1963年に陳景潤はk≦24/37を,1990年にハクスリーはk≦46/73を得た.
k=1/2と予想されている.
www.geocities.jp/ikuro_kotaro/koramu/834_r2.htm
- 731 名前：デフォルトの名無しさん mailto:sage [2016/08/31(水) 20:41:41.64 ID:p1K5Mzky.net]
- 半径rのときの点の最大数は
bごとにaを変化させていってx、yが同時に整数になる数の最大数だな。
x=r (cos a +cos b)
y=r(sin a+ sin b)
- 732 名前：デフォルトの名無しさん [2016/09/01(木) 00:30:32.18 ID:F9uf4uEu.net]
- R(r) 半径rの円の内部の整数点の個数
L(r) 半径rの円の円周上の格子点の個数として。
rより小さいsをとれば、
L(r) <= πr＾2 + cr＾k - ( πs＾2 - cs＾k ) 、s -> rとして =2cr＾k
>>716にはcの値が書いてないが適当にc=7/2として、
よりよい評価したいのでk=1/2とすると、L(r) <= 7√r
うまく円周上に格子点を配置できたときの上限が7√r。
円周上の格子点を
32点生成できるrはr^2 = 5*13*17/2
64点生成できるrはr^2 = 5^3*13*17/2 らしいので
上の公式で計算してみると
上 = 7√r = 33.9375
下 = 7√r = 75.8867
評価式の性能はいまいち。
評価値とぴったり一致すれば最小半径が証明できるとおもったが使えない。
- 733 名前：デフォルトの名無しさん [2016/09/01(木) 01:40:05.53 ID:F9uf4uEu.net]
- しかし、評価式のべつの使い道があるな。 L(r) < 7√rは正しい前提として。
たとえば、100点生成できる半径を求めようとしたとき、
L(203) < 99.7346 だから、半径が203以下ではムリだと判明する。探索するとき幅は狹められる。
- 734 名前：デフォルトの名無しさん mailto:sage [2016/09/01(木) 08:42:57.18 ID:d9inzlx2.net]
- どこかほかでやってくれないかな…
- 735 名前：デフォルトの名無しさん mailto:sage [2016/09/01(木) 18:50:15.31 ID:wr8HVpEY.net]
- そうだな。そもそも単なる数学の問題を
お題化したって、どうせ宿題なんだろって思ってしまう
- 736 名前：デフォルトの名無しさん [2016/09/02(金) 16:08:29.58 ID:szLK569k.net]
- 円周の格子点は一年半弱まえのやつだし、数学、数学の宿題の範疇では解けるとはおもえない。
僅かでも円のイチをずらせば格子点がまったく無くなったりするわけで
コンピュータの力技は必要だろ? ある程度、探索範囲をせばめることはできても検証でプログラムいるとおもう。
- 737 名前：デフォルトの名無しさん mailto:sage [2016/09/02(金) 19:02:35.81 ID:VYGld2xC.net]
- 思考垂れ流しうんこマンが自重してくれればそれでいい
一人で連投してんじゃねー
- 738 名前：デフォルトの名無しさん mailto:sage [2016/09/02(金) 20:03:49.13 ID:enD9pirT.net]
- 「論よりコード」
- 739 名前：デフォルトの名無しさん mailto:sage [2016/09/02(金) 21:05:07.04 ID:+wy8tThR.net]
- この流れならむしろ数学板でもいいとおもう
- 740 名前：デフォルトの名無しさん mailto:sage [2016/09/02(金) 21:52:48.00 ID:e1jBggiu.net]
- お題：
下図のように山の麓（標高0）の両側にいるA君B君が頂上（標高10）を目指して同時に出発する
ただし、A君B君のいる位置の標高はどの時刻でも等しくなるように登らなければならない
（下図でA君が標高7の峠から標高3の谷へ下るときにはB君は来た道を引き返す必要がある）
標高1だけ上るor下るのに1時間かかるとして頂上まで最短で何時間かかるか求めよ
10
7 ／＼
／＼／3 ＼
Ａ 0／ ＼0 Ｂ
山の形状は以下のような文字列で表現する
１）文字列の先頭と末尾はA君B君のスタート地点（標高0）を表し、必ず'0'である
２）ゴールの頂上（標高10）の位置は':'で表す（文字コードがちょうど':'='0'+10なので）
３）途中の峠と谷の標高を'1'〜'9'で表す（上図の山の形状は"073:0"と表される）
４）途中の峠と谷は交互に現れるようにする（例えば"037:0"は無し）
テスト例
"073:0" -> 18
"07362:450" -> 36
"06464:36470" -> 42
"0827171:28480" -> 66
"0737491:28180" -> 146
"05374734372747484:184618186912120" -> ?
- 741 名前：デフォルトの名無しさん mailto:sage [2016/09/02(金) 23:34:33.91 ID:hbWVf6eK.net]
- A：012101....
B：012123...
詰む気がするんだけど
- 742 名前：デフォルトの名無しさん mailto:sage [2016/09/03(土) 04:18:59.59 ID:P0QwwpBf.net]
- >>726
c++ https://ideone.com/2sIaGw
とりあえず、サンプルが通ったからsubmitって感じ。
- 743 名前：デフォルトの名無しさん [2016/09/03(土) 08:16:17.90 ID:QWBdU6+p.net]
- 一年半弱立っててもまともなコードがあがってない難問。 論、一部結果はでてるが有効打ゼロ。
- 744 名前：デフォルトの名無しさん mailto:sage [2016/09/03(土) 18:06:05.39 ID:fVb/pFms.net]
- >>728
https://ideone.com/2sIaGw (上書き修正)
BFS版を追加して、それを本採用
※依然として低い高さ制限=10に甘えたコードになっている
- 745 名前：デフォルトの名無しさん mailto:sage [2016/09/03(土) 20:46:56.74 ID:hrFRXovl.net]
- >>604 OCaml(勉強中)
ideone.com/fRBQlj
F#と並行してその元になってるOCamlの勉強も始めてみました
yukicoderで同じ問題やったらOCamlの方が実行時間8倍速、使用メモり1/7くらいだった･･･
- 746 名前：デフォルトの名無しさん [2016/09/04(日) 04:44:05.42 ID:swx+XD0y.net]
- >>726
Ruby
https://ideone.com/LcrSC5
- 747 名前：デフォルトの名無しさん [2016/09/04(日) 10:12:56.94 ID:AIgtYd56.net]
- 円周の格子点は、
平面上の0-45度部分へ整数点の中心(a,b)を取って
原点を通る円、 (x-a)^2 + (y-b)^2 = r^2, (r^2 =a^2 + b^2)をベースに
整数mをとって解個数を1/m以下にする操作、
(mx-a)^2 + (my-b)^2 = r^2を考えればよさげ。
これならa,b,mは小さい順に無駄なく動かせ網羅できるかと。
- 748 名前：デフォルトの名無しさん mailto:sage [2016/09/04(日) 14:51:14.83 ID:+9WebUQ3.net]
- >>733
論よりコード もしくは演算結果
- 749 名前：デフォルトの名無しさん mailto:sage [2016/09/07(水) 01:44:45.83 ID:Bbadz6db.net]
- >>726 Emacs Lisp
(require 'cl-lib)
(defun f (s)
(let* ((e (reduce (lambda (a b) (concat a (substring b 1)))
(mapcar (lambda (x) (let ((a (car x)) (b (cdr x)))
(macrolet ((c (d) `(loop for i from a ,d b concat (string i)))) (if (< a b) (c to) (c downto)))))
(loop for i from 0 below (1- (length s)) collect (cons (aref s i) (aref s (1+ i)))))))
(f (position ?: e)) (g (substring e 0 (1+ f))) (h (apply #'string (reverse (string-to-list (substring e f)))))
(w 0) (y '(((0 . 0) 0 nil))))
(while y
(let ((i (caaar y)) (j (cdaar y)))
(if (and (= (aref g i) ?:) (= (aref h j) ?:))
(setq w (cadar y) y nil)
(setq y (append y (mapcar (lambda (x) (list x (1+ (cadar y)) (cons (cons i j) (caddar y))))
(remove-if (lambda (x) (or (< (car x) 0) (< (cdr x) 0) (find x (caddar y) :test 'equal) (/= (aref g (car x)) (aref h (cdr x)))))
(list (cons (1+ i) (1+ j)) (cons (1+ i) (1- j)) (cons (1- i) (1+ j)) (cons (1- i) (1- j)))))))))
(pop y))
w))
(f "073:0") 18
(f "07362:450") 36
(f "06464:36470") 42
(f "0827171:28480") 66
(f "0737491:28180") 146
(f "05374734372747484:184618186912120") 400
(f "021:120") 12
(f "091:280") 62
- 750 名前：デフォルトの名無しさん mailto:sage [2016/09/09(金) 01:34:40.70 ID:U1OL4Uha.net]
- >>726
Haskell
ideone.com/SHS7xc
- 751 名前：デフォルトの名無しさん mailto:sage [2016/09/12(月) 09:47:06.73 ID:lP0lbdh9.net]
- お題: Hello, World! を円形にして出力。
円形の定義、CUI, GUI どちらでやるかも自由。
丸くなっていれば良しとする。
- 752 名前：デフォルトの名無しさん mailto:sage [2016/09/12(月) 16:48:28.87 ID:cNnBFZuZ.net]
- >>737 Javascript
codepen.io/anon/pen/VKvNOg
- 753 名前： []
- [ここ壊れてます]
- 754 名前：デフォルトの名無しさん mailto:sage [2016/09/13(火) 03:30:08.30 ID:jvr3tDVu.net]
- ideone.com/cGLp0X
C++。イデオンで再現しようと思ってエスケープシーケンス検索したら、
win10の以前のアップデートで限定的に復活してたので使ってみた。
イデオンでは通らなかった。Orz
- 755 名前：デフォルトの名無しさん mailto:sage [2016/09/13(火) 03:30:44.87 ID:jvr3tDVu.net]
- 画像つけ忘れた。Orz
sssp://o.8ch.net/gsxd.png
|
 |
