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

• 課題 1： ソーティングアルゴリズム
• 課題 2： 対戦型ゲーム

【注意事項】

• 課題 1, 2 とも必修とする．

• 提出に際してメールアカウントは学外のものを用いてもよいが，
  こちらから受領確認の返事を出すので必ず届くようアドレスの設定には注意すること．

• 提出〆切は 1/31（土）24 時とする．

• 他の受講生と酷似した（コピーしたとしか考えられない） レポートやプログラム
  を提出してきた場合は，後から提出された方を 0 点にする．

• リンク先のプログラムはいずれも Linux 上で作成したものである （文字コードは UTF-8 ）
  文字化けするときは表示の文字エンコーディングを UTF-8 に変えてみるとよい．

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

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

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

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

• プログラム（ソースコード）
  メールの「添付」で提出 （提出先アドレス aman ＠ ehime-u.ac.jp）

  件名（subject）には，学年・番号・氏名・課題名を書くこと：
  （例）2 年生 99 番 愛大 太郎が課題 1-1 を提出する場合 2/99/愛大 太郎/1-1

  必ずこちらからの返事を確認すること． 明らかな誤りがある場合，そのままだと０点になるので再提出を指示することがあります．

• レポート（A4 で 1 枚にまとめる；表紙不要；裏表に書いてよい）
  印刷して提出する場合は 講義時に手渡しするかメディアセンター 2 階 208B （階段を出て左手にぐるっとコの字形に回り込んだ奥） まで持参すること
  メールで提出する場合は プログラムと一緒に添付ファイルで提出すること． 形式は PDF か Word が望ましい．

課題 1-2（発展問題）：マージソートの改良

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

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

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

• プログラム（ソースコード）
  メールで提出 （提出先アドレス aman ＠ ehime-u.ac.jp）

  件名（subject）には，学年・番号・氏名・課題名を書くこと：
  （例）2 年生 99 番 愛大 太郎が課題 1-2 を提出する場合 2/99/愛大 太郎/1-2

  必ずこちらからの返事を確認すること． 明らかな誤りがある場合，そのままだと０点になるので再提出を指示することがあります．

• レポート（A4 で 1 枚にまとめる；表紙不要；裏表に書いてよい）
  印刷して提出する場合は 講義時に手渡しするかメディアセンター 2 階 208B まで持参すること
  メールで提出する場合は プログラムと一緒に添付ファイルで提出すること． 形式は PDF か Word が望ましい．

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

課題 2-1（基本問題）：やり直し（undo）機能と履歴表示機能の実装

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

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

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

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

• プログラム（ソースコード）
  メールで提出 （提出先アドレス aman ＠ ehime-u.ac.jp）

  件名（subject）には，学年・番号・氏名・課題名を書くこと：
  （例）2 年生 99 番 愛大 太郎が課題 2-1 を提出する場合 2/99/愛大 太郎/2-1

  必ずこちらからの返事を確認すること． 明らかな誤りがある場合，そのままだと０点になるので再提出を指示することがあります．

課題 2-2（発展問題）：コンピュータの強化

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

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

• プログラム（ソースコード）
  メールで提出 （提出先アドレス aman ＠ ehime-u.ac.jp）
  

  件名（subject）には，学年・番号・氏名・課題名を書くこと：
  （例）2 年生 99 番 愛大 太郎が課題 2-2 を提出する場合 2/99/愛大 太郎/2-2

  必ずこちらからの返事を確認すること． 明らかな誤りがある場合，そのままだと０点になるので再提出を指示することがあります．