大学時代にライフゲームには熱中した思い出がある。理系の人間には馴染んでいる人が多いのでは。
鈴木一史。配列の応用。アルゴリズムとプログラミング。コードも複雑になる。前回は配列の操作。挿入削除探索など。配列を利用した線形探索など。配列を使った応用的なコード。スタックとキュー。C言語を利用した。コードの応用例としてコンウェイのライフゲームについて。
スタックとキュー。計算機科学の教科書などで出てくる。スタック。色々な場面で。データ構造のスタック。非常に簡単に言うとデータ保持の形式。様々だがスタックは基本的。積み重ねる、の意味。積み重なったデータ。一つしか読み込めない。最後に積まれたものだけ。複数のデータが積まれていると底になり頂上になる。概念的なもので縦方向に積んでいるがどんな方向でも良い。一般には縦方向に。スタックのデータ構造は後入先出。構造においてデータは後入先出で。基本的操作。プッシュ。データを頂上に積む。ポップ。データを頂上から除く。他の補助的なものも。ピーク。頂上のデータを削除せずに値を見る。スワップ。頂上にあるデータと次のデータを入れ替える。ダップ。複製。スタック頂上を複製してプッシュ。逆ポーランド記法が利用できる関数電卓で。数値などがスタック構造で保存。スタックの構造は配列を使って実装。様々な実装法がある。スタックの構造を実現した具体例。プッシュポップの主要操作などが関数として実現。このコードでは添字の情報を渡して実現する構造に。グローバル変数として。配列を利用した実装では容量が超える場合の処理などを考慮する必要がある。メインの関数。蓄える配列の宣言。添字となるトップ。データという変数。スタックをスタックユニットという関数で。結果はコードの出力に。データがプッシュされポップされる。関数内で静的にスタックが確保されている。動的なメモリ配列ならサイズが大きいものが。大変重要で関数の呼び出しなどに利用される。そこにメイン関数が。その上に呼び出された関数。アルゴリズムには利用例が沢山ある。
キュー。待ち行列。列に並んで待つ。基本的なデータ構造。最初に挿入したデータが最初に取り出される。キューの構造。スタックの図と比較する。既にキューに複数のデータが。先頭フロント。最後はキューの末尾リア。キューのデータ構造は先入れ先出し。FIFO。データは先入先出で保存。エンキュー。列に加える。可列、末尾に。デキュー。先頭からデータを取り出す。ピーク。キューの先頭のデータを見る。キューの末尾などを見る派生型も。コードの言語。整数型変数を格納。C言語。エンキューとデキューと初期化。キューの先頭と末尾を見る関数が。単純な実装では先頭と末尾の位置関係から大きな行列が必要。環状バッファが。メインの関数。キューのデータを保存する整数型の。添字をフロント。リア。キューを初期化する関数が呼ばれてその後にエンキューが5回。順番に。キューが空になるまでデキューを。プログラムの出力。データの表示。キューは一時的に蓄える。様々なアルゴリズムで使用。計算機科学で重要なもの。覚えておくこと。配列を利用して実装が可能。配列を関数に渡すには。
配列の応用。実装例を。ライフゲームと呼ばれるものの実装。欧米などの大学のプログラムの宿題に。70年にコンウェイ博士が。セルオートマトン。例として有名。動きがないが主要な動画の例を。検索をすればライフゲームが分かる。二次元の正方形のセルで分割された無限の。生きているか死んでいるか。各セルの状態は時代ごとに変化。近傍にあるセルの状態に依存、セルに接している水平垂直斜めの8つの。ムーア均某。ライフゲームはどんなものか。初期のセルの配置は第1世代。第2世代目はセルの状態と規則による。規則は同時に実行。生きているセルに隣接する生きたセルが2つより少ない時、セルは死滅する。孤独死。生きているセルに隣接する過密状態での死。生きているセルに隣接するセルが2つまたは3つのときは生存する。死んでいるセルに隣接した生きているセルが３つのときにセルが誕生。ライフゲームの規則は派生版も。規則によっては数世代で死ぬ。空間が生きているセルで埋まるもの。標準的規則ではバランスが取れるほうに。様々な変化が。消滅の例。セルが死滅。振動の例。２世代の周期で。幾つか例があるが周期は異なる。長い周期のものの。ブリンカー。点滅信号機。固有の名前が。固定。生物。４つのセルの配置から正方形。変化せず。グライダー。滑空機。グライダーは４世代ごとに１つ移動。パターンが同じ。グライダーが右斜め下などに。滑空しているように。コンピュータ・プログラムとしてセル状態を保存する必要がある。限定すれば容易に実装が可能。初期化。規則の実行や表示。関数として表現できる。ライフゲームを作れる。欧米の大学のプログラミングでよく使われる。ライフゲームのコード例。長めのコードだがセル状態の初期化などの機能を関数で。セルオートマトンの特徴。同期性。更新前と更新後の状態を保存する2つの関数が。2つの配列が使われる。コードの実行例。世代0。単純に乱数を使ってランダムに配置。コードを変更して特定のセルパターンを。世代1。セルパターンでは孤立しているセルは死滅する。同様の繰り返し処理。新たに生まれたり現状維持したり死滅したりして世代が進む。四角形が観察されるなど。世代が進んでも変化がない。しかしグライダーがぶつかれば別。世界的人気があり様々な言語で実装。拡張版も多い。動画サイトで検索すればアニメーションが。データベース化したサイトも。ただ単にアニメーションの面白さだけでなく学術的な研究も。書籍も多い。
演習問題。スタックの重要な操作。プッシュとポップ。プッシュは積む。ポップは取り出す。キューの重要な操作。エンキューとデキュー。エンキューは列の末尾に。デキュー。先頭からデータを取り出す。スタックの5つのデータを順にプッシュすると。ポップを3回すると頂上は？スタックの構造を理解。最初のデータが底に。最後が頂上に。スタックの図を描くと分かりやすい。キューのデータ構造では先入れ先出し。エンキューするとキューの先頭データや末尾データ。先頭にあるデータは？キューについてエンキューとデキュー。キューの図を描く。キューの主要な操作について。チャレンジ問題。難易度が高い。回答例は補助教材で。連関バッファ。添字の大きさを。直線バッファが繋がり円環状に。リングバッファ。配列の添字を。色々な解法のコードが。ライフゲームの出力を。開発環境に依存。エスケープシーケンスによる制御が問題。スナップショット。ライフゲームで世代ことに。Linuxの例。グラフィックスライブラリーを使うのも面白い。
配列を使った応用的なコード例。スタックとキューの構造。C言語による配列を利用した実装例。スタックではプッシュ。頂上に積む。ポップ。データを頂上から取り出す。ピークなどが。ピークは頂上のデータを見る。スワップ。ダップ。スタック頂上を複製。スタックの操作を行う問題は試験にも。キュー。エンキューとデキュー。エンキュー。データをキューの末尾に。デキュー。先頭からデータを取り出す。これらは計算機科学に重要。配列と関数を利用したコードの応用例。ライフゲーム。各セルは生きているか死んでいるか。世代ことに変化。コンピュータ・プログラムとして実装するには二次元配列をして実装。セル空間の初期化や規則の実行。表示などは関数として実装。最初の世代のセルを特定の配置にしたりして色んな応用が可能。規則の変更も。コードの改良を。ファイル。コードではデータ入力をキーボードで。標準入力で、C言語でファイルを扱う。読み込みや書き込み。データを読み込む。ファイル形式や仕組み。画像ファイルのデータをメモリに読み込み処理して画像ファイルに書き出す。ファイルを自由に扱えるとプログラミングが楽しめる。
