情報知能工学演習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があるか? あれば，そのような自然数の列を答えよ．

N = X1 + X2 + … + XM
1≦K≦N なる各自然数 K について，以下を満たす整数 I, J (1≦I≦J≦M) が存在する．
K = XI + XI+1 + XI+2 + … + XJ

課題問題は以下の通りです．ヒントが欲しい場合は，どんどん田村 (tamura@seg.kobe-u.ac.jp) まで質問してください．

問題:
与えられた自然数 N, M (N≧2, 1≦M≦N)について，上の条件を満たす自然数のリスト [X1, X2, ..., XM] を L に返す述語 measure(N, M, L) を定義しなさい．解がある場合には，少なくとも一つの解が返されればOKとします． CPU時間の短いものほど良い成績としますが，もちろん答えがそのまま書いてあるプログラムは不可．

例:

ゴール	答
measure(6, 2, L)	no
measure(6, 3, L)	L=[1,3,2] など
measure(9, 3, L)	no
measure(9, 4, L)	L=[1,1,4,3] など
measure(13, 4, L)	no
measure(13, 5, L)	L=[1,1,4,4,3] など
measure(17, 5, L)	no
measure(17, 6, L)	L=[1,1,1,5,5,4] など

ヒント:
「探索問題」の「整数の分割」を参考にすると良いでしょう．

自分でCPU時間を計りたい場合は，以下の述語を使ってみてください．


    runtime(G) :-
        statistics(runtime, _),
        call(G),
        !,
	statistics(runtime, [_,T]),
	write('CPU時間 '), write(T), write(' ミリ秒'), nl.
    runtime(_) :-
	statistics(runtime, [_,T]),
	write('CPU時間 '), write(T), write(' ミリ秒'), nl, fail.

使い方は，以下の通り．


     ?- runtime(measure(6, 2, L)).

注意!
残留プロセスには注意してください． winterm 中で top と入れると，CPUを多く使っているプロセスの一覧が表示されます．無駄なプロセスは，すぐに kill してください．
参考:
- 目盛の消えたものさし (PDF 36Kバイト)
- 田村三郎，藤村幸三郎「パズル数学入門」講談社ブルーバックス
- 小谷善行「マイコンパズル学入門」廣済堂産報出版
- 目盛の消えたものさしとは違いますが，良く似ているゴロム定規について
  - 最短ゴロム定規（OGR)とは？
  - プロジェクトOGR
  - Golomb Ruler (Wikipedia)
  - Golomb rulers (CSPlib)

課題(第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