2013/06/18の授業中に説明した有限オートマトンのプログラムをもとに、有限オートマトン（ミーリーマシン）を実装せよ。
(A)出力関数は遷移関数と同様に配列で表現すること。出力関数の配列名は toutput とすること。
(B)遷移時に、出力記号だけではなく、元状態と次状態、入力文字を表示すること。
上記ミーリーマシンにおいて、初期状態を「状態0」として、２クロック遅延マシンを考案し、実装すること。
参考：１クロック遅延マシンについては授業中の説明参照（wikipediaにも説明あり）
２遅延の出力が始まってからは全ての状態を受理状態とする。
入力文字は半角の0,1の２文字種のみとする。
入力はキーボードから受け付けるものとする。
２遅延であることが見やすくなるよう、元状態・次状態・入力文字・出力文字のレイアウトには気を使うこと。
入力として認められない文字種が入力された場合は、その旨表示して終了すること。
| 【状況】 | 【指示】 |
| 誰かに教えてもらった場合 | その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。
（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。） |
| 誰かに教えてあげた場合 | その学生（氏名・学籍番号）をプログラム先頭に記すこと。 |
| お互いに相談した場合 | お互いの氏名・学籍番号を、教えてもらった・教えてあげたの例に準拠して提出してください。 |
1000円未満の指定金額の支払いにおける硬貨枚数最小化問題について、10進数で桁ごとに分割し、それぞれの桁でGreedyアルゴリズムでの硬貨枚数最小化を考える。
下記の３種類の貨幣体系について、上記の分割アルゴリズムとその統合が、全体の貨幣枚数最小化と一致するかどうか、理由とともに説明せよ。
(1) 500, 100, 50, 10, 5, 1 円硬貨
(2) 500, 200, 100, 50, 20, 10, 5, 2, 1 円硬貨
(3) 800, 100, 80, 10, 8, 1 円硬貨
(4) 800, 400, 200, 100, 80, 40, 20, 10, 8, 4, 2, 1円硬貨
授業中に示した、ナップサック問題を最長経路問題に変換するアルゴリズムについて、 最長経路問題を解くプログラムにグラフ情報を与えられるように、隣接行列を出力するプログラムを作成せよ。
実行結果を示すためには、下記のナップサック問題事例でプログラムを提出すること。
隣接行列は、経路が無い場合は-1ないしNLと表記すること。
隣接行列は、標準出力（ないしテキストファイル）に出力すること。
隣接行列の見やすさに配慮してあるほうがよい。
#define WL 10 // Weight Limit
#define N 5 // Number of objects
struct {
int v; // value
int w; // weight
} obj[N] = {
{ 11, 7},
{ 3, 2},
{ 9, 5},
{ 13, 8},
{ 5, 3}
}; |
