情報知能工学演習VI: Prolog 課題問題(第2回)

Last modified: Tue Jan 16 16:19:06 2007 JST

課題問題(第2回)

色々考えたのですが, 結局「目盛の消えたものさしのパズル」にしました.

1cmきざみで目盛のついている長さ6cmのものさしがあります. ところが,下のようにいくつかの目盛が消えて, 間に2つしか目盛が残っていません.

     +-----------------------------+
     |                             |
     |    |              |         |
     +----+--------------+---------+
     0cm  1cm            4cm       6cm
でも,このものさしがあれば,1cm から 6cm まで計れるのです.
0cm と 1cm の間で,1cm
4cm と 6cm の間で,2cm
1cm と 4cm の間で,3cm
0cm と 4cm の間で,4cm
1cm と 6cm の間で,5cm
0cm と 6cm の間で,6cm

目盛の間の長さのリストで表すことにすれば, このものさしは [1,3,2] というリストで表すことができます. この場合,以下のようになっているので,1cm から 6cm まで計れるといえます.

1cm = 1 (リストの1番目)
2cm = 2 (リストの3番目)
3cm = 3 (リストの2番目)
4cm = 1 + 3 (リストの1〜2番目の和)
5cm = 3 + 2 (リストの2〜3番目の和)
6cm = 1 + 3 + 2 (リストの1〜3番目の和)

したがって,このパズルを一般化した問題は,次のようになります.

目盛の消えたものさしのパズル:
与えられた自然数 N, M (N≧2, 1≦M≦N)について, 以下の条件を満たす自然数(1以上)の列 X1, X2, ..., XMが あるか? あれば,そのような自然数の列を答えよ.
課題問題は以下の通りです. ヒントが欲しい場合は,どんどん 田村 (tamura@seg.kobe-u.ac.jp) まで質問してください.

課題(第2回目)の提出

上記の課題問題の解答プログラムを 説明つきで単一のファイルとして作成し, 以下のコマンドで提出しなさい (説明はプログラム中にコメントの形で記述すること). また,Prolog演習についての感想も コメント中に記述しなさい. なお,解答プログラムは必ずEUC文字コードで作成すること (でないと実行ログファイルが文字化けする). Mule中で,EUC文字コードを選択するには, 「C-x C-k f」として *euc-japan* と入力すれば良い.
提出期限は12月1日(火). 期限を過ぎたものは不合格とする. 同じプログラムを提出した者は全員不合格とするので注意すること (変数名だけが異なるプログラムなども同一とみなす). また,CPU時間が短いものほど良い点をつける. また,提出期限以前なら何度でも提出できるので, 早い機会に一度提出の練習をしておくこと. 最後に提出したものだけが有効になる. うまく提出できない場合は,田村まで連絡してください.

     % rlogin jube
     % cd 解答プログラムのあるディレクトリ
     % submit2 解答プログラムのファイル名
提出コマンド submit2 の詳しい説明は,以下のようにすれば表示されるので, 必ず見ておくこと.

     % submit2
「submit2 -l」で提出者一覧(学番順),「submit2 -L」でCPU時間順の一覧が 表示される.
Naoyuki Tamura