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

課題の提出

• 提出期限
  2008/06/10 (Tue), 08:30 JST
• 提出方法
  Web CTから提出
• 条件
  「必修」課題は全て提出してください。
  「発展」課題の提出は任意です。
  （「発展」課題を出さなくともＡ評価になる可能性はありますが、確実に目指すのなら「発展」課題をするほうがよいでしょう）
  

課題３

• ★必修：課題３ａ★

  安定結婚問題を解くプログラムを、授業で配布した資料のアルゴリズムに基づいて実装し実行せよ。
  （もとの資料はUCBの下記の頁にある。必要であれば各自で参照のこと。）
  http://www.cs.berkeley.edu/~jfc/cs174lecs/lec7/lec7.html
  

  • Preference orderの例０
  • Preference orderの例１
  • 例０の実行結果のサンプル（実行がこの順である必要はない）
  • 例１の実行結果のサンプル（結果・実行がここにある通りになる必然性はない）

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

  • 提出物〔3a-1〕：Ｃソースファイル（コメント必須）
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    Prefererence Orderの配列については、例０を読み込む状態のプログラムになっていること。 プログラム中の変数（配列含む）については全て１つずつ説明をつけること。
    

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

    プログラム先頭の様子

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

  • 提出物〔3a-2〕：Preference Orderの例０に対する出力結果を保存したテキストファイル
    出力例を例０に示していますが、結果が正しいとわかる形式であれば、例に従う必要はありません。

  • 提出物〔3a-3〕：Preference Orderの例１に対する出力結果を保存したテキストファイル
    出力例を例１に示していますが、結果が正しいとわかる形式であれば、例に従う必要はありません。

• ★必修：課題３ｂ★

  求婚アルゴリズムがDisasatisfied pairを作ることなく全員のペアを作れることを証明せよ。

  • 提出物〔3b-1〕：テキストファイル
    プレーンテキスト（拡張子 .txt）で提出すること。
    

• ◆発展：課題３ｐ◆

  ある結婚状態（全員がペアになっている状態）において、Disasatisfied pairが存在しないことを検証するプログラムを作成・実行せよ。課題３ａと組み合わせてよい。
  ソースコードは例０に対する実行時のものだけでよい。
  

  • 提出物〔3p-1〕：Ｃソースファイル（コメント必須）
    Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
    プログラム中の検証に関わる部分を明示し、十分なコメントをつけること。
    他の注意点については〔3a-1〕に同じ。

  • 提出物〔3p-2〕：課題３ａの例０で作成した結婚状態に対する出力結果を保存したテキストファイル
    出力例を例０に示していますが、結果が正しいとわかる形式であれば、例に従う必要はありません。
    《“Reference: marriaged pairs”以下の行は左から検証する既婚２組 (P,Q) (R,S)でそれぞれ(男,女)の順。続くP(男)---S(女) R(男)---Q(女)が不安定状態かどうかを示す（不安定状態なら-x-,安定状態なら---で関係を表示）。》

  • 提出物〔3p-3〕：課題３ａの例０で作成した「以外の」結婚状態に対する出力結果を保存したテキストファイル
    注意点は3p-2と同様です。