ソートについて
ソートについて はじめに n個の要素がある配列をソートする方法を挙げていく。 バブルソート バブルソートは最も簡単な方法です。 単純に隣同士を比較して順番が逆なら入れ替えるという操作を 一番目の要素から順番に行っていきます。 この操作をn回行うと、要素の中でもっとも大きな要素が一番n番目に来ます。 そして、また一番目の要素からn-1回操作を行います。 これで二番目に大きな要素がn-1番目に来ます これを繰り返してソートします。 サンプルコード //バブルソート void BubbleSort(int Data[], int n) { int BeginPlace, ComparePlace; //比較を始める位置を最初からn-1まで変えていく for(BeginPlace = 0;BeginPlace Data[ComparePlace])
Bonanzaで使われているinsertion sortとは何か？ - Bonanzaソース完全解析ブログ
■ Bonanzaで使われているinsertion sortとは何か？ Bonanzaで使われているsort(並べ替え)は、 1) insertion sort 2) shell sort 3) quick sort の3種類である。 3)はCのqsort関数を呼び出しているだけなので解説は不要だろう。また、3)は定跡データベースのメンテナンスにのみ使われており、実際の探索で使われているのは1),2)のみだ。 また、2)には1)が必要である。そこで、今回は1)について解説する。 ■ Bonanzaのnext.c Bonanzaのnext.cは、次の指し手を生成するcoroutineである。ここでinsertion sortが使われている。 指し手生成をcoroutineにしないでいきなり全部の手を生成したり、全部の手に対して点数をつけてquick sortしたりすると劇的なパフォーマンスの
コーディングに役立つ！ アルゴリズムの基本 － ＠IT
本連載ではアルゴリズムとデータ構造を学ぶ、または学び直すことで、プログラミングのスキルを深めていきます。アルゴリズムは学問として取り扱われることが多いですが、この連載では開発の現場に役立つスキルを身に付けることを目的とします。 機械学習／Deep Learningが気になる人も要注目、「アルゴリズム」の基本が学べる無料の電子書籍150ページ 人気連載まとめ読み！ ＠IT eBook（29） 人気過去連載を電子書籍化して無料ダウンロード提供する＠IT eBookシリーズ。第29弾では「コーディングに役立つ！アルゴリズムの基本」10回分を1冊のPDFとしてまとめた。アルゴリズムとは何か？ なぜ学ぶべきなのだろうか？
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
ALGORITHM NOTE 幅優先探索 Breadth First Search
幅優先探索はグラフにおける幅優先探索と同様に動作し（グラフのノードを状態とみなします）、幅広く状態変化を行います。つまり、現在の状態から可能な全ての状態変化を行い新しい状態を作ります。この探索をシステマティックに行うために、状態変化によってつくられた新しい状態をキューに追加し、探索を展開するためにキューの先頭の状態からさらに状態変化を繰り返します。一度生成した状態を再び作らないために、生成された状態を全て記録する必要があります。幅優先探索は、問題に解が存在すれば初期状態から最終状態までの最短の経路を求めます。 それでは、８パズルを幅優先探索で解いてみましょう。 プログラムの説明 以下のプログラムは、例えば 2 8 3 x 1 5 4 7 6 というような、'x' をスペースとみなしたパズルを読み込み、 ldruuldlu という、l = left, r = right, u = up, d
プログラミングのための線形代数 - 『プログラミングのための確率統計』非公式サポートページ
@@ -9,7 +9,7 @@ * [[なんでも|PSCS.Comment]] … 掲示板 !!リンク -* [[→ 公式ページへ|http://ssl.ohmsha.co.jp/cgi-bin/menu.cgi?ISBN=978-4-274-06775-4]] … シミュレーションスクリプトや補足編PDFのダウンロードなど. 詳細目次もこちらに. +* [[→ 公式ページへ|https://www.ohmsha.co.jp/book/9784274067754/]] … シミュレーションスクリプトや補足編PDFのダウンロードなど. 詳細目次もこちらに. * [[→ プログラミングのための確率統計 in Haskell|http://note.golden-lucky.net/2010/12/1-2-3-4-5-6-16-16-16-16-16-16-246-135.html]] * [[
天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
『プログラマの数学』
プログラマの数学 第2版 難しい数式は使いません。 たくさんの図とパズルにやさしい解説。 プログラミングの初心者でも、数学の苦手な人でも、楽しく読めます。 プログラミングに役立つ「数学的な考え方」を身につけよう。 第2版では「機械学習への第一歩」を新たに加筆！ 『プログラマの数学 第2版』目次 はじめに 第1章 ゼロの物語 ―― 「ない」ものが「ある」ことの意味 10進法 / 2進法 / 位取り記数法 / 指数法則 / 0の果たす役割 / 人間の限界と構造の発見 第2章 論理 ―― trueとfalseの2分割 どうして論理が大切なのか / 網羅的で排他的な分割 / 演算子で複雑な命題を組み立てる / ド・モルガンの法則 / カルノー図 / 未定義を含む論理 第3章 剰余 ―― 周期性とグループ分け 曜日クイズ / オセロで通信 / 恋人探し / 畳の敷き詰め / 一筆書き 第4章 数学的
RDBMSで使われるB木を学ぼう （1/3）－ ＠IT
第5回 RDBMSで使われるB木を学ぼう はやしつとむ アナハイムテクノロジー株式会社 2009/6/22 オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか（編集部） 第3回「AVL木で木構造を学ぼう」、第4回「もっとAVL木で木構造を学ぼう」と2回連続でAVL木について解説しました。 今回はAの後だからBというわけではありませんが、B木（B-Tree）を取り上げます。 B木の変種であるB+木やB*木は、OracleやPostgreSQL、Firebirdなどのリレーショナルデータベースでインデックスとして利用されている、メジャーな木構造です。 筆者はDelphi 2009でサンプルプログラムを作成していますが、Delphiをお持ちでない方は下記のURLからTurboDelphiをダウンロードして
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
アルゴリズムと計算量
金庫破りと計算量膨張 n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 〜 99 の 100 個の正解があるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。 99 が正解とは限らないので、平均的にはこれより早く解き終わります。 0 であるときの確率は 1/100 で、このときの手数は 1 手です。 1 であるときの確率は 1/100 で、このときの手数は 2 手です。 2 であるときの確率は 1/100 で、このときの手数は 3 手です。 3 であるときの確率は 1/100 で、このときの手数は 4 手です。 : 99 であるときの確率は 1/100 で、このときの手数は 100 手です。 つまり、平均手数は により、100 手目の約半分です。 ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計
wonderfl build flash online | 面白法人カヤック
wonderflは、サイト上でFlashをつくることのできるサービス。 通常Flashをつくるためには、Flash IDEやFlex、FlashDevelop等といったツールを使って、コードを書き、コンパイルする必要がありますが、wonderflでは、サイトにあるフォームにActionscript3のコードを書けば、サーバサイドでコンパイルを行えます。 つまり、ブラウザさえあれば、Flashをつくれます。コンパイル結果はサイト上に表示され、作成されたFlash（swf）はページ上に自動的に表示されるので、完成したFlashをリアルタイムに見ながらコードを書くことができます。 ※APIとして、はてな OpenIDを使用してネットにさえつながれば、誰もがFlashクリエイターになれます。世界中のFlashクリエイターがユーザーになるwonderflは、 文字通り、世界のFlash図鑑となってい
アルゴリズム再入門 | matarillo.com
2012-07-16 14:25:12 WEB+DB PRESS総集編［Vol.1～36］ | 技術評論社 WEB+DB Press 総集編［Vol.1〜36］に書いた記事『Webエンジニアのための基礎，徹底理解 3章：アルゴリズム再入門 C#編』を公開します。 ちなみにこの記事ではデータ構造についての話を最小限にしています。出てくるデータ構造は配列と二分木だけ。それは、データ構造については別のライターさんが記事を書くことになっていたからです。 ちなみに、書いてみたかった(というか、書いてみたけどやめた)アルゴリズムは、 ハッシュ法 (これはデータ構造の章にあります。すばらしいです) 木の探索 (traversal) 平衡木 (AVLとか) その他の有名なソート (バブルソート、シェルソート、ヒープソート、etc) Skip List (これはどちらかと言うとデータ構造メインな話なのでため
kd-tree Visualization(2) - agwの日記
先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。 繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成したkd木を可視化したものは以下のようなものでした。 同じく、木構造として可視化したものは以下のようなものでした。 さて、では何故均衡の取れない木が構築されてしまうのでしょう? 座標群の初めの点、1番の点を挿入した直後の状態を可視してみましょう。 この可視と先ほどの木構造としての可視を比較すると不均衡な木が構築される理由がより明らかとなります。木構造の可視にて1番の左側にぶら下がっている2番以下の座標群は、この可視では1番によって空間分割された領域の下側、つまり、y座標値がより小さい側に分布しています。 同様に、木構造にて1番の右側にぶら下がってい
現実の構造を分析し、それをプログラムの構造にそのまま写すのが何故いけないか - みねこあ
わたしの以前のエントリー中の 例えば、カモノハシ本 の5章では、エイトクイーンパズルを解いていますが、これは Queen オブジェクト自体に「取られない位置に進む」「この位置を自分が攻撃できるか？を答える」という責務を持たせる Queen を各列に一づつ置く 端から順にQueen に「取られない位置に進め」をさせる。 という解き方をしています。各Queen は自らの位置の解を自ら解きます。 （中略） Board というオブジェクトは必ずしも必要ないですし、連結リストの一番端には現実には存在しない「番兵」を置く場合もあります。なによりも、Queen の駒が現実で勝手に自分の攻撃されない位置を求めて動くなんてありません。（そんなチェス盤を開発してくれ、という要件ではないのです） つまり、これは現実の写像ではありません。でも良いデザインです。 憂鬱本レビューの補足 - みねこあ について、わから
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
サービス終了のお知らせ
Algorithm Database
サービス終了のお知らせ
ヒープソートのアルゴリズム
