パズル (バケツを空に)

 投稿者:山中和義  投稿日:2011年 8月28日(日)19時50分38秒
  !問題
!大きなバケツが3つある。6,11,14ずつ水が入っている。
!あるバケツに、それ以上多くの水が入っている他のバケツから、水を一部移して2倍にできる。
!この操作を繰り返して、1つのバケツを空にせよ。
!例
!バケツをA,B,Cとして、6,11,14とすると、
! バケツBからバケツAに水を移して、12,5,14とする。
! バケツCからバケツAに水を移して、12,11,8とする。
! バケツCからバケツBに水を移して、6,22,3とする。
!の3通りの操作ができる。
!
!答え
!水量の小さい順にバケツをA,B,Cとする。それぞれの水量をa,b,cとする。
!・q=[b/a]とするqを2進法展開して、k桁となれば、
! q=q[0]*2^0+q[1]*2^1+q[2]*2^2+ … +q[k-1]*2^(k-1)、ただしq[i](0≦i≦k-1)は0,1
! 長さkのビット列について
!  ビットq[i]が1なら、バケツBからバケツAに水を移す。すなわち、2*a,b-a,cとする。
!  ビットq[i]が0なら、バケツCからバケツAに水を移す。すなわち、2*a,b,c-aとする。
! を行う。
!・移動した結果をあらためて、水量の小さい順にバケツをA,B,Cとする。
!これを繰り返せば、バケツBが空になる。

LET a=6 !バケツの水量
LET b=11
LET c=14

LET s=0 !手数
PRINT s;": "; a;b;c

DO WHILE a>0 AND b>0 AND c>0 !どのバケツも空でないなら

   IF b< a THEN swap a,b !a≦b≦cとする
   IF c< a THEN swap a,c
   IF c< b THEN swap b,c
   PRINT "(";a;",";b;",";c;")"

   LET q=INT(b/a)
   PRINT BSTR$(q,2) !debug
   DO WHILE q>0 !2進法展開
      LET s=s+1

      IF MOD(q,2)=1 THEN !バケツBから
         LET b=b-a
         LET a=2*a
      ELSE !バケツCから
         LET c=c-a
         LET a=2*a
      END IF
      PRINT s;": ";a;b;c

      LET q=INT(q/2)
   LOOP

LOOP

END
 

戻る