Top > 疑問・質問 > アルゴリズムについて教えてください。

アルゴリズムについて教えてください。

アルゴリズム

一般的な用語は、アルゴリズム - Wikipediaを参照して下さい。

プログラミングのアルゴリズムは、古くから存在し、各言語はバージョンアップを繰り返しながら、言語仕様として、ライブラリとして様々なアルゴリズムを組み込んできました。そのため、基本的な「アルゴリズム」を学習しないままライブラリに存在する「アルゴリズム」を利用する、あるいは知らないまま、気が付かないまま、わざわざ別の方法でプログラミングする人も少なくありません。

事前にどんなアルゴリズムがあるか知っておくといざという時に役にたちます。

アルゴリズムは、コンピュータ言語に依存しない!

ここで紹介する「C言語によるはじめてのアルゴリズム入門」は、平成4年に初版が発行され、平成20年に3版(VS2008対応)発行ですが、内容は変わっていません。

図解入りでわかりやすい解説とアルゴリズムをC言語でシンプルなコードで構成されています。言語特有の部分はありませんので、C#の方はもちろん、VBの方にも十分利用価値の高い教本です。本書を元に.NETとの対比・補完しながら、各アルゴリズムをご紹介しましょう。なお、本書のグラフィック ライブラリは、.NET言語では使用できないため、当サイトでは、独自のライブラリを作成して検証しました。

「アルゴリズム」の基本を知り理解することで、応用範囲が広がり、ライブラリを深く知る手がかりにもなります。ライブラリにもない、プログラマーなら知っていて当然というアルゴリズムもあります。モジュール・ダウンロードはこちら


C言語によるはじめてのアルゴリズム...

ライブラリは、アルゴリズムの意味、論理、用途をある程度理解していることを前提に提供しています。クラスを使う前に、頭の中を整理するとよりベストな解決方法が見つかるでしょう。

 

目次

  • 第1章 ウォーミング・アップ
    1. アルゴリズムとは
    2. 漸化式
    3. 写像
    4. 順位付け
    5. ランダムな順列
    6. モンテカルロ法
    7. ユーグリッドの互除法
    8. エラストテネスのふるい
  • 第2章 数値計算
    1. 数値計算とは
    2. 乱数
    3. 数値積分
    4. テイラー展開
    5. 非線形方程式の解法
    6. 補間
    7. 多桁計算
    8. 長いπ
    9. 連立方程式の解法
    10. 線形計画法
    11. 最小2乗法
  • 第3章 ソートとサーチ
    1. ソートとサーチ
    2. 基本ソート
    3. シェルソート
    4. 逐次探索と番兵
    5. 2分探索
    6. マージ(合併)
    7. 文字列の照合(パターンマッチング)
    8. 文字列の置き換え(リプレイス)
    9. ハッシュ
  • 第4章 再帰
    1. 再起とは
    2. 再起の簡単な例
    3. 再起解と非再帰解
    4. 順列の生成
    5. ハノイの塔
    6. 迷路
    7. クイック・ソート
  • 第5章 データ構造
    1. データ構造とは
    2. スタック
    3. キュー
    4. リストの作成
    5. リストへの挿入
    6. リストからの削除
    7. 双方向リスト
    8. 逆ポーランド記法
    9. パージング
    10. 自己再編成探索
    11. リストを用いたハッシュ
  • 第6章 木(tree)
    1. 木とは
    2. 2分岐探索木の配列表現
    3. 2分岐探索木の動的表現
    4. 2分岐探索木の再帰的表現
    5. 2分岐探索木のトラバーサル
    6. レベルごとのトラバーサル
    7. ヒープ
    8. ヒープ・ソート
    9. 式の木
    10. 知的データベース
    11. 第7章 グラフ(graph)
    12. グラフとは
    13. グラフの探索(深さ優先)
    14. グラフの探索(幅優先)
    15. トポロジカル・ソート
    16. Eulerの一筆書き
    17. 最短路問題
  • 第8章 グラフィックス
    1. 基本グラフィックス・ライブラリ
    2. moveとturn
    3. 2次元座標変換
    4. ジオメトリック・グラフィックス
    5. 3次元座標変換
    6. 立体モデル
    7. 陰線処理
    8. リカーシブ・グラフィックスⅠ
    9. リカーシブ・グラフィックスⅡ
  • 第9章 パズル・ゲーム
    1. 魔方陣
    2. 戦略を持つじゃんけん
    3. バックトラッキング
    4. ダイナミック・プログラミング
  • 附録 VisualC++2005/2008で動作させる場合

ダウンロード

本書では、個々のアルゴリズムごとにProjecが提供(CD-ROMにて)されています。対象言語はC言語、C++となっています。そのため、C#などの.NET環境下で動作する言語は移植する必要があります。特に、グラフィックライブラリは、C++/CLI対応版も含まれていますが、互換性は全くありません。

C#への移植に際して

  1. グラフィックライブラリのインターフェイスはそのままにして、内部コードを書き換える(元々がOnPaintには対応していないため、再描画されず描画が消える場合がある)
    グラフィック初期値では、表示が荒くなるため、高画質に変更する
  2. アルゴリズムの関数は、極力ロジックを変更しないようにする
  3. 165個のアルゴリズムサンプルを一つのProjectにまとめる
  4. TreeViewから選択された項目に対応するアルゴリズム呼び出しは、Delegateで対応する
  5. 入力値を必要とするアルゴリズムは、コード変更で対応するものとする(入力機能なし)
  6. TreeViewの項目を選択して「実行」または項目ダブルクリックにて実行する
  7. 画面はフリー、レイアウトは自動追従できるようにTableLayoutPanelを使用する

実行モジュールのダウンロード

Algorithm.zip(1章、2章、8章のみ対応済み:2010/2/9)Ver 0.4

グラフィックのサンプル

実行画面イメージ

 
グラフィックは、計算しながら(点・線で)描画するようになっています。そのため、多少描画に時間がかかります。

IT@NET塾
丸山

▲ページトップに戻る