アルゴリズム講座/実践編/バックトラック
バックトラック(バックトラッキング)は思考アルゴリズムの王様と言っても過言ではありません。私の知る限り思考プログラムの約90％はバックトラックを使っていると思います。 １．バックトラックの考え 人が行う「試行錯誤という行為」を忠実に実行するように考え出されたアルゴリズムで利用範囲は 広範です。もちろん不得意分野もあります。 複数の未知のものを上手く組み合わせて、ある条件を満たす全体を得るのに、その未知のものを ひとつずつ許される範囲内で「もし、こう仮定して」さらにこの状態から「次に、こう仮定して」 というように仮定から仮定へと強引に突き進みます。 そんなことをすれば大抵は途中で行き詰ってしまいます。その時は1歩戻って(バックトラッキング) 仮定を立て直して、また、突き進みます。総ての仮定に失敗したら、そこからまた1歩戻って新たな仮定 を立て直して同様に進行すれば、やがては解に到達することに
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
てっく煮ブログ - 四則演算を JavaScript で実装する
aki note ≫ Google 電話面接を受けました orz （いまは消えてるけど）にて割り算が壊れました。自分で実装してみてくださいという質問が紹介されていた。せっかく(?)の機会なので、割り算だけでなく、四則演算を全部壊してみて、JavaScript で実装して見ることにした。JavaScript を選んだのは、コンパイル不要、ビット演算がある、Firebug で手軽に確認できる、という理由から。それ以上の深い意味はない。ということで、次のような問題に一般化してみた。問い四則演算を JavaScript で実装しなさい。演算子は ==、!= およびビット演算子のみ使ってよいものとします。補足例えば、for 文で for(var i = 0; i { // ... } と書くためには、++ 演算子は次のように定義できる。 function increment(i){ var c =
第11回 プログラム同士の対戦ゲーム
あなたは魔法使い。もちろんプログラミングの腕もウィザード級です。そんなあなたがライバルと対決することになりました。マップ上にある「魔法の要素」をうまく集めてライバルを倒すプログラムを作成してください。今回は，カコミ記事「ゲームのルール」に従って移動ができるまでとします。 キャラクタを移動させるアルゴリズム アルゴリズムを作っていて一番うれしいと感じるのは，「自分で作ったアルゴリズムが動くところを見る」ときではないでしょうか？ 日本IBM主催で大会が開かれた「Robocode」がその代表的なものでしょう。Javaで仮想的なロボットを制御するアルゴリズムを記述し，対戦させるゲームです。アルゴリズムを組み立てたら，さっそくその内容を試せますし，アルゴリズムが悪ければゲームに負けてしまいます。こうして楽しみながらトライ＆エラーでアルゴリズムを組み立てられるところから，新人研修などで最近よく使われて
地球にやさしいアルゴリズム---目次 - 地球にやさしいアルゴリズム：ITpro
アルゴリズムを構成している楽しい仕組みを紹介しながら，あなたに「おおっ」と言わせることが，本連載の最初の目的です。興味を持てたなら，アルゴリズムに関する文献や情報を抵抗なく読めるようになるはずです。アルゴリズムを使いこなしたり，作ることも無理なくできるようになるでしょう。 まずはいろいろなアルゴリズムの面白いところを見て，楽しんでみましょう 第1回 ナンプレを解いてみよう 第2回 パズルみたいに楽しいデータ圧縮 第3回 「場面」の移り変わりに注目する 第4回 できるだけ短いルートでゴールに到達する 第5回 隣の区画と異なる色で地図を四色に塗り分ける 第6回 上手なアルゴリズムの見つけ方 第7回 多対多の関係を賢く扱う 第8回 倉庫番を解くアルゴリズム 第9回 プロトコルを実現するアルゴリズム 第10回 麻雀の役を判定する 第11回 プログラム同士の対戦ゲーム 第12回 対戦ゲームの戦略を考
「安定な」クイックソート - 飲み物だから太らない
id:sawat:20061123の記述に関して。 クイックソートとマージソートの話で、クイックソートは安定でないということが書かれているが、そういう風に書くとさすがに嘘じゃないか？と思ったので。安定と言うのはこの場合、リスト中に同じ大きさの要素があった場合に、その順序が入れ替わらないことを言う。 クイックソートで第一に重要になるのはピボット選択(つまり、比較対象の選択)だが、これをもし仮にリスト(or配列)の中から取ってくるとすると、その値をどこに入れるのか。その作業で不安定になることがある。しかし、クイックソートはリストの対象を二つに分割するわけだが、その操作においては安定であるようにすることが可能である。例えばHaskellなどでよく使われるクイックソートは、 quicksort :: Ord a => [a] -> [a] quicksort = quicksort (x:xs)
stable quick sort - odz buffer
ref:落ちてないけど堕ちている - 「安定」なクイックソート stable な quick sort もあるよ、という話なのだが。 quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (x:xs) = quicksort [ y | y <- xs, y < x ] ++ [x] ++ quicksort [ y | y <- xs, y >= x ]これは遅そうだなぁ。in-place にはできないのか？じゃないとメモリ消費量がすごそう。 ただし、このようなことをする場合には内部的にmallocが必要となる(リストだし・・・)。 連結リストだからといって毎回動的メモリ確保が必要かといえばそうでもない。必要なサイズがあらかじめ分かれば1度大きな配列を作ってインデックスをポインタ代わりに使えば済む。 そもそも、問題は m
Sorting Algorithms Demo
Sorting Algorithms We all know that Quicksort is one of the fastest algorithms for sorting. It's not often, however, that we get a chance to see exactly how fast Quicksort really is. The following applets chart the progress of several common sorting algorithms while sorting an array of data using in-place algorithms. This means that the algorithms do not allocate additional storage to hold tempora
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Subsetの生成