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

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18] どこにもない強固なスレにしたい 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文字 の順列をぜーんぶ列挙するのになにかよい方法ってありますか？ つまりは任意の配列から総当りするためのネタ作りをしたい訳なのですが。。。 338 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 02:37:18 ] 順列？同じものの重複利用は禁止？ 339 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 08:06:36 ] permutation でぐぐれ いっぱいサンプルプログラムが転がってる 340 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 09:33:12 ] >>338 はい。2が入力だったAB,BA見たいな感じのものが生成されるような。。。 >>339 ありがとうございます。見てみますね。 341 名前：デフォルトの名無しさん mailto:sage [2008/03/11(火) 22:47:15 ] アルゴリズムスレで言うのもなんだけど C++ だったら STL にある next_permutation 使うと割と簡単に書けると思う。 342 名前：337 mailto:sage [2008/03/11(火) 23:54:54 ] まだ詳細は調べ切れていないのですが、こういうのって自分で手書きするなら・・・・ 並べ替えたいN個の要素のリストから一つ取っては、N-1人の自分にN-1個になったリストと自分の ポインタをそれぞれ丸投げし、N-k番目の子はk番目の要素を一つとってさらに子に・・・取るものが ラスト一個になったら、自分の親の取った要素をつなげて表示する。 みたいな実装イメージになるんでありましょうか。 343 名前：デフォルトの名無しさん mailto:sage [2008/03/12(水) 23:07:29 ] 書き方なんていくらでもあるだろうが、俺だったらリストにせずに配列を使って再帰的には書くと思う。 っちゅーかそれこそ調べればいいんじゃないの？と言いつつ安易に書いてみる。 後、26! = 403291461126605635584000000 なんで全部回してるとやってられないと思う。 #include <iostream> int result[26]; void permutation_imp(int n, int m) {   if(m == n) {     for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(result[j] == i) std::cout << ' ' << static_cast<char>('A' + j);     std::cout << std::endl;   } else {     for(int i=0;i<n;++i) if(result[i] == -1) { result[i] = m; permutation_imp(n, m+1); result[i] = -1; }   } } void permutation(int n) {   for(int i=0;i<n;++i) result[i] = -1;   permutation_imp(n, 0); } int main(void) {   permutation(3);   return 0; } 出力結果：  A B C  A C B  B A C  B C A  C A B  C B A 344 名前：デフォルトの名無しさん mailto:sage [2008/03/13(木) 21:43:11 ] 参加してみた #include<stdio.h> #include<string.h> void swap(char *a, char *b){ char c; c=*a;*a=*b;*b=c; } void func_internal(char *buf, int bufsize, int left){ int i; if(left<=0) printf("%.*s\n", bufsize, &buf[-bufsize]); // 気持ち悪いかな？ for(i=0;i<left;i++){ swap(&buf[0], &buf[i]); func_internal(buf+1, bufsize, left-1); swap(&buf[0], &buf[i]); } } void func(char *buf, int bufsize){ func_internal(buf, bufsize, bufsize); } int main(void){ char buf[]="abcde"; func(buf, strlen(buf)); return 0; } 345 名前：337 mailto:sage [2008/03/14(金) 03:01:52 ] >>333-334 これまた短いですね。。。なんでこんなのが思いつくのかが不思議です。 自分の思った方法でも無理ではないんだろうなとは思うのですが、擬似コードの段階で だらだらしたものになってますからね。。。 再帰ですらすら考えられる人ってあたまよさそうです。 346 名前：337 mailto:sage [2008/03/14(金) 03:02:36 ] >>345 アンカーミス。。。 >>343-34 でした。 347 名前：デフォルトの名無しさん mailto:sage [2008/03/14(金) 09:00:14 ] 多くのアルゴリズムは定番とか定石がある。特に基礎的なものは。 このスレのタイトルの本もそういうものだわな 348 名前：デフォルトの名無しさん mailto:sage [2008/03/17(月) 18:49:55 ] A/D変換データをソフト的な処理で安定させるやり方 として移動平均以外に何かありますか？ 移動平均は平均回数をおおくとると、反応 が遅く（変化が鈍く）なるので、なるべくそうならな い方法を探しています。 349 名前：デフォルトの名無しさん mailto:sage [2008/03/17(月) 22:10:48 ] >>348 Ａ／Ｄ、Ｄ／Ａ半導体 science6.2ch.net/test/read.cgi/denki/1120158621/ 350 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 02:11:43 ] >>348 高次曲線近似とかベジェ曲線近似はどうかな？ 351 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 09:17:19 ] 移動平均はFIRフィルタ　LPFの一種だから係数をキチンと設計すれば応答性と安定性を両立出来る。 計算量の面では２次の IIRフィルタにすれば、応答性と安定性と計算量も両立出来る。 352 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 10:01:45 ] >>350 初めてききました。なんだかC言語で書くと難しそうですね。 >>351 係数って平均回数のことですよね？ 353 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 11:45:53 ] 平均回数じゃなくて、 FIRフィルタでするという場合は、それぞれに重みを付けて計算するわけ だから、移動平均に比べて計算コストは非常に大きい 例えば、サンプリング間隔の1/5以上で変動するようなノイズを取りたいという時に 16個の移動平均をしても ノイズは1/16までしか減らないけど 0, 0.015270303 1, 0.048044002 2, 0.098545986 3, 0.151768713 4, 0.186370997 5, 0.186370997 6, 0.151768713 7, 0.098545986 8, 0.048044002 9, 0.015270303 と１０個の係数かけて累積すれば、サンプリング間隔の1/5以上の成分は1/200以下に減る 354 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 15:30:03 ] 例えば １０、１５、２０、１０ っていう４つのデータがある場合 10*0.4 + 15*0.2 + 20*0.2 + 10*0.2みたいに するっていうことですか？ この重みの決め方がまた大変そうですね。 ちなみに353の例だとなんで1/200になるんですか？ なんかアルゴリズムとは関係なさげな話になって 申し訳ないです。 355 名前：デフォルトの名無しさん mailto:sage [2008/03/18(火) 20:34:43 ] たとえば、　sin(i*1.3)*100+200 みたいな信号が入力されたとする。 入力　移動平均　>>353の方式それぞれの結果は 200.0 12.5 3.1 296.4 31.0 14.1 251.6 46.7 37.8 131.2 54.9 73.6 111.7 61.9 115.1 221.5 75.8 152.4 299.9 94.5 178.6 231.9 109.0 192.7 117.2 116.3 198.4 123.8 124.1 200.0　 <--　10個目から >>353 の方式はほぼ200に安定 242.0 139.2 200.0 298.7 157.9 200.1 210.8 171.0 200.0 107.1 177.7 199.9 139.5 186.4 200.0 260.6 202.7 200.1 <-- 移動平均は16個目以後でも±8程度変動する 292.9 208.5 200.0 189.1 201.8 200.0 101.3 192.4 199.9　ただしsin(i*w) のwの係数が　 2*PI/5=1.25 以上の時に >>353 は効く 158.1 194.1 200.0 276.3 204.4 200.1 356 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 22:37:03 ] ちょっと考えてる問題があるので意見を聞かせてください。 例えば300個の積み木があるとして、これらは様々な重さ・大きさがあり、5種の色のいずれかが ついてたとします。 これらを山に積み上げて行くときに、なるべく重さのピークが高い山がたくさん欲しいけれど、以下 の条件を満たさないといけないとします。 １．大きいものほど下にある ２．一山は積み木は10個が限度だけど、赤い積み木が三つ含まれていたら8個が限度になる。 ３．一山には2色しか存在してはいけないし、異なる色の境界は1箇所だけ(赤青赤はだめで、赤赤青は良いみたいな) ものすごく簡略化してしまいましたが、ナップザック問題に条件が加わったようなものになるのかと 思います。 細々とした条件・・・特に色の条件のせいで欲張り法が使えない気がするのですが、こういったものを常識的 時間で解く方法を調べたいので、キーワード程度でも教えてもらえませんか？厳密、近似は問いません。 357 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:31:07 ] >>356 「重さのピークが高い」って言葉の意味が分からない． あと，複数の山があったときにどう評価するかも分からない． 具体例をいくつか出してくれないかしら． 358 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:40:00 ] >>357 重さのピークについてですが、例えば価値＝重さが 1 2 2 3 4 5 6 7 8 9 のような9個があったとして、ここから>>356より少ないですが、2段まで積んでいいこととするならば 98 76 54 32 21 のような山できてほしくて、 19 82 27 36 45 のようにはできて欲しくないのです。 できた山の価値の標準偏差が一番でかい組み合わせになるんでしょうか・・・ 書いてて思いつきましたが、>>356をさらにいうならば、300個から最大で10個（特例を除く）で構成される山 を例えば15個作るとき、最も15山の価値の合計が高くなる組み合わせ。 これだとまた全く別の問題になってしまうのでしょうか。 359 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:40:37 ] ＞のような9個があったとして 10個でした。 360 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:46:06 ] まず問題を誰にでもわかるように定義することからはじめようか。 361 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 23:53:53 ] >>357 問題を考えるときは，それを数式で書けるくらいまで整理しないと， アルゴリズムなんて出せるはずがない． きっとなんか解きたい問題があって，あなたはその要点のみを 取り出したつもりだと思うんだけど，取り出し方が悪くて全然分からないよ． 362 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 00:10:42 ] 解きたい問題は実は特になくて、この手の雑学の本を読みながら考えていたら、これは欲張り法で できるのかな？と思ったのです。 で、もうちょっと整理してみました。 ナップサックが10個、取れる品物は300個あるとしてこれらはランダムに5色のいずれかの色がついている １．品物の価値が高いものを先に詰めねばならない ２．品物の色は、一袋には2色までしか混載できない ３．さらに一袋を詰め終わる過程で、色の切り替わる回数は一回のみ ４．ナップサック一つには10個まで入るが、赤い色の品物を3個入れていたら8個までになる 以上の満たして10個のナップサックをつくり、10袋の価値和を最大にする ２、３は、「赤赤赤赤青青青青青青」はいいが、「赤赤赤赤青青青青赤赤」だめ ４は「赤赤緑緑緑緑緑緑緑緑」で一袋、「赤赤赤緑緑緑緑緑」で一袋になるという感じ これですっきりしたよーに思いますがどうでしょう？ 色がついているのと、4みたいな条件のせいで、欲張れないんじゃないかと思うのです。 363 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 00:10:52 ] Σ((山の重さ)^2) を最大化するの？

---

---

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

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