＝＝＝課題６＝＝＝ 受付開始日時 2015-06-02 11:30 受付終了日時 2015-06-08 18:00 閲覧設定 提出者本人と教員のみ閲覧・コメント可（個別指導） 学生による再提出の許可 再提出を許可する ●必須課題6-1 [記述(pdf)] Stable Marriage 課題に関する説明 ・Stable Marriage問題において、各個人の幸せ度を、その個人からみて何番目に好きな相手と結婚できたかで定義するとします。 （例えば、Ａ君が、３番目に好きなｃさんと結婚した場合は幸せ度３とします。） ・Ｎ人ずつ（全体で２Ｎ人）の安定結婚状態において、幸せ度の平均を採ることを考えます。 ・幸せ度平均の最良値を与える状況を説明し、その値をＮを使って示しなさい。 ・幸せ度平均の最悪値を与える状況を説明し、その値をＮを使って示しなさい。 ・先頭に学籍番号・氏名・課題番号を示すこと。 ●必須課題6-2 [プログラム(zip)] Knight Tour と Knigt Tour Round 課題に関する説明 ・Knight tourの解のうち、最終位置から一手で開始位置に戻れる解を、Knigt tour の round解と呼ぶことにします。 ・授業中に示したKnight Tourを解くプログラムについて、完成させるとともに、以下の改良を施しなさい。 →Knight tour解が得られたときに解の総数を数え上げ、かつその時の解を表示する answercheck() を作成すること。 →Knight tour解が round解 であるかどうかを確認し、round解の数を数え上げ、かつ解を表示できるように answercheck()を改良すること。 →main関数側で、解の探索に掛かった時間をミリ秒の単位まで計測し、終了時に盤のサイズ、開始座標、knight tour解数、round解数とともに表示すること。 ・実際に得られたknight tour解の例をresult-tour.txtファイル中に３つ示すこと（最初の３つでもなんでもよいが、必ず３つだけとする）。 ・実際に得られたknight tour round解の例をresult-round.txtファイル中に３つ示すこと（最初の３つでもなんでもよいが、必ず３つだけとする）。 ・開始座標は(0,0)とする。 ・Knightの移動方向８か所のリスティングは好きな順でよい。 ・提出プログラムでは 盤のサイズの横NX=6, 縦NY=6とすること。 ・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。 ・グラフは授業中で説明したものをベースにすることこと。 ・プログラムで工夫した部分について、プログラムソースの何行目付近を確認してほしいか明記し（複数場所可）、其々の場所では何かしらの説明をコメントの形でプログラム中に書き込むこと。 ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 ◇発展課題6-A [プログラム(zip)] 開始点を変えた場合の Knight Tour 課題に関する説明 ・課題6-2で完成させたプログラムについて、さらに以下の改良を施しなさい。 ・盤上のいずれのマスも開始点として、それぞれについての解の数を求められるようにしなさい。 ・Knight Tour, Knight Tour roundの両方の解の数を求めなさい。 ・出力として、下記のような行が、マス数だけ(NX=6,NY=6であれば36行)必要ということになります。 　（出力形式はこの通りでなくても構いません） 　（下記例では数値は正しくありません） Start (0, 0): tour = 12345, round = 12, time = 12.334 [sec] Start (0, 1): tour = 445, round = 12, time =222.334 [sec] ・NX=6, NY=6として提出しなさい。 ・プログラムソースの先頭に、学生番号、氏名、課題名をコメントで記入すること。 ・結果は result.txt に保存すること。 ・プログラムで工夫した部分について、プログラムソースの何行目付近を確認してほしいか明記し（複数場所可）、其々の場所では何かしらの説明をコメントの形でプログラム中に書き込むこと。 ・高速化のために、対称性等を用いても構いません。その場合はプログラム中の説明を丁寧にすること。 ・Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。 ⇒誰かに教えてもらった場合：その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を独自の説明で数行以上書き込むこと。 （教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） ⇒誰かに教えてあげた場合：その学生（氏名・学籍番号）をプログラム先頭に記すこと。 ⇒お互いに相談した場合：お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 ◇発展課題6-B [記述(pdf)] Knight の移動方向の定義 課題に関する説明 ・発展課題6-Aにおいて、Knightの移動方向８か所のリスティングを適当に入れ替えたとき、result.txtの中の値のうち、変化する項と変化しない項を挙げ、その理由を簡単に説明しなさい。 ・リスティングを適当に入れ替えたとき、発展課題6-Aの総実行時間に変化があるはずかどうか、議論しなさい。理由の説明を試みること。 ・実際にリスティングを２回変更して（もともととあわせて３回）、上記２つの予想がそれぞれ結果と一致しているかどうかを確認しなさい。