データ構造とアルゴリズム レポート課題

[12/16, 2014 H.Aman]


【注意事項】


課題 1:ソーティングアルゴリズムの実装

課題 1-1 か課題 1-2 のいずれか一つを選択しなさい.
なお,課題 1-2 は発展問題のため,課題 1-1 よりも高い評点を与える場合がある.

課題 1-1(基本問題):選択ソートの実装と実行時間測定・考察

【内容】
report1-1.c (※右クリックで保存) は選択ソートによりデータの並べ替えを行い,その実行時間を測定するプログラムである.
ただし,肝心の選択ソート実行部分(関数 selection_sort)は未完成になっている.
これを完成させ,ソースプログラム(.c ファイル)をメールで提出しなさい.

あわせて,作成したプログラムを用いてさまざまなデータで測定実験を行い,
選択ソートの平均計算量と最悪計算量が O(n^2) であることを確認しなさい.
そして,確認内容を A4 用紙 1 枚にレポートとしてまとめて提出しなさい.

【提出物:2点】

課題 1-2(発展問題):マージソートの改良

【内容】
report1-2.c (※右クリックで保存) はマージソートによりデータの並べ替えを行い,その実行時間を測定するプログラムである.

マージソートでは,データ数が 2 以下になるまでデータ列を分割する.
しかし,あまり細かいところまで分割すると再帰呼出しの回数も増大してしまい実行速度の低下が懸念される.
そこで 「データ数がある程度小さくなったところで選択ソートに切り替える」 という融合アルゴリズムを考える.
例えばデータ数が 1000 未満になったら マージソートの再帰呼び出しを行う代わりに選択ソートを実行するというかたちである.

作成したプログラムを用いてさまざまなデータで測定実験を行い, 実行速度の向上を確認しなさい.
そして,確認内容を A4 用紙 1 枚にレポートとしてまとめて提出しなさい.

【提出物:2点】

課題 2:対戦型ゲームの実装

課題 2-1 か課題 2-2 のいずれか一つを選択しなさい.
なお,課題 2-2 は発展問題のため,課題 2-1 よりも高い評点を与える場合がある.

課題 2-1(基本問題):やり直し(undo)機能と履歴表示機能の実装

【内容】
report2-1.c (※右クリックで保存) は 3x3 のゲーム盤で○×を交互に描き, 先に縦・横・斜めのいずれかを揃えた方が勝ちという簡単なゲームプログラムである.
(※表示の都合上,○ として @ を,× として X を用いている)

現時点で一通りゲームを実行できるが,「待った」をかけることができない.
※「待った」をかけると,直前のコンピュータの手と自分の手をそれぞれ一手ずつ 「無かったもの」としてやり直しできる.
つまり,直前の自分の番の状態まで戻すという機能である.

また,ゲーム終了時点で「お互いにどういう手を打ったか」という履歴も表示させたい(下の例を参照)がその機能も実装できていない.
(履歴の表示例)
3 に○
5 に×
2 に○
9 に×
1 に○

上のプログラムを完成させなさい.
プログラム中には「この部分は自分で作ること」という部分が 3 箇所用意されている.
その他の部分も自由に改変してよい.
※スタックの実装については情報工学実験 I の資料を参照のこと

【提出物】

課題 2-2(発展問題):コンピュータの強化

【内容】
課題 2-1 のプログラムにおいて, コンピュータは次の一手をランダムに決めている.
これを自分なりに工夫して,コンピュータがより賢く次の一手を打つように強化しなさい.

※課題 2-1 の機能も実装すること.

【提出物】