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

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/ 宿題は宿題スレがあるのでそちらへ。 610 名前：デフォルトの名無しさん mailto:sage [2016/08/14(日) 20:29:36.17 ID:itqO338w.net] >>598 問題例に不備があるじゃないか。 611 名前：デフォルトの名無しさん mailto:sage [2016/08/14(日) 21:16:51.46 ID:HA8B0Krx.net] 訂正 問題例 --c- cab- cbac ---- 答え 4 --c-|----|--c-|---- -ab-|----|--b-|-a-- ----|cba-|--a-|cb-- ----|----|----|---- 612 名前：デフォルトの名無しさん mailto:sage [2016/08/15(月) 01:18:23.97 ID:ATOVcA82.net] 全てのbの上下左右にあるaの数*cの数を足せば良いんだな。 613 名前：デフォルトの名無しさん mailto:sage [2016/08/15(月) 05:08:48.91 ID:VvgCdVoy.net] >>598 >>600 ideone.com/AW6YTZ C++。Yukiだとサンプルしか通らなそうなコード。 まぁ、これが俺の地だしなぁ。 俺は俺にガッカリだよ。Orz 614 名前：デフォルトの名無しさん mailto:sage [2016/08/15(月) 05:19:59.98 ID:VvgCdVoy.net] >>598 >>600 ideone.com/oUQbfM C++。>>601メソッド？？ ちょっとすっきりした。 615 名前：デフォルトの名無しさん mailto:sage [2016/08/15(月) 13:40:01.81 ID:YWGtPoG/.net] お題 ズッカーマン数(Wikipediaより) ズッカーマン数（-すう、Zuckerman number）は自然数で、各桁の数字の総乗が元の数の約数 であるような数である。例えば315は各桁の数字の積が 3×1×5=15 であり、15は 616 名前：315の約数で あるので315はズッカーマン数である。 ズッカーマン数を最初から100個求めよ。 [] [ここ壊れてます] 617 名前：デフォルトの名無しさん mailto:sage [2016/08/15(月) 13:49:14.49 ID:/RUSPZDT.net] 梅干し食べて... なんか力技でやるしかなさそうな感じだな 618 名前：デフォルトの名無しさん mailto:sage [2016/08/15(月) 14:10:04.63 ID:VvgCdVoy.net] >>604 ideone.com/t6xXhj C++。あってるかな？ 619 名前：デフォルトの名無しさん mailto:sage [2016/08/15(月) 20:11:53.65 ID:NvOrOVSG.net] こんな感じでいいのか？ ideone.com/NJ6rGr 620 名前：デフォルトの名無しさん mailto:sage [2016/08/15(月) 20:38:01.87 ID:/9WWz1kS.net] なぜいいと思った 621 名前：デフォルトの名無しさん mailto:sage [2016/08/15(月) 21:21:48.34 ID:cQHsobNS.net] C ideone.com/peczRr 622 名前：デフォルトの名無しさん mailto:sage [2016/08/16(火) 01:56:24.06 ID:fBfaZTKr.net] >>604 F#勉強中@半年 https://paiza.io/projects/Zt_Tw1LaKtiB93Fi6dWkJQ Wikipediaに書いてある数字との照らし合わせはしました あと、paiza.ioのを貼るのは初めてなのでうまく貼れてるかどうか・・・ ちなみに、F#は主にyukicoderで鍛えてます、少しは分かってきたかも 623 名前：デフォルトの名無しさん mailto:sage [2016/08/16(火) 02:08:11.71 ID:q0PyZcrj.net] >>598 >>601のやり方で C言語 ideone.com/wkEP9Z >>604 C言語 ideone.com/Pxskoy 624 名前：デフォルトの名無しさん mailto:sage [2016/08/16(火) 14:43:03.45 ID:9WgV32AQ.net] >>604 @Mathematica ideone.com/tq9juG 625 名前：デフォルトの名無しさん mailto:sage [2016/08/17(水) 08:55:07.31 ID:5k4XIPv4.net] >>604 Squeak Smalltalk | Zuckerman | Zuckerman := Generator on: [:g | 　1 to: Float infinity do: [:n | 　　(n isDivisibleBy: ((n asString asArray collect: #digitValue) reduce: #*)) 　　　ifTrue: [g yield: n] 　] ]. Zuckerman next: 100 626 名前：デフォルトの名無しさん [2016/08/20(土) 20:32:51.59 ID:vgYTWLvl.net] >>604 Rubyで。 class Zuckerman # @param [Int] num チェック対象数値 # @return [Bool] true:入力値がズッカーマン数, false:ズッカーマン数でない def self.zuckerman num w = num.to_s .split(//) .map {|e|e.to_i} .reduce(:*) w == 0 ? false : num % w == 0 end def self.func1 cnt = 0 (1..Float::INFINITY).map { |e| (cnt += 1; p e) if self.zuckerman e break if cnt >= 100 } end end Zuckerman.func1 627 名前：デフォルトの名無しさん mailto:sage [2016/08/21(日) 01:56:15.80 ID:bS7dpt9A.net] プログラミングのお題で言語間のコード量競うってか いかに数学的アルゴリズムを考えるスレか？ 628 名前：デフォルトの名無しさん mailto:sage [2016/08/21(日) 04:07:51.39 ID://fxd30H.net] 競プロの故郷じゃよ。なんて。 俺算数で解いてるんだぞ・・・。Orz 629 名前：デフォルトの名無しさん mailto:sage [2016/08/21(日) 07:18:31.83 ID:DtQd7MF/.net] 問題を解く早さ、 計算時間の速さ、 コードの短さ、 コードの美しさ、 色々あるね。 630 名前：デフォルトの名無しさん [2016/08/22(月) 00:07:09.67 ID:x59Y2UAa.net] お題 フィボナッチ数列の先頭に近い数字の合計が、入力値になるように求める。 入力値の例--->出力 1 ---> 1 2 ---> 1,1 3 ---> 1,2 4 ---> 1,3 5 ---> 1,1,3 6 ---> 1,2,3 7 ---> 1,1,2,3 8 ---> 1,2,5 631 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 00:37:32.44 ID:RW2M/REU.net] 30人の生徒がいるクラスで、同じ誕生日の子がいる、確立を求めて 1年を365日とする 632 名前：デフォルトの名無しさん [2016/08/22(月) 00:49:12.07 ID:3wW8ItwJ.net] >>619 「確立」は求められないけれど，「確率」なら求められる…というのはさておき， 同じクラスで誕生日が同じ子がいる確率の問題は， 森口繁一『応用数学夜話』 に解説があるのだが，その本が本の山の中に 埋もれていて，いま探し出せないのが残念。 633 名前：618 mailto:sage [2016/08/22(月) 01:14:27.85 ID:RW2M/REU.net] 1 - 全員が異なる誕生日である確率 で求めて 634 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 01:18:50.34 ID:38ySFfYc.net] ideone.com/54J6iS C++。数列に1を含んでいるので、例のようにやろうとすると全部1で分解しようとする。かも。 例がちょっと懇意なので、俺にはこれが限界やったわ。 635 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 01:27:31.25 ID:38ySFfYc.net] >>622　->　>>618 安価忘れた。 636 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 01:53:51.46 ID:38ySFfYc.net] >>619 >>621 ideone.com/BPf9XW C++。確率の問題なんてだーいきらい。あってるか知らんけど大体こんな感じか？ 637 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 02:06:45.94 ID:P8rthkb+.net] >>621を出された時点で理論的確率を求めて欲しいのは明らかだけど、それだとプログラムを組む意味がない 要するにスレチ 638 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 02:15:23.57 ID:38ySFfYc.net] >>625 算数でそれは無理なので、俺には無理だー。 ( ﾟ∀ﾟ)ｱﾊﾊ八八ﾉヽﾉヽﾉヽﾉ ＼ / ＼/ ＼ 639 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 02:31:12.36 ID:ze8O1aG1.net] >>625 いやいや、簡単な数式で表現できても人力で数値解を求めるのは 大変なんだから、それってまさに計算機の出番ではあるよ。 お題として楽しいかどうかは別にしてw 640 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 03:39:29.64 ID:PiS6AnEW.net] >>619 Java https://ideone.com/Qmn3oZ 641 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 03:55:16.97 ID:38ySFfYc.net] あ、勘違いしてた。>>624の結果逆だ・・・。Orz 642 名前：デフォルトの名無しさん [2016/08/22(月) 10:05:22.23 ID:6SPK9Sy9.net] お題 やじろべえの左右の腕に交互に重りを吊るしていく ただし、左右の重りの重量差が10ｇを超えたらバランスを崩してしまう 重りの重量が順に与えられるので最後までバランスを保ったままかどうか判定せよ 643 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 10:32:46.57 ID:38ySFfYc.net] >>630 右と左を引き算してABS取ればいいのはわかるんだけど、重りのサンプル無いかい？ 644 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 18:46:34.40 ID:FFKbVhI+.net] >>618 Common Lisp https://ideone.com/A0NXTP 64個でタイムアウト 遅すぎるよねこれ もっと速く解ける気がするけど分からなかった 645 名前：デフォルトの名無しさん [2016/08/22(月) 19:23:14.70 ID:3wW8ItwJ.net] >>619 森口繁一『応用数学夜話』（ようやく見付けました）によると、この問題は、von Misesとのことです。 結果だけ書くと、ｋ人からなるクラスで誕生日がだれひとりとして同じにならない確率は (1/n^2):*(n!/(n-k)!) で、ｋはひとクラスｊの人数、ｎは場合の数で、閏年を考えなければ n=365となります。 この本によると、この確率が0.5を超えるのは k=23 の時だそうです、つまり24人以上のクラスからなる学校では、 誕生日の重なるクラスが多くなるということになります。 646 名前：デフォルトの名無しさん mailto:sage [2016/08/22(月) 22:39:24.73 ID:RW2M/REU.net] 24人で、0.5を超えるのか。不思議な感覚だな 漏れの感覚では、24人で、0.15ぐらい 647 名前：デフォルトの名無しさん [2016/08/23(火) 00:06:33.47 ID:nbfEIr8Y.net] >>618 DP? C言語 https://paiza.io/projects/NpNLBMGoxV-tDcmm4CycBQ https://out.paiza.io/projects/NpNLBMGoxV-tDcmm4CycBQ/output.txt 648 名前：デフォルトの名無しさん [2016/08/23(火) 00:26:56.57 ID:nbfEIr8Y.net] >>635 出力整形した https://paiza.io/projects/rXzmboNl1gbBZflK_j8BrA https://out.paiza.io/projects/rXzmboNl1gbBZflK_j8BrA/output.txt 649 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 05:09:43.19 ID:1XZ2ZUlZ.net] ideone.com/RLDrpn ベンチマークしようとしたら、先に出力エラーになった。 650 名前：デフォルトの名無しさん [2016/08/23(火) 13:54:31.44 ID:nbfEIr8Y.net] >>637 5,6,7は>>618の結果と違うようだけど 651 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 14:03:36.67 ID:nbfEIr8Y.net] そうかフィボナッチ数列はすぐ大きくなるから項数はそんなに大きくならないからgreedyでもいいのか オーダーのことは未だよく分からないけど たぶんDPよりgreedyのほうがいいのかな？ >>637がgreedyで求めてたので何となくそう思いました 652 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 14:13:51.47 ID:nbfEIr8Y.net] >>639 あ、greedyだから題意を完全に満たさない結果になってるのか やはりメモ化探索か brute forceはキツそうだし 653 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 14:21:20.64 ID:1XZ2ZUlZ.net] >>638 ちょっとよくわからないけど、バグかなぁ。>>635とかできてるしなぁ。 俺が悪かった。忘れてくれ。 654 名前：デフォルトの名無しさん mailto:sage [2016/08/23(火) 14:47:31.03 ID:nbfEIr8Y.net] 自分の解答>>635>>636は題意を満たしてに可能性があるかも 先頭に近い数字という条件を 構成数が最も多くなるうち最初に見つかったものという勝手解釈したが そうじゃなく辞書順的に小さい数を含むほうを選択する必要あるなら構成数が最大になるとは限らないかも 俺も自分の解答>>635>>636を取り下げます 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を求める問題。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef