＜集大成＞アルゴリズム大辞典

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18] どこにもない強固なスレにしたい 445 名前：443 mailto:sage [2008/08/29(金) 07:05:54 ] >>444 まさに理想形です。 可能な範囲で助言をいただけると嬉しいです。 今更かもしれませんが、補足 中心から方向Xに距離Rで配置すると中心の密度が上がってしまうので困ってます。 446 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 07:29:24 ] >>445 方向X、円周からの距離Rの片側正規分布で一定以上は切ればいい希ガス。 447 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 08:51:36 ] 偏角は一様分布で出して、 中心からの距離を、 一様分布に対して 1/r かけたもので作れば r に比例した分布になる。 1/r^2 とかかけとけば 442 みたいな分布になると思う。 448 名前：デフォルトの名無しさん mailto:sage [2008/08/29(金) 10:02:34 ] >>443 x=乱数; y=乱数; if(x*x+y*y<r*r) 点を打つ; 449 名前：443 mailto:sage [2008/08/29(金) 11:38:57 ] みなさんありがとうございます。 乱数は一様乱数しか知らなかったので、正規乱数を使う事で解決しました。 ありがとうございました。 450 名前：デフォルトの名無しさん mailto:sage [2008/08/30(土) 07:10:18 ] piece tableのサンプルコード等ありませんでしょうか 451 名前：デフォルトの名無しさん [2008/09/02(火) 14:25:43 ] データベース等に詳しい方教えてください。 B+木を実装する際に、ページに複数のエントリを入れる場合、 ページにできるだけたくさんエントリを入れようとすると、 空間効率は上がるが、木がバランスされなくなると思うのですが、 実際はどのような実装するのが普通なのでしょうか？ ページに入れるエントリ数を固定するのでしょうか？ （その場合は、エントリのサイズが小さい場合は、空間効率が悪くなるし、 大きい場合は、１ページに入らないといった問題がおきて、 実装がややこしくなりそうと思っています。） 452 名前：デフォルトの名無しさん [2008/09/02(火) 14:32:31 ] 451です。 一般的には、 次数を d としたとき、d <= m <= 2 d となるような m が各ノードのエントリ数となる ということは理解していますが、 エントリのサイズが可変の場合は、最大2d個のエントリをどう格納するのかが よくわかっていません。 * ページサイズを可変にする * ページサイズは固定で、入りきらない場合は複数のページを使う この辺があると思っています。 453 名前：デフォルトの名無しさん mailto:sage [2008/09/03(水) 20:16:03 ] ページに入るエントリ数は固定。 バランスされなくなるって、ノードの兄弟を見ながら 2dに収まるように分割してくんだよ。 ほとんど理解できてないみたいだから より単純なB木から学んだ方がいい。 454 名前：デフォルトの名無しさん [2008/09/16(火) 18:38:15 ] ４つの都市A、B、C、Dのそれぞれの距離がわかっている状態で、 xy平面上に正しくA、B、C、Dを配置したいのですが考え方がわかりません。 アドバイスをいただけないでしょうか？ 455 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 19:12:08 ] 回転どうすんだ 456 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 21:57:19 ] >>454 三角関数 457 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 22:07:09 ] >>454 回転が確定しなくていいなら、相対測位とかいうキーワードでぐぐれ。 458 名前：454 [2008/09/17(水) 16:07:09 ] 455様、456様、457様返信ありがとうございます。 余弦定理を用いて半径ACと半径BCの円の交点を考えC点を導いたのですが 次のD点を考えるときに半径AD・BD・CDの円が（当たり前かもしれませんが）１点で交わらないので求められませんでした。 455様と457様が言っている「回転」が必要だなと思い、 B点をA点のまわりで距離ABを保ちつつグルグル回るようにしたのですが、どうも違うみたいで困ってしまいました。 回転についての詳しい説明を教えていただけないでしょうか？ 今は下のような状態になっています。 ttp://www.dotup.org/uploda/www.dotup.org0494.png 赤・青の円は半径AC・BCの円でC点（黄緑）を求めました。 薄い赤・青・緑の円は半径AD・BD・CDの円でとりあえず円AD・BDの交点から仮のD（紫)を導いたところです。 よろしくお願いします。 459 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 17:00:27 ] ４点が平面上にないだけじゃないの？ 分かりやすい座標で１回やってみた方がよさげ。 460 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 22:38:41 ] 3点の位置が決まって距離もわかってて4点目が交わらないってあるのかな？ 各点間の距離データはあってるんだよね？？ 461 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 00:59:48 ] 現実の都市間の距離だったりして・・・ とはいえその場合でも、対称を同一視すれば一意に求まるはず。 462 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 02:23:10 ] >>459,461 そ れ だ。 現実の都市間の距離で、球面上には矛盾無く配置できるけど平面上では矛盾無く配置できないとかな。 とりあえず454はそれぞれの距離を提示するべき。 463 名前：454 [2008/09/18(木) 14:11:16 ] 459様、460様、461様、462様返信ありがとうございます。 まず都市ABCDが現実に存在する都市かどうかですが、この世に存在しない都市を仮定しています。 そのため距離は毎回乱数で定まっています。 最初に断わっておくべきでした申し訳ないです。 4点が同一平面上にない場合があることは考えていませんでした。 今回の考え方を元に、単語同士の非関連度を距離に置き換えてそれぞれを配置するプログラムを作ろうかと思っていたのですが、 平面上のみで考えるのは無理があるのでしょうか。 464 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 14:40:44 ] 4点をa,b,c,d、それらの間の距離6つをab,ac,ad,bc,bd,cdと書くことにする。 距離を何の制約も無しに乱数で作ると、それは4点間の距離と言えないものもできてしまう。 a,b,cで三角形になるのだから、ab+bc>acなどの制約が必要。 a,b,c、a,b,d、a,c,d、b,c,dの各組が三角形になる制約を満たすなら、 4つの点a,b,c,dは4面体を作る。 465 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 17:25:13 ] 何点あっても、二点間の間での距離だけを定義すればうまくいくんじゃね？ 完全ランダムでは無理条件ができるけど 466 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 20:06:30 ] >>465 > 二点間の間での距離だけを定義する という意味がわからないけれど， 『任意の二点間で三角不等式が成立するならば実現可能」 という主張なら，4点で反例が構成できる： d(12) = 1, d(13) = √5, d(14) = √2, d(23) = 2, d(24) = 1, d(34) = 1 467 名前：デフォルトの名無しさん mailto:sage [2008/09/18(木) 20:25:51 ] これは非常に有名な問題（グラフ実現可能問題）． 以下の事実が知られている． 定義： n×n 行列 D = (d_ij) が EDM であるとは， ある点 p_1, ..., p_n ∈ R^k が存在して， d_ij = |p_i - p_j|^2 が成立することをいう． k を D の埋め込み次元という． I を単位行列，J をすべての成分が 1 の行列とする． 定理(Schoenberg, Young-Householder)： 対称かつ対角成分がゼロの非負行列 D が EDM であることと， G := -V D V / 2 が半正定値であることが同値． ただし V = I - J/n である． また，G = X X^T を コレスキー分解としたとき， X の列ベクトルは D の実現となる． なので，与えられたデータから行列 D を構成して G を計算してコレスキー分解すれば埋め込みが決定できる． もし rank G > 2 だったら平面には埋め込めない． 詳しくはEuclidean Distance Matrixなどで検索してくれ． 468 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 00:48:36 ] 質問させて頂きます。 XY平面上に、その座標データを保持するオブジェクトが複数個あり、 それらの座標はそれぞれランダムだったとします。 それぞれのオブジェクト間の距離が一定以下の場合は、 一定距離の間隔を置けるように引き離し、 さらにオブジェクトの距離の一番近いオブジェクトを探す というようなことをしたいのです。 この処理はリアルタイムループ内で実行するので、 引き離しは1距離だけ離れるだけで十分であるとします。 一応は下記のようなプログラムで実装は出来ているのですが、 オブジェクトの数が増えた場合に処理が急激に重くなります。 この処理の計算量がn^2であるので、 オブジェクトの数が100、200と増えていった場合には とてもリアルタイムループでは遅すぎる速度になってしまうのです。 何とかしてこの計算量を減らす方法はないものでしょうか？ 469 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 00:50:56 ] >>468 簡略 #define n 200 struct Object { 　　double x, y; 　　int near; } op[n]; double dx, dy, dr, drmin; for(int i = 0; i < n; i++) { 　　drmin = 1000000; //とりあえず大きい数 　　for(int j = 0; j < n; j++) { 　　　　dx = op[i].x - op[j].x; 　　　　dy = op[i].y - op[j].y; 　　　　dr = sqrt(dx * dx + dy * dy); 　　　　//一番近いオブジェクトを探す 　　　　if (dr <= drmin) { 　　　　　　 op[i].near = j; 　　　　　　 drmin = dr; 　　　　} 　　　　//一定距離以内の場合は引き離す 　　　　if (dr <= 400) { 　　　　　　op[i].x += dx / dr; 　　　　　　op[i].y += dy / dr; 　　　　　　op[j].x -= dx / dr; 　　　　　　op[j].y -= dy / dr; 　　　　} 　　} } 470 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 01:27:09 ] >>468 動的ボロノイ図を使えば，一反復が O(n + k log n) でできる． ただし k は引き離す必要のあるペアの数． ただ，これは実装が結構しんどいので，現実的には x 座標でソートしたリストを盛っておいて，x 座標の近い順に見て 枝刈りするのが有力だと思う （x 座標が一定距離を超えたら，距離が一定距離以下にはならない等） 計算量は最悪 O(n^2) だから変わってないけれど，現実的には改善されるはず． なお，ソートは最初の一回だけ行えば，あとは引き離したところだけ更新すると 多少の効率化ができる． 471 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 19:43:55 ] >>470 動的ボロノイ図は調べてみましたがサッパリ理解できませんでした（汗 なので後者のソートして近いところから探す方法を試してみたところ、 オブジェクト800個くらいまでは実用レベルの速度で動くようになりました。 但しやはり位置関係によっては重くなることもあり、 必ずしも安定しているとは言えませんが、 総当りに比べれば桁違いの速度になりました。 ありがとうございました。 472 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 23:01:01 ] 「一定距離」の間隔でマス目に区切って、マス目毎にデータをコレクションで持ち、 引き離し処理をするときには、データとその周囲の9マス分の範囲だけ調べるとか。 □□□□□ □■■■□ □■▲■□ ←▲のところが自分の属すマス □■■■□ □□□□□ データの散らばってる範囲が狭過ぎると密集して役に立たないし、 逆に広過ぎるとマス目の管理を工夫する必要があるけど。 あと、「一定距離」以上でも最も近い点を取得する必要があるなら、これじゃだめかも。 473 名前：デフォルトの名無しさん mailto:sage [2008/09/19(金) 23:06:33 ] ヒューリスティックだけど、自己組織化で適当に動かしてみるとか。 474 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 11:26:32 ] すまん、図形描画アプリみたいなものを作ってるんだが･･･ 次のようなもので悩んでます。 １．複数の矩形があるときに同じところを再描画しないように無駄なく描画する矩形を計算するにはどうしたらいいか? 場合によっては複数矩形を包含する矩形で一度に描画した方がいい場合も含む。 総当たり以外でエレガントな方法というとどんなんざんしょ? ２．同じような話なのかもしれんが、矩形と線分(曲線含む)が混在してる場合で描画する矩形にかかる部分だけの線分を描画する効率のいい方法。 教えてエロイ人･･･ 475 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 12:15:00 ] メモリが許せば、思い切って座標にオブジェクトを持たせるとか。 476 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 12:15:42 ] >>475は>>468にです。 477 名前：468 mailto:sage [2008/09/20(土) 18:05:06 ] お返事ありがとうございます。 >>472 空間分割とかいうやつですかね？ しかしこれは「最も近い点を取得する」という場合に やはりお察しのように問題がありまして、 結局こちらの方法は諦めたのであります。 一応この最も近い点を探す距離も制限されてはいるのですが、 結構範囲が広いのでその表現は省かせていただきました。 >>475 これはその空間分割の究極ですね・・・ しかしこれはまた違う方向で膨大な判定量になりそうな気がします。 478 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 19:00:54 ] >>477 472の亜種だと思うけどＸ，Ｙ軸上でソートして、各軸上の分布をクラスタとして扱うっていうのがGameProgrammingGEMに載っていた。 479 名前：デフォルトの名無しさん mailto:sage [2008/09/20(土) 21:40:57 ] >>474 問題が明確じゃないのだけれど， (1) 『描画する』条件は，単に『別の矩形に包含されないこと』でよい？ それとも，矩形間に上下関係（例: Windowsのウインドウ）がある？ (2) 『描画する』条件は (1) と共通ということでよい？ それと，曲線はどのような形で与えられる？（例：ベジエ曲線） 何にせよ平面走査型のアルゴリズムが有力に動くと思う． 480 名前：デフォルトの名無しさん mailto:sage [2008/09/21(日) 11:23:34 ] ナップサック問題とは、価値と重量があるものを、入れられる重量に制限がある箱に 一番価値が高くなるように効率よくいれるにはどういれたらよいかの手順を考える問 題ですよね。 これに、価値が高くなることに加えて、入れる順番も重さがあるものから入れる、あるいは 軽い順に入れるなどの制限が加わった場合にどのようにすればよいかという解法は 存在しますか？ 481 名前：デフォルトの名無しさん mailto:sage [2008/09/21(日) 11:59:36 ] >>480 入れるものを決めた後で重量でソートすればいい 482 名前：474 mailto:sage [2008/09/21(日) 12:35:56 ] >>479 不明確ですいません･･･orz 1．矩形間に上下関係有りです。ただその辺含めてまとめて”無駄な矩形を省く”というかたちでまとめられないかと。 ２．描画の段階ではパラメトリック曲線から計算された連続した直線になると仮定しています。 平面走査型ちょっくらぐぐってきます。 483 名前：デフォルトの名無しさん mailto:sage [2008/09/22(月) 00:32:18 ] >>481 書くべき事がたりませんでした。。。 では更に、例えば前に入れたものよりn単位以上軽いものは配置してはいけない というような、ソート後にだめだという事がわかってしまう場合はどうでしょうか？ 484 名前：デフォルトの名無しさん mailto:sage [2008/09/22(月) 02:43:01 ] DP使うしかないんじゃない？ 485 名前：デフォルトの名無しさん mailto:sage [2008/09/23(火) 09:49:23 ] >>480 状態を (現在の重さ，最後に入れた重さ，現在の価値) という三つ組みで持つ． 重さが自然数であれば，品数を n，重さの最大値を W としたとき 普通の動的計画法に基づく O(n W) アルゴリズムを修正すれば O(n^2 W) のアルゴリズムが簡単に作れる． 重さが実数であれば，基本的には枝刈り探索しかないのだから， 上の三つ組みを持って適当に探索する． 本気を出すなら，品数や重さなどによって適切な探索法が変わるけど そこまでがんばるかい？ 486 名前：デフォルトの名無しさん mailto:sage [2008/09/23(火) 11:07:05 ] >>482 もうググって見つけたかもしれないけれど， 1 に関しては平面走査型アルゴリズム（plane sweeping）が考えられる： ・y 軸に平行な直線を考える（走査線と呼ぶ） ・走査線を x = -∞ → +∞ に移動させていく． ・走査線に新たな矩形が乗ったら走査線上の矩形とだけ描画判定を行う． 走査線は y 座標でソートされた二分探索木を用いると， 描画判定を行うべき矩形を O(log n + k) 程度で列挙できる． 二分探索木を管理するのが面倒ならリストで持ってもよいが， これだと列挙に O(n) かかる． （矩形がそれなりに散らばっていれば，現実的には相当改善する） こういうのは「線分交差列挙」などで調べると参考になると思う． ちなみに矩形が動的に増えたり減ったりするような状況設定なら， 空間分割木などの幾何データ構造を使うことになる． 2 に関しては，描画の段階でなくて，データの段階でどうなるかが問題． もしデータの段階で「連続した線分の集まり」と思ってよいなら， 1 の平面操作型アルゴリズムに走査線に線分が交わったら云々を追加するだけ． それがダメなら，扱う曲線のデータ構造が分からないと，どうしようもない． たとえば『曲線の方程式 (x(t), y(t)) が与えられる』くらいだと， 曲線と矩形の交差を全チェックするしかない． 487 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 01:27:20 ] ポリオミノ自動生成アルゴリズムって、起点を中心にどんどん成長させていって、 それぞれ検証する意外に、もっと早そうな根本から違うアルゴリズムって有るかな。 488 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 19:54:18 ] 自動生成って何？ 指定したサイズのもの全てとか、小さい順とかで列挙すること？ それとも、条件を満たすもののサンプリング？ 489 名前：デフォルトの名無しさん mailto:sage [2008/09/25(木) 21:02:22 ] nの数を与えて、その全パターンを出すアルゴリズムです。 n=7なら、108通り全部とか。 490 名前：デフォルトの名無しさん [2008/10/19(日) 01:32:31 ] あげ 491 名前：デフォルトの名無しさん [2009/01/18(日) 20:54:29 ] age 492 名前：デフォルトの名無しさん [2009/01/19(月) 19:28:43 ] 良スレの予感 493 名前：デフォルトの名無しさん [2009/01/19(月) 23:10:09 ] DBMについて興味があり、最近書籍やウェブなどをあたっていました。 B-Treeなどのアルゴリズムについてなんとなく理解したのですが、 それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。 C言語で実装されているソースの解説などどこかにあるでしょうか。 もう少し実力があればTokyoCabinetなどを解析すればよいのでしょうが、 ちょっと敷居が高いです。 494 名前：デフォルトの名無しさん mailto:sage [2009/01/20(火) 01:02:00 ] いきなりF1に乗ろうとする奴っているよね。 495 名前：デフォルトの名無しさん mailto:sage [2009/03/03(火) 06:57:31 ] >>493 >それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。 互換性が要らないならバイナリでダンプしてもいいし、サイズを優先してバイナリで writeしてもいい。互換性を重視するならテキストでwriteするといい。 速度を優先するならseekしたほうがいい。言語によってはシリアライズ機構がある。 よく分かっただろう？ 496 名前：デフォルトの名無しさん mailto:sage [2009/03/03(火) 08:09:55 ] >>493 自分で実装したC#のソースなら持ってるけど 497 名前：デフォルトの名無しさん mailto:sage [2009/03/04(水) 18:34:35 ] そのseekってなんのこと？ 498 名前：デフォルトの名無しさん mailto:sage [2009/03/05(木) 06:32:12 ] 速いライブラリを自分で探せってこった。 499 名前：デフォルトの名無しさん [2009/03/20(金) 20:01:14 ] 499 500 名前：デフォルトの名無しさん mailto:sage [2009/03/20(金) 20:56:21 ] 500 501 名前：デフォルトの名無しさん mailto:sage [2009/03/20(金) 21:16:26 ] >>493 ISAM 502 名前：デフォルトの名無しさん [2009/03/20(金) 23:09:41 ] page4.auctions.yahoo.co.jp/jp/auction/d91264064 503 名前：デフォルトの名無しさん mailto:sage [2009/04/01(水) 00:32:52 ] 多角形の頂点の座標が配列で与えられている時に その図形の重心を求めるアルゴリズムを教えてください。 頂点の数は３以上。 全ての辺について、他の辺と交差することは無い。 一つの角の大きさは0〜360度。 504 名前：デフォルトの名無しさん mailto:sage [2009/04/01(水) 00:43:45 ] 三角形の場合なら公式かなんかあったんだっけ？重心って。 多角形の場合は、三角形に分割して、 それぞれの重心に対して、面積で重み付けして相加平均かな。 505 名前：デフォルトの名無しさん mailto:sage [2009/04/01(水) 00:58:49 ] 504で十分だけど、以下も参考になるかもしれない。 oshiete1.goo.ne.jp/qa4821139.html 506 名前：デフォルトの名無しさん mailto:sage [2009/04/01(水) 01:09:53 ] >>504-505 これで先に進めそうです。 ありがとうございました。 507 名前：デフォルトの名無しさん mailto:sage [2009/04/08(水) 10:28:33 ] ははは 508 名前：デフォルトの名無しさん [2009/06/21(日) 20:30:51 ] 漏れはアルゴリズム考えてると頭痛がしてくるからブルートフォースでいいやと思ってたけど 百万個を20ステップでバイナリサーチするlog nの威力を前にしてあっさり宗旨替えしたｗ 509 名前：デフォルトの名無しさん mailto:sage [2009/06/21(日) 21:06:10 ] バルバロイもそうやって教化されていくんだな 510 名前：（ナワバリ付き）グループ内問題なら処理を軽くする法 mailto:sage [2009/06/21(日) 21:48:11 ] >>468　見てとっさに「過密ストレス指標」と 「指標が高い奴は低い奴に八つ当たりOK」 っていう移動対象絞り込み方が浮かんだ… 特定対象ばかりが連続移動を避けたい時？ 　実際には、完全独立自由主義でなければ 　ご近所さんグループで扱う方がいいかな グループ内成員どうしが比較的接近してて 他のグループの成員とは離れている場合 「外」への移動を好ませればいいのかな 平面なら上が第一候補、ダメなら右など 優先でダメなら時計回りに選択肢変更 一通り計算後グループ内を一斉移動 明確なグループがなければ初期座標で分類 以降はそれに従う（大きな変動がなければ） 通信などによって掛かる時間が移動させる 対象の個数そのものならこんな感じかな？ 　均等に散らばってれば走査線が一番？ 　研究・ライブラリ等充実してるようだし (「MMORPGのアイテムやPCの移動じゃないんだから…w」 ※身内や同画面内の都合なら移動もガマンしてくれる等 511 名前：デフォルトの名無しさん mailto:sage [2009/06/22(月) 23:33:24 ] そうは言うけど、ソートしとかないと駄目じゃん。 ソートのステップ数も入れて考えられた？ 512 名前：デフォルトの名無しさん [2009/07/27(月) 18:33:04 ] あげ 513 名前：デフォルトの名無しさん mailto:sage [2009/07/27(月) 21:07:38 ] COSS age。今年は東工大でやってるわけだが、参加してる人はいるかい。 514 名前：デフォルトの名無しさん [2009/07/29(水) 07:01:46 ] 素数をぷりぷり生成し続けるアルゴリズムを教えて下さい 515 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 07:07:20 ] つ[エラトステネスの篩] 516 名前：デフォルトの名無しさん [2009/07/29(水) 07:15:13 ] 2 3 5 7 9 11 13 ..ってプリプリ垂れるんですよ だとしてもエラトスに帰着されるのですか？ 517 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 09:05:55 ] >>516 「ぷりぷり生成」の意味が曖昧。 518 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 09:17:27 ] www.nicovideo.jp/watch/sm7061127 519 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 12:23:11 ] 一般的に次の素数を求める方法、というのは存在しない。 したがって、（最初の2を別として）奇数を順に生成して、それを ふるいにかけるという方法しかない。 520 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 12:42:47 ] >>519 > 一般的に次の素数を求める方法、というのは存在しない。 マジ？詳しく教えて 521 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 13:25:07 ] >>517 2 からスタートして永遠に次に大きい素数を吐き出し続ける事とします 522 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 14:38:46 ] >>521 メモリは無限にあるとしてよいならば試し割りなり篩なりで十分。 高々有限ならば、不可能。 523 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 15:18:33 ] >>522 無理しなくていいよ たまには素直になろうね 524 名前：デフォルトの名無しさん [2009/07/29(水) 16:11:26 ] なに上のレス？おつむおかしい人？ >>516のように2,3,5,7,9,11,13とぷりぷりたれるだけなら、 a[0]=2,a[1]=3,a[n+1]=a[n]+2で十分だろ 9を素数だと思ってんだしさ このテの人はどうせめちゃくちゃ大きい素数なんて出力させないんだし、 試し割りでも採用してればいいだろｗ 525 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 16:19:43 ] これは酷い 526 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 16:39:48 ] 馬鹿にしないで下さい＞＜ 527 名前：デフォルトの名無しさん [2009/07/29(水) 17:28:28 ] long a[100000],al=0;for(long i=2;i<200;i++)for(long j=0;(j<al && a[j]*a[j]<=i)?i%a[j++]!=0:0==printf("%d : %d\n",al,a[al++]=i);); これで200個ぷりぷりでます これ以上圧縮してかけなかったｗ 528 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 18:34:01 ] ぐぐったもの。動作確認はしていない。 x[1<<15],w=1200,p,r;main(s){for(;++s<w;)for(x[p+=r==1]=r=s;s%--r;);} 529 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 19:31:03 ] 毎回エラトスするよりも 素数はメモライズしていった方が速いわけですね でもこのやり方はメモリも無尽蔵に使うということですかね 530 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 19:59:53 ] FOR N=1 TO 12251:PRINT PRM(N):NEXT 531 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 20:46:49 ] そういえば、一つ前の素数を返すアルゴリズムはみつかってたような気がするな 確かwikiで見たが、思い出せん 532 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 20:54:28 ] 一つ前の素数じゃなかったし、まだ証明されてなかった(フォーチュン予想) これとは別に、wikiに解が素数となる式が載ってるね 常人には理解不能だわ wz + h + j ? q = 0 (gk + 2g + k + 1)(h + j) + h ? z = 0 (16k + 1)3(k + 2)(n + 1)2 + 1 ? f2 = 0 2n + p + q + z ? e = 0 e3(e + 2)(a + 1)2 + 1 ? o2 = 0 (a2 ? 1)y2 + 1 ? x2 = 0 16r2y4(a2 ? 1) + 1 ? u2 = 0 n + l + v ? y = 0 (a2 ? 1)l2 + 1 ? m2 = 0 ai + k + 1 ? l ? i = 0 ((a + u2(u2 ? a))2 ? 1)(n + 4dy)2 + 1 ? (x + cu)2 = 0 p + l(a ? n ? 1) + b(2an + 2a ? n2 ? 2n ? 2) ? m = 0 q + y(a ? p ? 1) + s(2ap + 2p ? p2 ? 2p ? 2) ? x = 0 z + pl(a ? p) + t(2ap ? p2 ? 1) ? pm = 0 533 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 22:48:35 ] >>532 どこのwikiに載ってたの？ 534 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 07:13:02 ] Wikipediaをwikiって略すなー、な所だな 535 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 12:13:47 ] ところでウィキペディアにフォーチュンの予想はない件 536 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 12:42:35 ] フォーチュンってどれくらい偉い人？ 声優で喩えて 537 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 13:38:19 ] 石丸博也くらい 538 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 15:11:05 ] そんなに偉い人だったのか 僕もヌンデマス 539 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 17:33:34 ] >>535 google books で、ウェルズのプライムナンバーズの訳本が読めるぞ。 該当箇所は、P122だけど、ちょうどそこは読める範囲にある。 興味があればどうぞ。 540 名前：デフォルトの名無しさん mailto:sage [2009/07/31(金) 02:19:19 ] フォーチュンってサモアのデマで有名なマーガレット・ミードの旦那かよ 541 名前：tor.rootkit.de mailto:age [2009/08/17(月) 17:57:46 ] 自動焼人 ★　＝　自動保守 ◆KAWORUKOFI　＝　自動保守#K9K?_D[L 名言集　その１ 『アパッチ砲はワシが作った』 jbbs.livedoor.jp/bbs/read.cgi/internet/134/1229674638/5062 自分の管理するしたらばで借りた掲示板にて > 5062 ：自動保守 ◆AOIMAD.NZM [] ：2009/08/16(日) 00:46:29 ID:nQYgq9jg0 > そもそも、アパッチ砲っていうのは、私が指揮官になった時代に私の先輩たちが導入して > 先輩たちが命名したもの、っていうかまぁ、そういう砲は今まで存在してないから > 名前つけなくちゃいけないしｗ > > ってことで、使っているうちに広まった名前なので、それが正式名称になるんじゃないかと。 > > www.paradisearmy.com/doujin/pasok_apache.htm（俺の先輩が命名） > www.paradisearmy.com/doujin/pasok_hping.htm（俺が命名？） ※注　「アパッチ砲」の正式名称は「Apache Jmeter」で、もちろん自動焼人の先輩が作ったものではありません ---------------------------------------------- この自動焼人 ★メールマガジンの配信停止をご希望される方は qb5.2ch.net/test/read.cgi/sec2chd/1250169591/ にて自動焼人 ★までご連絡ください 542 名前：デフォルトの名無しさん [2009/11/09(月) 05:02:04 ] 平方根を求めるアルゴリズム下さい 小数点演算を使用せず整数のまま演算し、 実数の平方根を超えない最大の整数を返すものとします 543 名前：デフォルトの名無しさん mailto:sage [2009/11/09(月) 06:29:51 ] isqrt.c でググれ 544 名前：デフォルトの名無しさん mailto:sage [2009/11/09(月) 08:42:18 ] つ 「ニュートン法」 545 名前：デフォルトの名無しさん mailto:sage [2009/11/09(月) 12:09:28 ] １から元の値の間で二分法が簡単かな

---

---

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

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