第四回課題：データ構造とアルゴリズム（２００９）

データ構造とアルゴリズム, 授業科目, www.kameda-lab.org 2009/06/15a

課題の提出

提出期限
2009/06/18 (Thu), 18:00 JST 【WebCT設定にミスがあったので締切を約２日延期しました】
提出方法
Web CTから提出
条件
「必修」課題は全て提出してください。
「発展」課題の提出は任意です。
（「発展」課題を出さなくともＡ評価になる可能性はありますが、確実に目指すのなら「発展」課題をするほうがよいでしょう）

課題４

★必修：課題４ａ★

授業中に説明したKnight's Tour（騎士の巡回）の解を求めるプログラムを用いて、チェス盤の１辺Nが5と6の場合について、経路の数を求めよ。スタート地点は(0,0)とする。また、そのときの時間計算量（制御ループの一番内側のif文の評価回数で表すものとする）を、桁あふれがないように注意しつつ求めよ。

以下のものを提出してください。

提出物〔4a-1〕：Ｃソースファイル（コメント必須）
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。

【注意】
誰かに教えてもらった場合：	その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。）
誰かに教えてあげた場合：	その学生（氏名・学籍番号）をプログラム先頭に記すこと。
お互いに相談した場合：	教えてもらった・教えてあげたの例に準拠して提出してください。

プログラム先頭の様子

// 課題3 (3a-1) 
// 提出者 012345678 筑波 薫 【←学籍番号、氏名】
// 教わりました： 112233445 優秀 秀雄, 554433221 秋葉原 命
// 教えてあげた： 998877665 学園 友近
//
#include <stdio.h>
#define N 8
...

提出物〔4a-2〕：プログラムの出力結果を保存したテキストファイル
N=5, N=6の両方について、解の数と、時間計算量の評価回数、それに実行時間を示すこと。
なお、Ｌ棟５階計算機室以外の計算機を用いた場合はそのスペックも付記すること。
提出物〔4a-3〕：時間計算量を測定するための評価回数カウントに関する工夫を述べたテキストファイル
N=5, N=6の両方について、解の数と、時間計算量の評価回数、それに実行時間を示すこと。
時間計算量は通常のint型を超える可能性に対して、プログラム上どのように工夫して桁あふれがないようにしているかを説明する。
必要であれば、ソースプログラムの一部を引用してよい。

★必修：課題４ｂ★
Closed Knight's Tour（騎士の周遊）とは、Knight's Tourに加えて、経路の最後のマスからスタート地点に１手で戻れる経路を求める問題である。チェス盤の１辺Nが5と6の場合について、この条件を満たす経路の数を求めよ。また、実行時間も示せ。
- 提出物〔4b-1〕：Ｃソースファイル（コメント必須）
  Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
  改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
  その他の注意点は〔4b-1〕に準ずる。
- 提出物〔4b-2〕：プログラムの出力結果を保存したテキストファイル
  N=5, N=6の両方について、解の数と、時間計算量の評価回数、それに実行時間を示すこと。
  なお、Ｌ棟５階計算機室以外の計算機を用いた場合はそのスペックも付記すること。
- 提出物〔4b-3〕：時間計算量の見積もりに関する考察を述べたテキストファイル
  騎士の周遊(課題4b)は騎士の巡回(課題4a)と比較して、時間計算量はどのようにとらえられるか説明せよ。

◆発展：課題４ｐ◆

下記に示すチェス盤では、移動できる部分をoで、移動できない部分をxで示している。このようなチェス盤に対する Closed Knight's Tour の解の総数を求める問題に対して、時間計算量を見積もった上で、プログラムを実行し、解の総数と時間計算量（評価回数）を求めよ。また、得られた結果と時間計算量の見積とのずれの理由を考察せよ。

提出物〔4p-1〕：テキストファイル
各マップごとに、経路数、時間計算量（if文の評価回数）、および解の例を３つ以上（どれでもよい）含めること。
そのあとで、時間計算量の見積もり方法について述べ、実際の値とのずれの理由について記せ。

課題に利用するマップ

マップG マップJ マップM マップN マップZ

o o o o o o x x
o o o o o o x x
o o o o o o x o
x o o o o o x x
x o o o o o o x
x o x x x x x x
x x o o o o x x
o x x x x x x x

o o o o o o x x
o o o o o o x x
o o o o o o x o
o o o o o o x x
o o o o o o o x
x o x x x x x x
x x o o o o x x
o x x x x x x x

o o o o o o x x
o o o o o o x x
o o o o o o x o
o o o o o o x x
o o o o o o o x
x o x x x x o x
x x o o o o x x
o x x x x x x o

o o o o o o o o
o o o o o o o o
o o o o o o o o
o o o o o o o o
o o o o o o o o
x x x x x x x x
x x x x x x x x
x x x x x x x x

o o o o o o o o
o o o o o o o o
o o o o o o o o
o o o o o o o o
o o o o o o o o
x x x x x x x x
x x o o o o x x
x x x x x x x x

kameda[at]iit.tsukuba.ac.jp