水の移し替えパズル in Scheme DouKaku?

A, B, Cの容器があり，それぞれ水が4L, 2L, 10L入っている．ここで次の操作を繰り返す．

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ，残りの容器に移す．」

たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる．くみ上げる前の容器には必ず水が入っているとする．

(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ．

可能ならA=827392L，B=65536L，C=122880Lのときも求めよ．

このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。

うーん、最小であることの証明が出来ていないのですが、この手数で出来ることは間違い有りません。

結果：
 $ gosh 73.scm
10
827392
 $ fg

(define (wp n . l)
  (let1 sl (sort l)
    (cond ((= (caddr sl) (cadr sl)) (+ n (cadr sl)))
          (else (wp (+ 1 n) (+ (car sl) 2) (- (cadr sl) 1) (- (caddr sl) 1))))))

(print (wp 0 4 2 10))
(print (wp 0 827392 65536 122880))

自己フォロー
1 2 3
みたいな数列だと、先ほどのコードだと停止しません。
答えがないので仕方ないとも言えますが、悔しいので、過程の再出現の時点で「n/a」と返すコードを書いてみました。
全ての変遷の履歴を持ち、チェックする為、2番目の例だとなかなか計算が終わりません。

実行結果：
 $ gosh 73.scm
(4 2 10) -> 10
(1 2 3) -> n/a
 $

(define (wpz . l)
  (display #`",l -> ,(apply wp () l)\n"))

(define (wp n . l)
  (let1 sl (sort l)
    (cond ((= (caddr sl) (cadr sl)) (+ (length n) (cadr sl)))
          ((member sl n) "n/a")
          (else (wp (cons sl n) (+ (car sl) 2) (- (cadr sl) 1) (- (caddr sl) 1))))))

(define (main args)
  (wpz 4 2 10)
  (wpz 1 2 3))

DouKaku?

水の移し替えパズル

Posted feedbacks - Scheme

Index

Feed

Other

Link

Pathtraq