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

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18] どこにもない強固なスレにしたい 237 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 15:35:42 ] 標準に存在しないからって力技で自作したんだがどうだろう ベジエ勉強したほうが良いのかな 238 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 19:41:45 ] せめて入力変数の意味くらい書いてくれ 239 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 23:01:13 ] >>237 ベジエ曲線で完全な楕円は表現できない 近似はできるけどな 240 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 23:20:49 ] >>238 HDCはおいておいて、残りの5つは 焦点の座標（２つ）と長径 >>239 実用に耐えるなら近似で良いんだけどね 241 名前：デフォルトの名無しさん mailto:sage [2006/09/30(土) 23:59:26 ] 用途にもよるが、俺ならサンプル点の密度が極端に偏るアルゴリズムは使わないな。 242 名前：デフォルトの名無しさん [2006/10/22(日) 19:47:46 ] 最大遅れ最小スケジューリング (minimization of the maximum lateness) ってあるけど、 この最大遅れの「最大」ってなんなの? 遅れの合計を最大化したものを最小化? 意味がわからん。 エロい人教えて 243 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 19:51:50 ] 最大の遅れを最小にする．たとえば ・最初の仕事で30分遅れてあとの仕事はジャスト．（最大遅れ30分） ・全部10分づつ遅れる．（最大遅れ10分） の二つだったら，後者のほうが良いとするスケジューリング． 244 名前：242 mailto:sage [2006/10/22(日) 19:55:00 ] >>243 なるほど!トンクス 245 名前：デフォルトの名無しさん [2006/10/31(火) 16:55:59 ] $a=array('red','blue','yellow','green'); $b=array('white','blue','yellow','green'); $c=array('green','red','yellow','cian','black'); $a,$b,$cのどれにも存在する要素の'yellow','green'を取得するソースをPHPで。 246 名前：デフォルトの名無しさん [2006/11/02(木) 01:42:06 ] PHPで何？ 247 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 11:51:23 ] >>245 array_uintersect 248 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 19:21:30 ] 二つのソート済みの配列が与えられていて（合計の要素数はN） N個の要素からメディアンを計算量O(LogN)で求めるアルゴリズムを教えてください。 ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf www.cse.ust.hk/faculty/scheng/comp271h/assign/hw2_sol.pdf 検索して出てきたこの二つのPDFにある擬似コードをCで実装してみたんですけど 何度かテストしたらどちらも時々スタックオーバーフローが発生してしまいました。 （正しい結果を返すときもありました） 二つの配列の長さが同じ場合にしか使えないコードでもいいのでお願いします。 249 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 20:57:41 ] >>248 2つのソート済み配列をA,Bとする。 Aの中央値とBの中央値を比較する。 Aの方が大きいとすると、Aの小さいほうの集合とBの大きいほうの集合を残す。 以下これを反復する。1回の反復は配列の要素を指定して比較するだけだから定数オーダー。 反復ごとに要素数が半分になるから反復回数はlog N回 250 名前：248 mailto:sage [2006/11/03(金) 03:05:44 ] >>249 ありがとうございます。こんな感じになりました。 int median_search(const int *A,const int *B, int n){ 　　int m; 　　if(n==1) 　　　　return A[0]>B[0]?A[0]:B[0]; 　　m = n>>1; 　　if(A[m]>B[m]) 　　　　return median_search(A,B+m,m); 　　return median_search(A+m,B,m); } nは配列AとBの長さです。 ソート済みの配列AとBをマージした長さ2nの配列をCとするとこの関数はC[n]を返します。 A[0]>B[0]?A[0]:B[0];の部分を、A[1]<B[1]?A[1]:B[1];にすればC[n+1]を返します。 251 名前：248 mailto:sage [2006/11/03(金) 03:14:48 ] 連続投稿すみません・・。 >>250は配列の長さnが２のべき乗の場合しか使えないようですね・・。 もうちょっと考えてみます・・。 252 名前：デフォルトの名無しさん [2006/11/04(土) 02:07:10 ] バルブソート の検索結果 約 98,900 件中 1 - 10 件目 (0.75 秒) 253 名前：デフォルトの名無しさん mailto:sage [2006/12/01(金) 10:57:06 ] "バルブソート" の検索結果 約 73 件中 1 - 6 件目 (0.04 秒) 最も的確な結果を表示するために、上の6件と似たページは除かれています。 254 名前：デフォルトの名無しさん mailto:sage [2006/12/26(火) 19:17:24 ] バルブソート の検索結果 約 87,100 件中 1 - 10 件目 (0.29 秒) 255 名前：デフォルトの名無しさん mailto:sage [2006/12/27(水) 11:18:50 ] "パブルソート" の検索結果 2 件中 1 - 2 件目 (0.25 秒) 256 名前：デフォルトの名無しさん mailto:sage [2006/12/28(木) 09:05:20 ] ラストリゾート の検索結果のうち 日本語のページ 約 159,000 件中 1 - 10 件目 (0.14 秒) 257 名前：デフォルトの名無しさん [2006/12/30(土) 16:37:47 ] 桃太郎電鉄の「いけるかな？」の判定アルゴリズム教えてくれ。 258 名前： 【吉】 mailto:sage [2007/01/01(月) 12:18:14 ] ただの幅優先探索じゃね 259 名前：デフォルトの名無しさん mailto:sage [2007/01/05(金) 00:45:08 ] 使える素子に制限がある、ある動作をする組み合わせ回路の探索アルゴリズムって何かの本にかいてますか？ 例えば、NOT2個とAND複数、OR複数個だけで並列な独立した3つのNOT回路と等価な回路を探すアルゴリズム。 「思考する機械コンピュータ」という本に載っていた問題です。(この条件が) この間バックトラックでやったらあっさりできましたが・・・ 260 名前：デフォルトの名無しさん mailto:sage [2007/01/05(金) 07:45:57 ] >>259 加算器ぐらい合成できないと意味はない 261 名前：デフォルトの名無しさん [2007/02/13(火) 08:13:38 ] 総当たりなんじゃ・・・ 262 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 08:54:07 ] >>261 証明 263 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 15:00:13 ] 素子の種類の条件を満たす真理値表を小さい方から総当たりだな。 ちなみに「条件を満たす回路が存在しない」ことの証明は 総当たりで調べても見つからなかったことを言う以外に方法はない。 典型的なNP問題。 264 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 19:51:44 ] >>263 総当りでしか証明できないならNPに入っていないじゃん。 探査空間Pで十分だからPSPACEには入っているけど。 265 名前：デフォルトの名無しさん mailto:sage [2007/02/14(水) 16:25:03 ] ＞総当りでしか証明できないならNPに入っていないじゃん。 ？ 266 名前：デフォルトの名無しさん mailto:sage [2007/02/14(水) 18:10:31 ] >>265 NP=ある多項式長の補助入力が存在してPで解ける 総当り→補助入力は多項式長でないからダメ 補問題であるある場所にいけるかは 道順の例を補助入力として与えればこれは多項式長であり、明らかにPで検証可能。 したがって補問題はNP。 補問題がNPだから、PSPACEよりも狭いco-NPに入る。 267 名前：デフォルトの名無しさん mailto:sage [2007/02/15(木) 03:59:35 ] むずかしいはなしはきらいです 268 名前：263 mailto:sage [2007/02/15(木) 06:14:34 ] 間違った。 等価な回路を探すアルゴリズムがNPで、存在しないことの証明はNPじゃない。 269 名前：259 mailto:sage [2007/02/15(木) 16:03:39 ] もしアレでしたらソースコードUPしますけど・・・ 270 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 00:56:55 ] いらね 271 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 04:04:04 ] いる 272 名前：259 mailto:sage [2007/02/16(金) 04:34:16 ] 見たら吐くかも ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/3659.c 273 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 07:39:57 ] #define NOTA まで読んだ。 274 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 07:40:39 ] なんだよ、ノタって。ふつーNOT_Aだろ。 275 名前：デフォルトの名無しさん mailto:sage [2007/02/18(日) 16:31:13 ] 某板よりコピペ 多数のオブジェクトの衝突判定を並列化する方法 移動後の座標をボクセルに振り分ける。 1つのボクセル内に存在するキャラを総当たりで衝突判定。 処理の順序としては、移動、振り分け、衝突判定、衝突処理。 これで処理を並列化できる。 もう少し詳しく言えば、衝突判定をしやすくするために、 ボクセルに振り分ける時点で座標値などをボクセルごとの一時バッファに複製しておく。 これにより巨大なバッファをLSにロードする必要がなくなる。 衝突の連鎖については次フレームに回す。それで結果的には再帰処理になる。 普通は移動後に振り分けるというより ボクセル内のオブジェクトを管理するバッファを常設しておいて 移動でボクセル外に出たときだけバッファの更新をするでしょ。 276 名前：デフォルトの名無しさん mailto:sage [2007/02/19(月) 01:19:29 ] 類似の手法は物理計算では常識。 ボクセルよりも適当な空間木を用いたほうがよいと思う。 オブジェクトの分布や座標空間にもよるが、計算量の 意味で速度が改善されることも珍しくない。 277 名前：デフォルトの名無しさん mailto:sage [2007/02/20(火) 03:50:22 ] >>274 ふつーNOT_Aなのは分かる しかし、Shiftを押しながら「ろ」キーを押す手間が面倒なのも分かってしまうんだな 俺はどっちを応援すればいいんだ？ 278 名前：デフォルトの名無しさん mailto:sage [2007/02/20(火) 06:10:11 ] ふつーSHIFT+- 279 名前：デフォルトの名無しさん mailto:sage [2007/02/20(火) 16:04:22 ] その点以外の感想が欲しい今日このごろ 280 名前：デフォルトの名無しさん mailto:sage [2007/02/22(木) 07:38:32 ] C言語のソースは読むきしねぇ コメントぐらいかこうね 281 名前：デフォルトの名無しさん [2007/07/03(火) 15:59:46 ] 整数のリストを入力とし整数のリストを出力する関数nayose を、 Minimal を用いて次のように定義する。(ただしプログラム中、A or B 　はA とB のうち少 なくともどちらか一方がtrue のときtrue を返し、それ以外のときはfalse を返す論理演算 である。) 以下の問に答えよ。 fun member x lst = case lst of [] => false | hd::tl => hd=x or (member x tl) end; fun nayose lst = case lst of [] => [] | hd::tl => if (member hd tl) then (nayose tl) else hd::(nayose tl) end; (1) 関数nayose はどのような計算を行う関数か簡潔に答えよ。 (2) 長さがn のリストに関数nayose を適用したときの計算量をO(f(n)) の形で表せ。 (3) あらかじめ整列された整数のリスト（重複があってもよい）を入力とし、関数nayose と 同様の結果を出力する関数で、入力リストの長さがn のときの計算量がO(n) となるよ うな関数nayose2 を、Minimal プログラムで示せ。関数nayose2 がnayose と同様の結 果を出力する理由を簡単に説明すること。 (関数nayose2 は、整列されていない入力についてはnayose と異なる結果を返しても良 い。） 282 名前：デフォルトの名無しさん mailto:sage [2007/07/05(木) 07:23:15 ] 宿題は宿題スレへ 283 名前：デフォルトの名無しさん [2007/09/08(土) 02:49:46 ] age 284 名前：デフォルトの名無しさん mailto:sage [2007/09/10(月) 15:56:14 ] 反駁環境における生成器 % 何も生成しない生成器 repeat. repeat :- repeat. % 類型 リストからの生成 member(A,[A|_]). member(A,[_|R]) :- member(A,R). % 類型 リストの分解 append([],X,X). append([U|X],Y,[U|Z]) :- append(X,Y,Z). 285 名前：デフォルトの名無しさん mailto:sage [2007/09/11(火) 03:52:19 ] % 生成器のつづき % 連続整数の生成器(昇順) for(N,N,E) :- N =< E. for(S,N,E) :- S =< E,S2 is S+1,for(S2,N,E). 286 名前：デフォルトの名無しさん mailto:sage [2007/09/23(日) 09:39:58 ] 他所のHPの書きこみなんだけど > よく知られている問題ですが、一般に、Ｎ個のもののソーティング(順序付け)の > ための必要最少限の比較回数はlog2(Ｎ！) ≦ ｋを満たす最小の整数ｋです。 って本当? ていうか必要だけど充分じゃないっていう意味で言ってるんだろうか. 287 名前：アルゴリズム初心者 [2007/10/13(土) 20:48:56 ] ツリー構造(あるディレクトリ以下のファイル・フォルダ群）同士の差分を取得したいのですが、 そういったアルゴリズムの解説お願いします。 もしくはためになりそうなキーワードやウェブサイトを教えてください。 ３年くらいプログラミングはしているのですが、画面を作るばかりで 頭を使うようなことは一切やったことが無いので詰まってしまいました。。。 288 名前：デフォルトの名無しさん mailto:sage [2007/10/13(土) 21:04:06 ] アルゴリズムも何も、diff -rじゃダメなのか? 289 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 00:14:49 ] >>287 WinMergeをダウンロードしてくるといいよ 290 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 00:39:33 ] WinMergeはサブフォルダごと一気に比較すると、全部一画面で表示するから 見にくくてしょうがない。 DFみたいにフォルダごとに見れるようにしてくれよ。 291 名前：アルゴリズム初心者 [2007/10/14(日) 07:53:31 ] プログラムの中で使いたいのでこのすれにきています。そういうライブラリがあれば教えてください。 292 名前：アルゴリズム初心者 [2007/10/14(日) 07:59:15 ] ちなみにJavaです。 293 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 08:56:05 ] diff のソース読めばいいんじゃないか？ 294 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 09:55:04 ] >287 さすがに手作業で同じ事はできるよな？ じゃ、まずは簡単な例で手作業でやってみよう。 次に、どういう手順で行ったか書き下してみる。 で、人間なら分かるけど計算機には分からないといった about なところを詳細化する。 最後にコードに落としてやれば OK だ。 この程度で、アルゴリズムだとかライブラリだとか情報源とか探してるようだと いつまでたってもそのレベルから抜け出せないよ？ 295 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 10:34:59 ] >>291 system("diff -r dir1 dir2") 296 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 10:39:33 ] ある範囲内のユニークな乱数列を作る方法を教えてください 297 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 12:55:17 ] >>296 どういう範囲内でユニーク？ ユニークなことを確実に保障するのって難しいよ。 298 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 13:21:17 ] >>297 範囲というか、DBの正規化レコードのテストに使うので1〜1000万ぐらいで。 乱数をハッシュテーブルに登録してユニークな乱数列を作れないかと 思ったんですが、目的レコード件数分まわしても、重複で抜け番号が 出てくるので、一気に全部埋まる方法ないかなと。 299 名前：296 mailto:sage [2007/10/14(日) 13:24:14 ] 逆に、整列されたスカラ値の配列やリストを、 ランダムに混ぜる方法でもいいです。 300 名前：296 mailto:sage [2007/10/14(日) 13:28:03 ] あと、再現性が必要なのでシード値を取れる方法が好ましいです。 301 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 13:50:17 ] ユニークである必然性あるのかな？ 全数チェックしたらｗ 302 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 16:24:11 ] >296 多分、ユニークな乱数列、の意味が人によって違っているような気がする。 「乱数列」がユニークであることを望んでいるのではなくて、乱数列中に表れる数値がユニーク(重複しない) ってことなんだよね？ C++ で良ければ(アルゴリズムの説明にならないけど)、>299 で random_shuffle() 使うのが一番簡単かと。 あるいは、random(N) を 0〜N-1 の整数を発生する(シード値をとれる)疑似乱数生成関数として、a[0]〜a[N-1] にたいして、 for(i=0;i<N;++i) {     idx = random(N);     tmp = a[i];     a[i] = a[idx];     a[idx] = tmp; } で、いいんじゃない？ 303 名前：296 mailto:sage [2007/10/14(日) 20:45:00 ] あー その通りです。 ありがとうございました。 304 名前：デフォルトの名無しさん mailto:sage [2007/10/14(日) 20:49:40 ] >>302 そのコードだと均等に混ざらない（すなわち、全ての可能なケースが等確率で出ない）。 正しくはこんな感じ for(i=0;i<N;++i) { 　　idx = random(N-i) + i; 　　swap(a[i], a[idx]); } 305 名前：デフォルトの名無しさん mailto:sage [2007/11/13(火) 01:55:34 ] URIの一致箇所検出に 最適なアルゴリズムってどれですかね？ 306 名前：デフォルトの名無しさん [2007/11/20(火) 17:17:18 ] >>305 質問の意味がよくわからない 最長共通文字列？ ところで、良いアルゴリズムというかロジックが思い浮かばないんだけど何か良いの無いかな。 配列をPivotとの大小関係で三つに区切る。 C++っぽい擬似コードで書くとこんな感じ under = partition( Begin End < Pivot ) partition( under End == Pivot ) これより計算量係数を下げたいんだけど。 307 名前：デフォルトの名無しさん mailto:sage [2007/11/23(金) 08:28:25 ] >>306 係数を議論するなら計算モデルを出さないと普通不可能だし， その擬似コードの partition の実装もわからないからなんともいえない． 308 名前：デフォルトの名無しさん [2007/11/24(土) 19:00:09 ] 306 携帯からでカンマが改行になってしまいました。 >>307 具体的に計算する必要はありません。 何か他の実装が partitionの実装が分からなければSTLのソースでも見てください。 309 名前：デフォルトの名無しさん mailto:sage [2007/11/24(土) 19:52:52 ] >>308 ちと文章が切れてるので何を言いたいか察しかねるが、 計算量係数ってことは O(n) で隠れてる定数部分を 評価したいんでしょ？ そのためには、たとえば 　・対象はどう表現されているか（リスト，配列 etc） 　・n として何を数えるか（比較，イテレータの移動，スワップ etc） 　・それぞれどれくらいの計算コストの差があるか なんか決まらないと、とても評価できない。 「実用上早い」ってのは知られてるけど、計算量の係数が 実際にどんくらい小さいかってのは不明。 あと、306 のコードは「C++ 風の擬似コード」じゃなかったの？ それで「実装は STL を見ろ」というのではあなたの言うところの 擬似コードの意味がよくわからないんだけれど。 それに STL の partition はアルゴリズムは全く決めてないから 例えば「gcc のどのバージョンの STL の実装」とか言わないと。 310 名前：デフォルトの名無しさん mailto:sage [2007/11/24(土) 23:27:09 ] 何がやりたいのかわからんので、 エスパーで問題を考えて回答しよう。 入力 *X;(1,2,4,4,4,5,6,7);//ソート済み配列,長さO(n) Pivot=4;//比較する値 Begin=0;//探索範囲？ End==7;// 出力 (2,5);//(1,2),(4,4,4),(5,6,7)と分けたときの4と5のインデックス アルゴリズム B=Begin;E=End; while(E-B&g;1) if(X[(B+E)/2]>Pivot) 　　E=(B+E)/2; else if(X[(B+E)/2]<Pivot) 　　B=(B+E)/2; else {　　N=(B+E)/2; break; } 以降はBとN間、NとE間の境界を通常の二分探索で見つける。 比較回数の最悪は明らかに1回目の比較でbreakして全体の1/2のサイズの二分探索を二回行わなければならないときで、 1+2(logn-1)=2logn-1回 311 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 02:31:58 ] >>310 それはエスパー失敗 ソートされていない配列をピボットよりも 「小さい・同じ・大きい」に分ける」のが問題でしょう。 312 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 16:45:03 ] >>311 そんなの順番に見ていくブルートフォースアルゴリズムが自明で最速ではないか。古典では。 313 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 17:58:59 ] >>312 ブルートフォースという意味がよくわからないけれど、 先頭から順に見ていき、ピボットとの小中大によって 対応するリストにコピーする、というアルゴリズムのこと？ もしそうであれば、普通の計算コストの設定では最速ではない。 なぜならば、そのアルゴリズムは、「要素のコピー」 が 必ず n 回発生するが、普通はコピーは比較より数倍重い。 314 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 21:55:16 ] >>313 そのアルゴリズムが最速ではないというなら最速なアルゴリズムを記述してくれ。 コピーが重いならコピーせずにポインタで参照すればいいのでは。 二段参照になるからリストの性能は落ちるだろうが。 315 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 22:09:04 ] >>314 「最速」かどうかは知らないが次の論文を参照。 Jon Bentley and Robert Sedgewick, "Fast Algorithms for Sorting and Searching Strings", Eighth Annual ACM-SIAM Symposium on Discrete Algorithms New Orleans, January 1997 316 名前：315 mailto:sage [2007/11/25(日) 22:12:19 ] 補足。 コピーが重いというのは、別にオブジェクトが重いとかそんなものではなく、 int の値のコピーと int の値の比較でもコピーのほうが数倍遅い。 本当に膨大なデータを処理しようと思ったときは、この定数倍が響くことがある。 （それに、上のアルゴリズムは余計な空間を使うのも痛い） 317 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 22:52:24 ] >>316 おｋ理解した。 swapで必要なところだけ入れ替えると。 swapでコピーが2重に発生するから 最悪上の単純なアルゴリズムの2倍かかってしまうが、 平均的には速いと。 クイックソートは最悪時間はバブルソートと同じになるが、 平均的にはマージソートよりも速いみたいなものと。 318 名前：315 mailto:sage [2007/11/25(日) 23:30:21 ] >>317 ちょっと理解できていないように見えるんだけどな。 計算コストをきちんと設定しないといけないと言っていて、例えば 　・スワップはコピーを2回実行する 　・どこへのコピーも同じ単位時間で行える みたいなモデルを考えればあなたの言ってることはほぼ正しい （というか「平均的」（何の平均かわからんが）にも単純アルゴリズムが早くなる）。 しかし、現実の CPU ではそんなことは全然無くて、実際は 　・値のスワップはコピー2回よりも若干高速に実行される 　・同一作業領域中でのスワップは、別領域へのコピーよりもはるかに高速 ということになっているから、「2倍かかる」という算定は全く間違い。 x86 あたりを前提に算定すると「10倍以上早い」という結論でも不思議じゃない。 このあたりはオーダにしちゃうと完全に隠れる部分だから クイックソートを例に出すのは不適当だと思う。 319 名前：デフォルトの名無しさん mailto:sage [2007/11/25(日) 23:54:19 ] 具体例を見せてくれないかな。 320 名前：315 mailto:sage [2007/11/26(月) 00:33:18 ] >>319 何の具体例だい？「10倍以上遅くなる」ような実装の具体例？ そんなのは、Bentley-Sedgewick の論文からコードを引っ張ってきて、 手元で適当にコードを書けば簡単に具体例になるよ。 321 名前：306 [2007/11/27(火) 15:19:23 ] >>309 だらだらコード書くよりSTL使った方がやりたいことが分かり易いかと。 ﾌｧﾝｸﾀ書くのが億劫で擬似と言っただけです。 対象のデータ構造は特定しません。というかあわよくばデータ構造による差が分かれば尚良いです。…が面倒なのでﾗﾝﾀﾞﾑｱｸｾｽって事いいです。 STLは、書きながら思ったけど本当に突っ込まれるとは思いませんでした。一般に同じ様な実装だと思ってました。すみません。 確認したのはgcc3.4.4/4.2.2、VC8、bcc5.5、SGI3.3です。 >>311 補完ありがとうございます。 >>314 その最速が今揚げてる議題です。 322 名前：デフォルトの名無しさん mailto:sage [2007/11/27(火) 23:05:25 ] >>321 で、コスト設定はどうするの？ 少なくとも「イテレータの移動、比較、スワップ、スワップ」くらいのコスト比を 決めてくれないと、とても定数部分の違いは算定できないと思うんだけど。 現実のCPUみたいなキャッシュや分岐予測があるモデルだと、解析は さらに面倒なことになるけど、それはどれくらい考えないといけないの？ あと、 Bentley-Sedgewick は読んでみた？ 323 名前：デフォルトの名無しさん mailto:sage [2007/12/28(金) 03:47:56 ] うざ 324 名前：デフォルトの名無しさん [2008/03/05(水) 01:18:02 ] みんなアルゴリズムをどんな風に知っていったの？ ライブラリを主に使ってるから、ソート程度しか知らないんだけど、 今日、先輩プログラマにアルゴリズムも知らんのか？と言われた。 325 名前：デフォルトの名無しさん mailto:sage [2008/03/05(水) 02:01:07 ] 書籍 326 名前：デフォルトの名無しさん mailto:sage [2008/03/05(水) 23:39:34 ] アルゴリズムを知っているかどうかは使い捨てプログラマかどうかの目安の一つだな 327 名前：デフォルトの名無しさん [2008/03/06(木) 03:11:28 ] >>325 推奨書籍はありますか？ 328 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 07:54:07 ] 問題が解決出来るかどうか であって、アルゴリズムを知ってるだけじゃ駄目だろ。 アルゴリズムを知ってるだけでは、Fizz-Buzz問題でさえ解けるのは半数なんだそうだ 329 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 07:55:37 ] 奥村さんのアルゴリズム辞典が定番かね。 330 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 09:19:28 ] Introduction to Algorithms(MIT Press) 331 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 09:35:24 ] >>327 [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, Second Edition, MIT Press [KT] J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley [I] 石畑 清，アルゴリズムとデータ構造，岩波書店 [S] R. Sedgewick, Algorithms in C, Addison-Wesley [CLRS] はこの分野では定番で，標準的な教科書．和訳有． [KT] は最近出た本で，現代的な記述がされている． [I] は個人的にお勧めする本で，記述がやさしい．入門には適正． [S] は実装中心に書かれていて，理論より実装という人向け．和訳有． KT は最近和訳が進んでるって話もあるけど，きっとだいぶ先． 332 名前：デフォルトの名無しさん mailto:sage [2008/03/06(木) 11:32:21 ] 日経ソフトウェア買えばええやん 333 名前：デフォルトの名無しさん [2008/03/07(金) 07:20:53 ] アルゴリズムＣや珠玉のプログラミングはどう？ 334 名前：デフォルトの名無しさん mailto:sage [2008/03/07(金) 07:24:48 ] >>333 [S] R. Sedgewick, Algorithms in C, Addison-Wesley やん このあわてんぼさん。 335 名前：デフォルトの名無しさん [2008/03/07(金) 18:40:37 ] 「アルゴリズムC・新版」と「アルゴリズムC」って何が新版なの？ 336 名前： ◆JvckrUgJWM mailto:sage [2008/03/07(金) 18:43:11 ] >>327 つ ttp://d.hatena.ne.jp/yaneurao/20050522 337 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 02:31:13 ] 任意の26までの数値nが与えられたときに、Aからn番目のアルファベットまでを使ったN文字 の順列をぜーんぶ列挙するのになにかよい方法ってありますか？ つまりは任意の配列から総当りするためのネタ作りをしたい訳なのですが。。。

---

---

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

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