|
|
!問題
!大きなバケツが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
|
|