計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 237 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:08:19 ] 質問なのですが、例えば、 1、２、３、４、５、４０、５０、６０、７０　といった代表値である数字があるとします。 で、例えばXがその代表値のどれに一番近いかを求めるとき すべてを探索すれば答えはわかると思いますが、できるだけ高速に 求めたいと考えたとき、代表地を木にすればいいのではと私は考えました、 例えばXが6だとするとまず、5が一番近いことがわかります これをどうやって木にしたらいいのかがわかりません。 また１，２、３・・・・といっていましたが （X,Y,Z)と三次元に増えた場合、一番近い点を見つけるにはどうしたらいいのでしょう？ 一致するのを探すのではなく一番近いものを探すので苦労しています。 近さの判定としてはユークリッド距離を用います。 どうぞよろしくお願いいたします 238 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:13:08 ] 代表値の数列が整列されている前提ならバイナリサーチでいいのでは？ 239 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:32:56 ] >>238 ありがとうございます。 バイナリサーチですと完全に一致する場合は問題ありませんが 完全に一致せず一番近いものを選択するときに問題がおきます 237の例で6に一番近いものをバイナリサーチで探そうとすると 40になると思われます 240 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:46:58 ] バイナリサーチで最終的に 40 がヒットするわけだけど、 この 40 と X を比較することによって 5 < X < 40 という関係はすぐにわかる。 あとはどちらに近いかを計算するだけじゃないのかな。 241 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 04:54:28 ] >239 最終段でヒットしなかった時、left/rightどちらの方が近いかチェックしろ。 n次の場合は、a=f(X,Y,...)で、aの値でソート。 242 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 05:01:13 ] >>240 >>241 ありがとうございます。 ｎ次の場合はうまくいかないように感じるのですが できれば具体例を出していただけないでしょうか？ 241さんのを自分なりに解釈すると、まずはXについてどれが一番近いか しらべて次はY、Z・・・というふうなことだと感じているのですが 例えばXがかなり近くてもZ,Yがかなり遠いと総合的な距離は遠いわけで Xが多少遠くてもY,Zが近ければ総合的な距離は近くなるので あまりうまくいかなようなきがします。 間違っていたらすみません 243 名前：241 mailto:sage [2005/12/18(日) 05:37:33 ] >242 スマソ、完全に寝ぼけてた。 1次以上の距離で探したいのなら、総当りで検索するしかないんじゃね？ 244 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 05:40:16 ] >>243 ありがとうございます。 総当りですか・・・それですと時間がかかるので 何かいい方法がないかなと思いまして 245 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 07:16:28 ] >>241 ２次元（平面）ならボロノイ図・近傍で似たような問題がある ３次元以上だとできるかどうか知らない 総当りにしたら 246 名前：245 mailto:sage [2005/12/18(日) 07:17:31 ] >>245 の >>241 は >>237 の間違いです ｽﾏｿ 247 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 07:55:24 ] >>245 ありがとうございます。 ボロノイ図については知っていまして、三次元でも可能のようです。 ですが、これをどう木にすればいいのかよくわからなかったもので 何かいい方法があればと思って相談してみました、。 248 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 09:03:12 ] >>237 空間データベースって分野のお話だね． 望んだ形でデータを持ってていいなら，k-d tree を使うのが手軽かな． 空間に一点が追加されるたびに，その一点を通る超平面を引き，その超平面のどちら側に 点があるかで二分木を作る．探索は木を手繰りながら範囲を絞り込んで， その中で全探索をする．最悪 O(n) だけど，適当にばらけてれば O(log n)． ほかにも SR-tree とか SS-tree とか色々あるので，参考になりそうなのを挙げとく： www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html vision.unige.ch/~moennen/publi/moennen_tech0505.pdf H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley 249 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:00:28 ] >>248 ありがとうございます 望んだ形でデータを持っていても大丈夫です。 K−ｄ　tree　についてなのですが、これでは一番近い代表値に近似することはできないと 考えられます。 例えば www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html のｋ−ｄ　ｔｒｅｅ　のところの図で説明しますと 代表地がＰと考えると、Ｐ４とＰ５の線の中に点があるのですがＰ９に 一番近い点（一番近い代表地に近似したい点）があったとすると これはＰ４かＰ５に近似されることになります。 実際はＰ９に一番近いのにこれには近似されないとおいうことです 木を作る際にＰ７からでなくＰ６からはじめたとしても同様の問題はおきると考えられます しかしＲ−ｔｒｅｅというのは使えそうな気がします ちょっと読んでみますがいかんせん説明が少ないので理解できるかわかりませんが なんとかがんばってみます ありがとうございました 250 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:04:36 ] www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html のＲ−ｔｒｅｅを読んでみましたがこれでも正確に一番近い代表地に 近似されないように感じます。 うーんどうしよう 251 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:05:18 ] 一番近い点は一回では求まらないだろう。 　求めた点までの距離を半径とした点で総当りをその後ですればいいだろう。 　たとえば2次元なら　x 座標がその範囲にある条件、次にy座標がその範囲にあるという条件で絞りこんで 　　矩形で絞り込めばいいでしょ 252 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:07:59 ] あと、この問題は、最悪の場合は、全数検索が必要になる。 たとえば円周上に点が並んでいて、中心に近似しようとした場合など 253 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:17:52 ] >>251 >>252 ありがとうございます。 自分の中で何か新しいアイデアが浮かんできそうな気がします が、もう少し具体的にお願いできませんか。何かわかりそうな木がするんです どうかおねがいします 254 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:25:28 ] データ構造として、各母点に、母点を中心に、一番遠いボロノイ点までの距離半径の円内にある 母点までのリンクを距離順に並べて持たせておいて 最初に検索した母点までの距離内にあるリンクだけ全検索する 検索する過程で、それより近い点を見つけたら、母点を移して同じ事をする 255 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 10:35:34 ] >>254 ありがとうございます 私の理解力不足のためわからなかったです　すいませんが もう少し簡単な説明をしていただけないでしょうか　どうかお願いします 256 名前：248 mailto:sage [2005/12/18(日) 10:53:05 ] >>249 二つ目に挙げたテクニカルレポートも読んでね．ちゃんとそっちに作った木から kNN を絞り込む方法について コメントが入ってるから．参考文献にもそれっぽいのが沢山あるので子引き，孫引きしましょう． 257 名前：デフォルトの名無しさん mailto:sage [2005/12/19(月) 09:08:38 ] 長いですが、NP完全について質問です。 アルゴリズムの本に 「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾しているか？ "=Which of the diagrams do not contradict the current state of our knowledge about the complexity classes P, NP, and NPC (NP-complete problems)"」 という質問があってヒントに 「これらのうちの二つのみが現在の私たちの知識と矛盾している "=Just two of them do not contradict the current state of our knowledge about the complexity classes."」とあります。 「私たちの知識」とはその本に載っている 「もしP≠NPなら、PでもNP完全でもないNP問題があるはずだ "=It is known that if P≠NP, there must exist NP problems that neither are in P nor are NP-complete."」 っぽいです。 図は五つあって、そのうち aはP=NP=NPCで、bはNPCがP=NPの部分集合になっており、dはPとNPCが重なった形でNPの部分集合になっており、 これらは明らかに矛盾しているので除外です。 eは↓のサイトにも載っている一般的に知られているベン図ですから矛盾していません。 ttp://www.jyi.org/volumes/volume10/issue2/articles/widjaja.html で問題のcなんですが、これは↑のサイトに載っている図のPとNPCが NPを真っ二つにして占めており、まったく隙間がありません。(想像できますか？) これも矛盾してますよね？PでもNP完全でもないNP問題がないといけないんですから。 そうだとしたらこの本の間違いなんですが…。 ここの賢い人、どうか答えてください。せめてヒントだけでも…。 258 名前：257 mailto:ageで [2005/12/19(月) 09:19:37 ] あまりの必死さに図を描いてしまいます。m(__)m c.　　　　　　　　ＮＰ ┌─────┬─────┐ │　　　　　　　│　　　　　　　　│ │　　　Ｐ　　　│　　ＮＰＣ　　　│ │　　　　　　　│　　　　　　　　│ └─────┴─────┘ てな感じです。 259 名前：257 mailto:sage [2005/12/19(月) 09:23:48 ] 度々すみません。訳し間違えました。正しくは 「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾して『いない』か？」 と 「これらのうちの二つのみが現在の私たちの知識と矛盾して『いない』」 です。もう後で逝ってくるつもりです。m(__)m 260 名前：デフォルトの名無しさん mailto:sage [2005/12/19(月) 10:19:49 ] >>188 すみません 261 名前：デフォルトの名無しさん mailto:sage [2005/12/19(月) 13:34:18 ] >>257 「PでもNP完全でもないNP問題がないといけない」はあくまで「P≠NPならば」 であって、「P≠NP」とは限らない。 262 名前：257 [2005/12/20(火) 12:17:51 ] >>261 ありがとうございます。 なるほど、「P≠NP」とは限りませんよね。 もしそうだとすれば選択肢は「P＝NP」しかない訳で その場合は「PでもNP完全でもないNP問題があろうがなかろうが関係ない」 と解釈してよいのでしょうか？ 友達の一人は「『P＝NP』は『現在の私たちの知識』に矛盾していないか？ 図a, bはP=NPだから簡単に矛盾していると判断できたんじゃないか。 cがP=NPとするなら矛盾していると判断するべきだろう？」と問いかけてきました。うーむ。 すみません、自分、人より脳が少し足りないようです。 また説明お願いします。m(__)m 263 名前：デフォルトの名無しさん mailto:sage [2005/12/20(火) 14:31:12 ] >>262 現在の多くの人たちの『考え』には矛盾しているが、それは『知識』ではない。 P=NPは、我々が馬鹿なだけですべてのNP問題は実は多項式時間で とくことが出来ると言うこと。そんなことはないだろうと思うかもしれないが、 多項式時間で解くことの出来ない問題があることを証明できていない現在、 P=NPは矛盾しているとはいえない。 264 名前：257 mailto:sage [2005/12/21(水) 12:01:14 ] >>263 なるほど、ようやく分かりました。 すべてのNP問題が(近似解とかではなく) 多項式時間で解けるようになったら面白いでしょうね。 天寿を全うするまでに見たいものです。 ありがとうございました！ 265 名前：デフォルトの名無しさん mailto:age [2006/01/09(月) 00:12:14 ] age 266 名前：BASIC mailto:fh [2006/01/09(月) 16:12:52 ] N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい 体重が６０ｋｇ以上で、身長が１５０ｃｍ未満の人の名前を表示する 267 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 17:34:00 ] 宿題は自分でやれ 268 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 17:54:08 ] BASICなんて記憶の彼方だな 269 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 18:15:01 ] 何ベーシックかは指定していないな。 VBとかでもいいとすれば随分アレだ 270 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 19:08:23 ] >>266 www.sagami.ne.jp/tadaka/99Basic/ 271 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 03:29:11 ] ヤコビ行列の計算を効率良く行う工夫は何かあるでしょうか？ (n*m)回の微分演算という時間を喰う処理を少しでも短くしたいです もしくは優れたJacobianMatrixクラスの例をご存じであれば是非！ 272 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 06:49:10 ] Jacobian の成分が nm 個ある以上，本質的にそれよりオーダーが落ちることはありえない． 定数オーダーでの最適化は計算モデルに依存するので議論できん．そもそもおまいが微分をどう実装してるかもわからんし． O(nm) すら許せないなら，問題に応じてアドホックに解決するっきゃ無いと思うがなあ．どんな問題解いてるんだ？ 273 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 10:57:45 ] >271 LZのスライド辞書みたいに、演算した組み合わせを辞書に登録しておいて、 次回以降は演算を省くってのはどうだろう？ 辞書の検索にかかる時間を何らかの方法（連想配列とか）で短縮する必要はあるだろうけど。 274 名前：271 mailto:sage [2006/01/12(木) 12:31:26 ] >>272-273 早いレスどうもです！ >>272 やはりO(nm)回は「本質的に」避けられないわけですよねー・・・ 微分の差分近似をループでnm回やるつまらない実装なんで、 工夫できないかなと思った次第だったのですが。 ちなみに問題は非線形関数の最小値探査みたいな感じです >>273 んー、いいアイディアなんですが今回は 適用できないような気がします、ゴメンナサイ ただ、そのうち他の問題で使えそうな気がするんで、 そのネタはもらって覚えておきます！　ありがとう！ 275 名前：デフォルトの名無しさん mailto:sage [2006/01/14(土) 00:48:34 ] >>274 最小化したい非線型関数になんか条件付けないと定数レベルの最適化もつらいような 276 名前：デフォルトの名無しさん [2006/01/31(火) 17:55:55 ] 最小二乗法のライブラリきぼんゅ。 277 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 03:14:47 ] >>276 ライブラリも何も、大した計算じゃないじゃん。 278 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 12:32:21 ] >>277 世の中に存在するアルゴリズムの中で複雑と言えるものがどれだけある？ 279 名前：276 [2006/02/01(水) 12:44:24 ] 最小二乗法おしえて欲しいぉ。 280 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 13:38:16 ] 残差平方和が最小になるようにパラメータを決定するのです このスレでも簡単な例がいくつか >>178 >>182 >>196 非線形になってくるとちょっとめんどい en.wikipedia.org/wiki/Gauss-Newton_algorithm en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm ここら辺を参考に 281 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 02:20:31 ] >>278 FFTになると、ライブラリが欲しい程度には複雑だと思う。 282 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 08:51:05 ] >>281 どれだけある？という問いにＦＦＴ１個かよ。 283 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 09:25:21 ] >>282 世の中に存在するアルゴリズムがどれくらいあるのか教えてくれたら答えてあげるよ。 284 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 13:43:21 ] 行列計算もだいたい書く気がしないな．条件数が悪い場合とか考え出すと相当面倒くさい． 285 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 14:58:57 ] あとは圧縮＆展開と多倍長演算あたりかね？　汎用的なのは。 各分野毎にはいろいろとあるだろうけど。 画像エフェクト、サウンドエフェクト、3D系演算とか。 286 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 15:52:22 ] >>281 難しくはないが複雑ではあるよな。 287 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 22:26:58 ] 各種関数なんかは、大概簡単なことをやっていても、実装は面倒だなぁ。 288 名前：デフォルトの名無しさん mailto:sage [2006/02/05(日) 09:27:32 ] 最小二乗法は 円に適用するだけでも、厄介だし、 直線に適用しようとしたって、実はけっこう難しいよ。 たとえば、2次元画像から直線部を取りたいとしたら、学校でやるようなXとかYでの偏微分じゃ、それこそ偏る。 　残差って何って所から取り掛からないとね。 そして、余程単純じゃないと、たいていは方程式1発で解けるという事にはならない。 数値解で求める事になるだろうな 289 名前：デフォルトの名無しさん mailto:sage [2006/02/06(月) 07:09:38 ] >>288 ただの偏微分でしか説明しないのって，相当ひどい学校だと思う 290 名前：276 [2006/02/06(月) 10:04:37 ] >>288 じゃ、何を使うのさ？？？？？ >>289 詳しく！！！！！ 291 名前：デフォルトの名無しさん mailto:sage [2006/02/06(月) 14:14:46 ] >>288 最小二乗法はロバストでないのでそのあたりは考慮しないと。 例えば、y=x上に完全に点が並んでいる状態で、 たった一点(1,10000)が入ってきただけでy=2xとかになると困るわけだ。 292 名前：276 [2006/02/06(月) 14:22:51 ] 今回の開発では点の数に関しては、決めウチできます。 293 名前：288 mailto:sage [2006/02/07(火) 06:30:36 ] >>290 だから、最小2乗法を使うなら、何を最小にするのかって所が肝心って事さ 直線を求めるのにしたって、数表上と2次元データとは誤差の意味が違う 数表上なら結果の誤差を最小にしたいし 2次元なら直線からの誤差を最小にすると同時に回転変換で結果が変わらない必要がある 294 名前：デフォルトの名無しさん [2006/02/09(木) 11:57:07 ] 最小2乗法ｱｹﾞ 295 名前：sage mailto:sage [2006/02/09(木) 21:45:42 ] sage 296 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 17:31:27 ] n個の要素の2番目に小さい要素は最悪n+logn−2回の比較で求められることを証明しなさい。 順序統計量を使うのだと思うのですが、帰納法を使って証明するのかどうか分かりません。 どなかか説明してもらえないでしょうか？よろしくお願いします。 高校の時に教師が言っていたんだけど急に思い出して・・・・おねがいします。 297 名前：デフォルトの名無しさん [2006/02/11(土) 18:07:41 ] 　 ／￣￣￣￣＼ ／　　　　 ●　　 ●　 |Y　　Y　　　　　　　　 ＼ | |　　 | 　　　　　　　 ▼　| ﾊﾟｸｯ | ＼／　　　＿＿＿＿人__| |　　　　　　|∨∨∨∨∨　←296 ＼　　　　　＼∧∧　　　） 　｜ ｜　|＼　￣￣＼＼＼ 　｜ ｜　|　　￣￣￣ し し/ 　（_＿）＿） 298 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:33:39 ] 最悪 n - 1じゃないか? 何番目でも最悪 n - 1回でいけそうだ。 今適当に考えただけだから間違ってるかもしれないけど。 299 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:40:59 ] 違った、最悪 n回か。 300 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:45:05 ] >>298 いや、漏れが覚えている限りでは違うと思われ。 MITだかどっかの教科書の奴に載ってた。二番目を求めるけども一番最小を求めてからだったはず 院試にでてたかも。 301 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:57:23 ] >>300 やっぱり違ってた。考え直したら、 nが偶数なら (3/2)*n - 2, 奇数なら (3/2)*n - 3/2 回だった。 302 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 20:58:20 ] >>296 ソートアルゴリズムのところとかかな？学部生の時に必死こいてやったけどもう忘れた・・・。 あの教科書は原書で読んだ方がいいかもしれんな。英語だからかなりめんどくさいが。半期でやるのを英語でやったら一年半かかったよ。 303 名前：デフォルトの名無しさん mailto:sage [2006/02/12(日) 00:24:16 ] 証明になってないｗ 304 名前：デフォルトの名無しさん mailto:sage [2006/02/12(日) 03:01:20 ] >>296 完全二分木でトーナメントを考えよう。 一番小さい要素を見つけるのにn-1回の比較が必要。 二番目に小さい要素は一番小さい要素の対戦相手のどれか。 木の高さはceil(log n)で木の一番上には対戦相手はいないから、 二番目に小さい要素の候補たりえるものはceil(log n)-1個 この中から一番小さいものをみつけるのにceil(log n)-2回の比較が必要。 したがって比較回数は、 (n-1)+ceil(log n)-2<n+logn-2 ただし、ceil(x)はxの小数点以下切り上げの関数 305 名前：デフォルトの名無しさん mailto:sage [2006/02/13(月) 00:39:26 ] >>304 なるほど。 それは比較は少ないけどコピーがメモリが多く必要になりそうなんだけど どうなんだろう。 306 名前：デフォルトの名無しさん mailto:sage [2006/02/13(月) 06:11:40 ] ２分木にする必要性が感じられないってかなってないｗ 307 名前：デフォルトの名無しさん mailto:sage [2006/02/14(火) 10:30:15 ] >>305 実装の話はしてないんだよね。実際にこの比較回数で動くプログラムを作るのは 結構困難な気がするし、普通の 2n 回比較に定数倍で負けそう。 308 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 09:33:06 ] ３２ビットの符号無整数型で３２個のビットのうち N個をランダムに選んで１にするアルゴリズム。 （残りの３２−N個は０） 賢い人教えて。 309 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 11:33:45 ] >>308 そのサイズの乱数を一個生成するだけじゃいかんの？ C なら rand() とかで。 それとも乱数生成のアルゴリズム自体を聞いてるの？ 310 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:12:40 ] たぶん １）組み合わせの数の計算方法が判らない ２）乱数と、その全部の組み合わせを対応させる方法が判らない のだろうと思うんだけどね 311 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:28:33 ] 1U << (rand() & 31) とか、そういうことではないの？ 312 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:35:07 ] >>311 rand って完全にランダムじゃなくて、 下位ビットほど短い周期性持ってるから、 rand() & 31 はあんまりよくない。 (rand() >> 16) & 31 とか、何ビットかシフトするの推奨。 313 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:38:20 ] 分かってて書いてたつもりだけど…アルゴリズムの質問だし。 random()でもMTでも好きなの使えばいいんじゃない？ 314 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:41:56 ] >>313 まあそうだけどね。 >>308 がそんな判断できると思えなかったんで、一応補足のつもり。 315 名前：308 mailto:sage [2006/02/27(月) 13:09:41 ] MTとかで生成された乱数の立っているビットの数は １６本を中心にした正規分布になってると思うんだけど、 必ずN本になるようにしたい。 ３本とか３０本とかってのはたまにしか発生しないし。 N回ループで一度使った数は記憶させとくとかっていう 愚直なのは思いついたんだけど遅そうなので聞いてみた。 316 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 15:31:21 ] 32個の数字から N個取り出して順不同というのと　問題は同じでしょ 317 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 20:50:08 ] >>316 ですね。 1〜32の間で離散一様乱数発生させたものをa_0、 1〜31の間の乱数をa_1、1〜30の間をa_2として、 初期値は0で左からa_0番目のビットを1にする。 以降左からa_k番目の0のビットを1にする。 　　　　　　　　　　　　　~~ 318 名前：308 mailto:sage [2006/02/28(火) 09:54:13 ] >>317 今はそれでやってます。 みなさん聞いてくれてありがとう。 319 名前：308 mailto:sage [2006/02/28(火) 09:58:33 ] あ、ついでに言っとくとNが17以上の場合は32-N個のビットを立てて反転してる。 連投ごめん。 320 名前：308 mailto:sage [2006/03/01(水) 16:40:57 ] やっぱりもっと速いのないかな。 321 名前：デフォルトの名無しさん mailto:sage [2006/03/01(水) 17:19:36 ] >>320 これ以上議論するなら，「速い」をきっちり定義してもらわないと． 特に乱数生成のコスト，各ビットを参照するコストなどが無いと， どっちが速いかなんて比較できんよ． 322 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 11:59:32 ] もっと早い方法は、全部の組み合わせのテーブルを作っておいて それの配列番号を乱数で選ぶ事だね 323 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 12:53:16 ] >>322 2^32 / 2 (0≤N≤16 だから半分) = 2G×4Byte = 8GB 何を使って動かすつもり？ 324 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 16:39:38 ] >>317 それは、順番を考慮した場合のアルゴリズムだから違うようだけど 結果はN個のビットだから、どの組み合わせも等確率で発生するから問題ないのか >>323 Nを固定すれば　最大の組合せ数は N=16の時で その1/4程度の容量だから最近のPCなら入るんじゃないの？ 組み合わせの数ってどの程度だろ？ 32!/N!/2^N では大きすぎるな 325 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 16:43:14 ] たとえば32個中3個が１の組み合わせを F(32,3) のように書くと 先頭ビットが0 なら 残りは F(31,3) 先頭ビットが1 なら 残りは F(31,2) という事で F(N,M)=F(N-1,M)+F(N-1,M-1) 326 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 17:23:15 ] >>324,325 高校数学の教科書読み直したら？ ttp://ja.wikibooks.org/wiki/%E9%AB%98%E7%AD%89%E5%AD%A6%E6%A0%A1%E6%95%B0%E5%AD%A6A_%E5%A0%B4%E5%90%88%E3%81%AE%E6%95%B0%E3%81%A8%E7%A2%BA%E7%8E%87#.E7.B5.84.E3.81.BF.E5.90.88.E3.82.8F.E3.81.9B 327 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 18:34:31 ] という事は 32 C 16 www.google.co.jp/search?q=32!/(16!*16!) 601 080 390 って事か Σ M C n =2^M って事になるんだな 328 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 18:39:51 ] で 32個中16個の組み合わせ　は　32!/(16!*16!) なのに >>317の方法は　 順列　で　32!/16!　という事で、16! の重複があるから、なんか重そうに見えるという事？ 329 名前：デフォルトの名無しさん [2006/03/03(金) 07:29:43 ] 配列のソートではなく、上位2者と下位2者を高速にシークするアルゴリズムを教えて＞＜ 330 名前：デフォルトの名無しさん mailto:sage [2006/03/03(金) 07:50:10 ] var max1,max2 min1,min2; max1:=data[0]; max2:=data[1]; if max2> max1 then swap(max1,max2); min2:=max1; min1:=max2; for i:=low(data)+2 to High(data) do begin 　 if data[i] > max2 then begin 　 　if data[i] > max1 then max1:=data[i] else max2:=data[i]; 　 end; 　 if data[i] < min2 then begin 　 　if data[i] < min1 then min1:=data[i] else min2:=data[i]; 　 end; end; こんな感じでは？ 331 名前：デフォルトの名無しさん mailto:sage [2006/04/18(火) 07:42:35 ] いわゆる○×。ただし、ちょっと特殊。 ban(0) ban(1) ban(2) ban(3) ban(4) ban(5) ban(6) ban(7) ban(8) //盤面　位置関係はこんな感じ turn //ターン数　最初は1 プレイヤーＡのターン開始 ↓ Ａが指定しかつその場所に当たる変数（真ん中ならban(4)）が0であるならばそれに（turn×１０）＋プレイヤーの番号 （Ａは１、Ｂは２とする。）を代入。 ↓ turn>6ならば、次のことを行う。 　banの中で下１桁がプレイヤーの番号と等しいもののなかで、一番小さいものに0を代入 ↓ banに縦横斜めに自分の番号が並んでいるならば勝利 ↓ turnに１を足し、Ａのターンを終了、Ｂのターンになる。 で、できるだけ強いCOMのアルゴリズムを考えてほしいのです。 お願いします。 332 名前：デフォルトの名無しさん mailto:age [2006/04/18(火) 13:54:18 ] あぶらあげ 333 名前：デフォルトの名無しさん mailto:sage [2006/04/22(土) 16:23:12 ] >>331 ゲーム木使って実際に解いてみたら。 EXPTIME完全か知らんが、3×3ぐらいなら解けるだろ。 終盤6個そろってからの場合の数は 9*8*7*6*5*4 = 60480 回転と対称で重なるものを除くと 60480/8 = 7560 リーチがかかってかつ自分の手番のような自明な場面を除けばもっと少なくなる。 自分の手番でダブルリーチをかけられる状態であれば勝ち。 双方最善を尽くしたとき、ループに陥れば引き分け。 334 名前：デフォルトの名無しさん mailto:sage [2006/04/22(土) 17:08:22 ] 消してから勝利判定だとダブルリーチにならないんじゃない？ 335 名前：デフォルトの名無しさん [2006/05/22(月) 17:26:54 ] 楕円近似ライブラリなんてありまつか？ 336 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 17:37:12 ] 楕円近似というのは　 １、点列を楕円の一部として近似する事 ２、楕円の周長を近似計算する事 どっち？１はとても難しい　円ならまだ方法があるが 337 名前：デフォルトの名無しさん [2006/05/22(月) 17:56:27 ] ＞１、点列を楕円の一部として近似する事 これをやりたいです。

---

---

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

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