データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2

1 名前：デフォルトの名無しさん mailto:sage [2013/03/03(日) 18:10:11.63 .net] 【関連スレ】 3Dアルゴリズム全般 toro.2ch.net/test/read.cgi/tech/1164171086/ ＜集大成＞アルゴリズム大辞典 toro.2ch.net/test/read.cgi/tech/1086272325/ アルゴリズム総合スレ in ム板 toro.2ch.net/test/read.cgi/tech/1217773415/ アルゴリズムとデータ構造 - Kaneko Lab. ttp://www.kkaneko.com/adp/algo/index.html アルゴリズムとデータ構造 - ソースコード探険隊 ttp://www.codereading.com/algo_and_ds/ 各種アルゴリズムの C++ による実装 - Spaghetti Source ttp://www.prefield.com/algorithm/ アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP ttp://vipprog.net/wiki/algo_and_data_const.html 384 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 00:30:58.09 ID:/8HFkyur.net] ttp://www.younganimal.com/se/img/02.jpg ttp://www.younganimal.com/se/img/03.jpg ttp://www.younganimal.com/se/img/04.jpg ttp://www.younganimal.com/se/img/05.jpg ttp://www.younganimal.com/se/img/06.jpg ttp://www.younganimal.com/se/img/07.jpg ttp://www.younganimal.com/se/img/08.jpg ttp://www.younganimal.com/se/img/09.jpg ttp://www.younganimal.com/se/img/10.jpg ttp://www.younganimal.com/se/img/11.jpg 385 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 01:21:41.85 ID:LoW5JUMG.net] 続きはよ 386 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 01:23:49.16 ID:tByDu0vN.net] 続き見てきたけど、デザインパターンが分かって書いているとは思えないところがなんとも。 387 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 01:57:49.42 ID:mBc+6kiF.net] 続き読んでないけど、オカマなんか？ 388 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 10:08:06.94 ID:tByDu0vN.net] いや、オナホのソフトを作っている会社の社長。 ハードの話をすっ飛ばしていきなりオナホ界のジョブズだとかw 389 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 11:55:06.72 ID:2wcEJRw7.net] さて、短い旅から帰ってきた 頭からの再帰、明日にでもやろう その前に 頭からとか、末尾からとか 末尾再帰に関わる意味で言ってるんか？ おれは算術式の頭から見ていく という意味で言っていたが それにしてもなんでこんな簡単な問題が！ 初心者の俺は根本的に問題を誤解してるのか？ ま、いいや、明日には書いておく 390 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 14:05:33.54 ID:n8bRVLF6.net] >>389 少なくとも>>377で言ってる末尾は、再帰の話なんて一切してないよ。 単純に数式文字列の最後の文字と言う意味ね。 391 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 20:22:58.60 ID:peygn8xB.net] >>374 課題では中置を逆ポーランドにだったけど、アルゴリズムの都合上、 中置もポーランドも逆ポーランドに変換(無論、逆ポーランドはそのまま) また、各種記法の混在を認める ((1 + (* 3 5)) (8 - 2) (2 5 expt) +) でもよし 方針　式の頭からワンパスで変換を終了する 使用言語　Scheme codepad.org/Ogp2Lzwh 392 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 20:41:37.31 ID:2wcEJRw7.net] >>391 どひゃ！ >>391は変数と演算子を区別していない！ 式の計算ではなく 式の変換だけの課題だった！ もう、変換だけでなく計算してしまう過大なら楽なのに！ （今日は寝る） 393 名前：デフォルトの名無しさん mailto:sage [2014/05/04(日) 20:44:47.52 ID:2wcEJRw7.net] (number? x)のところを (number (eval x ()) )にすりゃいいな 394 名前：デフォルトの名無しさん mailto:sage [2014/05/05(月) 08:05:58.63 ID:wP+UVhzo.net] >>391 式に変数も認めるバージョン 演算子情報はは演算子データベースに保持 codepad.org/c65AyXpd 395 名前：デフォルトの名無しさん mailto:sage [2014/05/05(月) 09:00:44.75 ID:ZPrSoRKy.net] 気持ち悪い 396 名前：デフォルトの名無しさん mailto:sage [2014/05/05(月) 09:23:14.89 ID:wP+UVhzo.net] あはは ゲロはいてろ 397 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 17:36:11.48 ID:SXeDLzrE.net] 再帰プログラムを非再帰プログラムに変換する方法が理解できません。 たとえば、フィボナッチ数列を再帰的に計算するプログラムを スタックを使って非再帰的に計算するプログラムが野崎昭弘さんの 本に載っているのですが、何度読んでも理解できません。 どうすれば理解できるようになりますか？ 398 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 18:03:16.22 ID:lP/gHzU8.net] たまたまそのコードと自分の相性が悪い、といったようなことはあるから、 他の例をさがしてみたら？ 399 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 18:38:21.93 ID:rkx/vo/u.net] >>397 fibonacchi数列の非再帰表現をするにはごく普通にwhileループを使って実現できる f(n) = f(n-2) + f(n-1) のf(n-2)の値を例えば変数prev2に保存し f(n--1)の値を例えば変数prev1に保存すれば f(n) はprev2 + prev1で求められる それを変数ansに格納すれば while ループごとに 　ans = prev2 + prev1 prev2 = prev1 prev1 = ans と更新していけばよい また、f(1)=f(2)=1なのでそれはwhileループで処理しない。逆に f(3)以上の値をwhileループで求めればよい 具体的には、これを見ろ codepad.org/vdi9qyqK 400 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 18:41:31.99 ID:lP/gHzU8.net] フィボナッチを再帰的じゃなく求める方法についてじゃなくて、 再帰的なコードのループへの変換がわからない、ということでしょ。 401 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 18:42:59.47 ID:rkx/vo/u.net] ん？スタックを使いたい？プッシュしてな、いきついたら、ポップするんだよ 402 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:13:51.53 ID:a2G3KqVr.net] >>399 まあ再帰は基本的に遅いけど、メモ化すればずっとマシになるし(震え声) C++で書いてみたサンプル↓ codepad.org/HgtP5slM 403 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:17:07.35 ID:a2G3KqVr.net] >>400 まあフィボナッチは末尾再帰(非再帰型にしやすいもの)の中では定番ですし…… そうでなくてもスタックが使えれば原理的にはなんだって非再帰にできるはずだが ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0 www.math.kobe-u.ac.jp/~taka/asir-book-html/main/node67.html 404 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:34:10.95 ID:6FN1Wxeb.net] >>403 ではAVL木や赤黒木（二色木）を非再帰に書き下ろしてみてくださいな 405 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:38:01.88 ID:a2G3KqVr.net] >>404 「原理的に」つっただろ……なぜお前の代わりにそんな面倒なことする必要がある？ 406 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:39:42.73 ID:6FN1Wxeb.net] >>405 できないのですね 407 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 19:54:10.14 ID:84RD4hek.net] 煽っても何も得られないと思うぞ 408 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 20:11:01.93 ID:6FN1Wxeb.net] ということにしたいのですね 409 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 20:22:30.15 ID:lP/gHzU8.net] CPS変換すればなんでもGOTO 410 名前：デフォルトの名無しさん mailto:sage [2014/05/16(金) 23:21:34.01 ID:irORkSf3.net] 関数呼び出すは引数をスタックに積んでｇｏｔｏしてるんだものな。 411 名前：デフォルトの名無しさん mailto:sage [2014/05/17(土) 13:14:23.25 ID:6fCCnAU/.net] 呼び出した場所の情報もスタックに積まないと戻れないぞ 412 名前：デフォルトの名無しさん mailto:sage [2014/05/17(土) 13:28:37.03 ID:Ml/OqnCm.net] それも引数だと思えばいい。 ていうかCPS変換てのは、戻らない形にするプログラム変換だから。 413 名前：デフォルトの名無しさん mailto:sage [2014/05/17(土) 15:05:44.99 ID:r0DUx653.net] 「継続」だな 引数だけ渡しても再開できるとは限らんから 414 名前：デフォルトの名無しさん mailto:sage [2014/05/18(日) 14:33:40.46 ID:kmKCNCUr.net] 「再開できる」とはスタックは一本しかないことを認めているようなもの 415 名前：デフォルトの名無しさん mailto:sage [2014/05/18(日) 17:10:06.80 ID:Eb7sh+a5.net] アクティベーションフレームはスタックである必要性ないから 416 名前：デフォルトの名無しさん mailto:sage [2014/05/21(水) 11:33:25.46 ID:327eLNTn.net] こっちもよろしく アルゴリズムとデータ構造について語ろう ai.2ch.net/test/read.cgi/math/1379334483/ 417 名前：デフォルトの名無しさん mailto:sage [2014/05/21(水) 15:13:54.42 ID:MlM1D9Ph.net] a=a+1 を解釈する時点で混ぜるな危険 418 名前：デフォルトの名無しさん mailto:sage [2014/05/21(水) 15:48:05.32 ID:327eLNTn.net] とっつきやすいスレはここ。数学板は基本的に過疎なので遊びにきてほしい P vs NP ai.2ch.net/test/read.cgi/math/1344808587/ 419 名前：デフォルトの名無しさん mailto:sage [2014/05/21(水) 16:44:08.38 ID:d423R2AO.net] >>418 呼ぶな 420 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 00:22:21.54 ID:EC+gzOW5.net] >>397 再帰の技法　基本的考え方・アルゴリズム・プログラミング www.amazon.co.jp/dp/4434085972/ この本良いよ。 階乗、フィボナッチ、ハノイあたりから始まって再帰を使った問題を解説している もちろん再帰をループに書き直す考え方とかも入ってる 再帰だけ取り上げてる本ってありそうでなかったけど、苦手な人はこういう本で 一度基礎からちゃんと勉強した方が早道だと思う 421 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 00:24:47.89 ID:g/OODa/4.net] 俺は買わないけど言語は何使ってるの？ アマゾン見てみたが書いてなかったな、使用言語 422 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 00:33:08.26 ID:vwK3Zsni.net] 表紙に書いてあるけど 中身もそれかどうかは不明 423 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 00:39:11.30 ID:jH6wT1ov.net] なか見検索で見た限りは純粋なCだよ でも索引まで入れて140ページちょいって少なすぎないか？ 424 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 00:42:44.47 ID:vwK3Zsni.net] なかみで見れた もうおなかいっぱい 425 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 01:09:20.80 ID:g/OODa/4.net] C言語で再帰の本かい そういうのもあるんだなあ 426 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 02:27:20.02 ID:Viwfu6Pv.net] >>421 そのページの表紙の写真の下にある [この本の中身を閲覧する]をクリックして出てくるサンプルの3ページ目の下から3行あたりに 「この本ではC言語を用いてプログラムを示すことにしますので、読者はC言語の知識があるものとします。」 と書いてあるぞ。 427 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 02:28:45.56 ID:Viwfu6Pv.net] >>426 × サンプルの3ページ目 ○ サンプルの2ページ目 428 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 03:31:35.37 ID:2Sfp9Dnc.net] お前ら何か紹介されるととにかくまずけなしまくるよな 読んでさえいなくても 429 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 06:19:42.11 ID:g/OODa/4.net] >>426 さんくす、見てきた もう、お目目キラキラ一年生のために書きました！って言っていいくらいに丁寧にゼロから書いてる感じだった 「再帰？わかんねえよ」 「再帰の本ってリスプとかだろ？ べらんめえ！こちとら江戸っこでぇ、カッコカッコでコケコッコーじゃ埒が明かねえ！」 とか思うがヒトにはいいかもね (俺は買わないけど) 430 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 06:21:20.87 ID:g/OODa/4.net] (フリックで打ってると誤変換ふえるなあ、慣れなきゃ) 431 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 12:28:18.66 ID:W6i6Hy/C.net] うぜえ 432 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 14:11:02.49 ID:g/OODa/4.net] じゃ、しんでろ 433 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 14:59:53.72 ID:oNallj0q.net] NGNG 434 名前：デフォルトの名無しさん mailto:sage [2014/05/27(火) 20:30:31.87 ID:YRg9mIiY.net] >>428 べつにいいんじゃね、挨拶みたいなもんだよ 毎度のことなんで紹介する方もわかってるでしょ 435 名前：デフォルトの名無しさん mailto:sage [2014/05/28(水) 03:21:51.67 ID:7s/YdHrO.net] >>420 void main() だと？！ 436 名前：デフォルトの名無しさん mailto:sage [2014/05/28(水) 08:32:11.08 ID:O+De570m.net] >>435 VSなら間違ってないから(震え声) それに定説は「void main()な入門書は大概糞」ってだけだし > なお、C/C++の言語そのものの解説ではない書籍、例えば圧縮アルゴリズムに > 関する書籍に void main() のような記述があったとしても、その書籍の有用性とは > 直接関係ないので、大目に見てあげてください。 www.kijineko.co.jp/tech/superstitions/void-main.html 437 名前：デフォルトの名無しさん mailto:sage [2014/05/28(水) 09:59:35.52 ID:o+iely1Y.net] ttp://www.youtube.com/watch?v=FbqCbc7tFZg 総務省、「データサイエンス」力の高い人材の育成進める方針 438 名前：デフォルトの名無しさん mailto:sage [2014/05/28(水) 14:14:56.29 ID:H+u5tE5j.net] 組み込みを長くやっていた人なら void main()とか、無限ループしてmain()から抜けないとか、 日常茶飯事の感覚だろうな。 439 名前：デフォルトの名無しさん mailto:sage [2014/05/28(水) 14:19:38.07 ID:H+u5tE5j.net] gotoも日常茶飯事だな 440 名前：デフォルトの名無しさん mailto:sage [2014/05/31(土) 14:50:19.52 ID:iRT5FyvM.net] 組み込みは"hosted environments"じゃないことが多いからな。 "free standing environments"ならmainは必要ない。ある時の型も任意。 441 名前：デフォルトの名無しさん mailto:sage [2014/05/31(土) 15:06:23.11 ID:jIjiIgN7.net] 437のリンク先の要約をありがとう 442 名前：デフォルトの名無しさん mailto:sage [2014/05/31(土) 16:42:26.70 ID:eTy5fHBW.net] まあ C はオールマイティーだからな‥実装がすべて規格なんて糞食らえ 443 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 05:00:36.21 ID:7RR9zZ5c.net] つまり組み込みプログラマーは知的底辺ということか 444 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 05:01:24.48 ID:7RR9zZ5c.net] 動きゃいい！の匂いがプンプンする 445 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 16:30:01.83 ID:hm+Oq1Eo.net] 実際、動きゃイイよっての多くないか? 単価が高めの案件ほど特にｗ コードレビュー無し。 テスト仕様は徹底的だが 446 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 16:34:24.76 ID:hm+Oq1Eo.net] 高給な現場ほど、なぜかやり方を突っ込まれない。 悪意をもてばやりたい放題出来る。費用も言い値。 まあ悪意はそうそう持ち込めるものじゃないが。 多分STAP細胞の現場もそうだったんだろうな、と想像出来る。 447 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 16:39:58.16 ID:2EOO5SfK.net] 組み込み系のひとのソースは汚いのが多いよ ほんと動けば良いのノリだけで造ってる もちろんまともなひとがいない訳じゃないけどね 448 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 17:35:27.78 ID:zexIr6VF.net] >>447 一番最初のソースがひどいとダメだよね 次からはちょっと変更する工数しかないから、みんな割り切ってそのまま変更 まともな人は黙って or ダメソースをなんとかする工数うんぬんで上司と揉めて辞めてしまう 449 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 17:41:16.64 ID:MmoG7Ddq.net] ハードウェアが仕様通りに動くかどうかわかりません、もしくは仕様ありませんって世界だろ? ソフトウェアも相当部分が使い捨てだよね。完全にスレ違いの話題。 450 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 20:01:38.46 ID:X19dTLG/.net] しょうがない 451 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 20:03:23.97 ID:OmwWZrbT.net] >>449 へ？ハードが完全とはいえんから ソフトも適当でいいっていっるのか？ じゃ、馬鹿だ 452 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 20:04:28.73 ID:OmwWZrbT.net] 組み込み系のニンゲン だめな奴おおすぎ 453 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 20:56:04.36 ID:IYI3/sk2.net] のりじゃ作れんよ、凍死老 454 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 21:13:32.37 ID:JYHVd/sm.net] >>447 組込みに限らず、出来る人は2chなんかに来ないだろ。 455 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 21:14:22.88 ID:hqsmsqu0.net] クロック数単位の動作速度保証組み込んだ高級言語ってあるんかいなとふと思った 456 名前：デフォルトの名無しさん mailto:sage [2014/06/02(月) 21:28:06.44 ID:Evci24oh.net] エミュレータでカウントします。 457 名前：デフォルトの名無しさん mailto:sage [2014/06/03(火) 01:48:47.18 ID:Z4oEYHwK.net] 機能実装の作業がいつのまにかハードの不具合調査になってたり、 結果、ソフトに柔軟でかつ早急な対応が必要になるし。 クラス設計とかやった方がいいのかもしれないが、2の次になるとかそういうことだと思う。 458 名前：デフォルトの名無しさん mailto:sage [2014/06/03(火) 01:52:54.96 ID:Z4oEYHwK.net] 組み込み系は、ハード屋に使いまわされてて気の毒に思うことも多い。 459 名前：デフォルトの名無しさん mailto:sage [2014/06/03(火) 05:21:25.51 ID:5jlmL2lS.net] そりゃハード屋からみりゃ組込み君は奴隷 ハードのために仕事しろ！ だし アプリのためのOSのためのハードじゃないからな 460 名前：デフォルトの名無しさん mailto:sage [2014/06/03(火) 21:15:40.07 ID:wU314ZfN.net] このように、スレ違いであろうと自己憐憫の機会は決して逃さないFW屋であった。 461 名前：デフォルトの名無しさん [2014/06/05(木) 13:01:25.59 ID:TEbe8oH8.net] 整数x, yの範囲内で z個の重複しない乱数を発生させるためのアルゴリズムはどうしますか？ 【例】 x=100, y=200, z=5だと、121, 129, 142, 189, 195みたいなのを返す(当然y-x+1>zである必要がある)。 462 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 13:22:26.50 ID:frJCi6Xi.net] >>461 xからyまでの個数の配列作って乱数でシャッフル 先頭からz個取得 でいいんじゃないの？ 463 名前：デフォルトの名無しさん [2014/06/05(木) 13:30:50.33 ID:TEbe8oH8.net] >>462 シャッフルはオレのプログラミング哲学に反する。 先頭から取得するとどうしてても最初のほうの数が選ばれる確率が高くなるのは避けられない。 464 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 13:40:17.83 ID:XOt4XuJl.net] int a[z]; r=y-x+1; for(i=0;i<z;) { a[i]= x + 乱数生成(r); for(j=0;j<i;j++) { if(a[i]==a[j]) break; i++; } } 465 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 14:01:49.36 ID:frJCi6Xi.net] >>463 >先頭から取得するとどうしてても最初のほうの数が選ばれる確率が高くなるのは避けられない。 根拠は？ z個取得する位置もランダムで選択してもいいんじゃないの 466 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 14:06:43.74 ID:XOt4XuJl.net] 取得位置がランダムならシャッフルする必要ない。 シャッフルする必要なければ配列に入れる必要もない。 選んだ配列のインデックスが重複すれば無視しなければいけないのだから>>464と何ら変わることはない。 467 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 14:27:18.69 ID:frJCi6Xi.net] >>466 配列からz個読み出す初期位置を先頭からズラすって意味なんだけどね 468 名前：デフォルトの名無しさん [2014/06/05(木) 15:40:02.23 ID:hSA2XS33.net] オブジェクト指向は愚かな考え。 peace.2ch.net/test/read.cgi/tech/1393660194/ 469 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 16:22:07.85 ID:XOt4XuJl.net] 例えばFisher-Yatesシャッフルすればコスト少なくいい塩梅にシャッフルできるから、 (と言ってもzでなくy-xのオーダーになるので、 オーダーは変わらないものの>>463よりコスト安になることはない) >>463の懸念もあまり意味は無い。 しかし仮にちゃんとシャッフルできてないのでは?って懸念を認めるとすると、 最初の方だけ偏りがあるという変なシャッフルをしない限り、 どこから取っても偏りがあることには変わりない。 そういうわけなんで>>465は修正案の部分がおかしい。 「根拠は?」のところはいいんだけど、良いシャッフルアルゴリズムを挙げられればもっと良かった。 470 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 16:55:24.44 ID:jEZV0Sf8.net] >>461 こんなかんじかな。 先頭から、それぞれが選ばれる確率をきちんと設定して、 すべて等確率になるようになってる……はず。 検定は自分でやってくれ。 void choose(int x, int y, int z) { int i; int n = z; int d = (y-x+1); for (i = x; i <= y; i++) { if (n/d の確率で真) { printf("%d ", i); n--; } d--; } } 471 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 17:03:39.05 ID:jEZV0Sf8.net] あ、すまん。ぜんぜんちがった。 忘れてくれ。 472 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 17:09:28.41 ID:frJCi6Xi.net] >>469 xとyに大きな隔たり、つまり配列が大きい場合、最終的にz個取り出す位置にもランダム性があれば よりランダム性のあるz個の列を何度も取り出せるって意味合い程度だよ、思いつきだよ シャッフルでありがちな実装ってこんなんかな 乱数生成エンジンが質の良い物ならこんなんでいいと思うけどね int size = 10; int a[size] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; for(int i=size-1; i>0;i--) { int j = rand()%i; swap(a[i], a[j]); } 473 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 17:19:32.12 ID:jEZV0Sf8.net] >>461 こうだ。 dCn はコンビネーションな。d!/(n!(d-n)!) のこと。 void choose(int x, int y, int z) { int i; int n = z; int d = (y-x+1); for (i = x; i <= y; i++) { if ( (d-1)C(n-1) / dCn の確率で真) { printf("%d ", i); n--; } d--; } } 474 名前：デフォルトの名無しさん mailto:sage [2014/06/05(木) 21:11:11.97 ID:C2lCmQ2j.net] >>461 一応突っ込んでおくと、それを乱数とは言わない。 乱数を加工して得られる数列。 475 名前：デフォルトの名無しさん mailto:sage [2014/06/06(金) 02:53:59.42 ID:cO/jAhvR.net] １−１００の乱数で、重複しない乱数って重複が許されている乱数より、より 乱数じゃないよね。だって、後の方になるほど次に出る数に制限があって予想が つくわけだし。 99個目の次は100％当てられる そんなの乱数って呼んで良いの？　数学的に。 476 名前：デフォルトの名無しさん mailto:sage [2014/06/06(金) 08:45:46.74 ID:lrmBy0jf.net] 乱数として考えるのは「幾つかの数からなる集合」としてであって、 「集合に含まれる個々の数」では無いのだが。 さっきから馬鹿なこと言い続けてる奴がいるな。 477 名前：デフォルトの名無しさん mailto:sage [2014/06/06(金) 09:08:36.98 ID:F77g5hNR.net] >>476 それは乱択 478 名前：デフォルトの名無しさん mailto:sage [2014/06/06(金) 09:09:56.94 ID:DTdJKogB.net] >>475 そうだよ それは乱数じゃないよ 479 名前：デフォルトの名無しさん mailto:sage [2014/06/07(土) 02:24:09.38 ID:RWltX+Oe.net] 順列の集合から1個をランダムに取り出すんだと解釈すれば乱数やね >462の設問は言葉足らずかもしれないが、意図は通じるでしょ 480 名前：デフォルトの名無しさん mailto:sage [2014/06/07(土) 07:07:52.13 ID:SxbAzKvi.net] N回目の試行がN+1回目の試行に影響を及ぼしてはいけない >>461 は ambiguous だから知らんが >>475 は乱数ではない >>479 は 順列の集合から1個をランダムに取り出す の後で1個をもとに戻せばよい 481 名前：デフォルトの名無しさん mailto:sage [2014/06/07(土) 11:56:57.57 ID:kpprM5q6.net] >>480 その定義だと、線形合同法は乱数じゃなくなるね。 線形合同法を禁止するわけにはいかないのだろうか。 482 名前：デフォルトの名無しさん mailto:sage [2014/06/07(土) 12:05:27.70 ID:u3dUy4Sv.net] 影響って言葉の意味がズレてる。 「箱の中から1個取り出して元に戻さない」方式の場合は、取り出す前は 1/N の確率だったものが、 1/(N-1) の確率に変化してしまう、ということを言っている。 決定的である、という意味では、線形合同法に限らず、真の乱数でない、あらゆる疑似乱数が 決定的だから、線形合同法だけ槍玉に上げるのはおかしい。 483 名前：デフォルトの名無しさん mailto:sage [2014/06/07(土) 12:25:19.08 ID:GAICIAD/.net] 馬鹿な476の話題を引きずらなくて良いよ 484 名前：デフォルトの名無しさん mailto:sage [2014/06/07(土) 12:28:22.09 ID:kpprM5q6.net] >>481 線形合同法はN回目に取り出された物がN+x回目(xは1から周期の長さ)に取り出される確率は0じゃん。 線形合同法は「箱の中から1個取り出して元に戻さない」方式だよ。 481=483だとすると主張がよく分からない。

---

---

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

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