授業中に説明したKnight's Tour（騎士の巡礼）の解を求めるプログラムを用いて、チェス盤のサイズが６×６の場合の解の数を求めよ。
起動時の引数でスタート地点を指定できるようにプログラムを改良すること。
スタート地点としてx >= y を満たす全ての地点で、解の数をそれぞれ求めること。（２１地点）
（２１回プログラムを実行することになる。）
（５階計算機は折角のマルチコアなので、システムモニタ等を見て複数同時実行させましょう。）
騎士の８方向の移動順は、下記の通りとすること。
| int move[M][2] = { { 2 ,1},{ 1, 2},{-1, 2},{-2, 1},{-2,-1},{-1,-2},{ 1,-2},{ 2,-1} }; |
| 【状況】 | 【指示】 |
| 誰かに教えてもらった場合 | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。
（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合 | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合 | お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 |
| (0,0) 解の数
(1,0) 解の数 (2,0) 解の数 ... (5,0) 解の数 (1,1) 解の数 (2,1) 解の数 ... (5,5) 解の数 |
2013/6/4の授業中に説明したN-Queens問題の全解候補の数え上げ方式A(全組み合わせ), B(縦方向の制約を考慮), C(横方向の制約を考慮)について、N=8において
【説明】A/B/Cでの数え上げ方法を説明せよ。
【立式】A/B/Cの解数を求める式を示せ。
【数値】A/B/Cの解数を数値で示せ。その求め方も述べること。なお、正確な数値が求められない場合は、10のk乗という近似でもよい。その場合も導出を示せ。
※立式まで解答があれば合格最低点は配する。
(2013/6/10, N=8を明記)
【ループ回数】課題3Aの実施において、最内側のループの実行回数を表示できるように改良しなさい。
int型 / long int型では桁あふれを生ずるのでそのままではカウントとして利用できないことに注意する。
プログラムの実装として、カウンタは予想される最悪回数 (8^(6*6)) を表現できるようにすること。その仕組みをコメント行で説明すること。
【実行時間】課題3Aの実施において、実行時間を表示できるように改良しなさい。
ミリ秒オーダーまで計測するプログラム例を参考にすること。
ループ回数、実行時間は異なるスタート地点毎に計測すること。
システムモニタなどを確認して、マルチコアの全スレッド以上に同時実行しないように注意する。
単位時間当たりのループ回数がスタート地点によって異なるかどうかを計算して、その結果について述べなさい。
相談等した場合の対応は3A-1に準拠すること。
| (0,0) 解の数 ループ回数 実行にかかった秒数 単位時間あたりのループ回数
(1,0) 解の数 ループ回数 実行にかかった秒数 単位時間あたりのループ回数 (2,0) 解の数 ループ回数 実行にかかった秒数 単位時間あたりのループ回数 ... (5,0) 解の数 ループ回数 実行にかかった秒数 単位時間あたりのループ回数 (1,1) 解の数 ループ回数 実行にかかった秒数 単位時間あたりのループ回数 (2,1) 解の数 ループ回数 実行にかかった秒数 単位時間あたりのループ回数 ... (5,5) 解の数 ループ回数 実行にかかった秒数 単位時間あたりのループ回数 |