Monday, August 1, 2011
Sunday, July 31, 2011
Saturday, July 23, 2011
Thursday, July 21, 2011
Wednesday, July 20, 2011
Monday, July 18, 2011
Sunday, July 17, 2011
Friday, July 15, 2011
Wednesday, July 13, 2011
Friday, May 20, 2011
P019 : Tower of Hanoi
The Tower of Hanoi can be played using paper and pen only. The following is a solution of the game with 6 disks represented by the numbers 1,2,3,4,5,6 where disk i is smaller than disk i+1, i=1,2,3,4,5. The poles are represented by the letters A, B, C.
Explanation : In step (01), disk 1 is transferred from pole A to pole B.
(00) (123456,,)
(01) (23456,1,) (AB)
(02) (3456,1,2) (AC)
(03) (3456,,12) (BC)
(04) (456,3,12) (AB)
(05) (1456,3,2) (CA)
(06) (1456,23,) (CB)
(07) (456,123,) (AB)
(08) (56,123,4) (AC)
(09) (56,23,14) (BC)
(10) (256,3,14) (BA)
(11) (1256,3,4) (CA)
(12) (1256,,34) (BC)
(13) (256,1,34) (AB)
(14) (56,1,234) (AC)
(15) (56,,1234) (BC)
(16) (6,5,1234) (AB)
(17) (16,5,234) (CA)
(18) (16,25,34) (CB)
(19) (6,125,34) (AB)
(20) (36,125,4) (CA)
(21) (36,25,14) (BC)
(22) (236,5,14) (BA)
(23) (1236,5,4) (CA)
(24) (1236,45,) (CB)
(25) (236,145,) (AB)
(26) (36,145,2) (AC)
(27) (36,45,12) (BC)
(28) (6,345,12) (AB)
(29) (16,345,2) (CA)
(30) (16,2345,) (CB)
(31) (6,12345,) (AB)
(32) (,12345,6) (AC)
(33) (,2345,16) (BC)
(34) (2,345,16) (BA)
(35) (12,345,6) (CA)
(36) (12,45,36) (BC)
(37) (2,145,36) (AB)
(38) (,145,236) (AC)
(39) (,45,1236) (BC)
(40) (4,5,1236) (BA)
(41) (14,5,236) (CA)
(42) (14,25,36) (CB)
(43) (4,125,36) (AB)
(44) (34,125,6) (CA)
(45) (34,25,16) (BC)
(46) (234,5,16) (BA)
(47) (1234,5,6) (CA)
(48) (1234,,56) (BC)
(49) (234,1,56) (AB)
(50) (34,1,256) (AC)
(51) (34,,1256) (BC)
(52) (4,3,1256) (AB)
(53) (14,3,256) (CA)
(54) (14,23,56) (CB)
(55) (4,123,56) (AB)
(56) (,123,456) (AC)
(57) (,23,1456) (BC)
(58) (2,3,1456) (BA)
(59) (12,3,456) (CA)
(60) (12,,3456) (BC)
(61) (2,1,3456) (AB)
(62) (,1,23456) (AC)
(63) (,,123456) (BC)
The number of steps required to solve the game of Tower of Hanoi of n disks is 2^n-1 where n is the number of disks.
In the example above, note that the number of steps taken = 63 = 2^6-1.
Strategy : When transferring the disks, make sure that the numbers representing the adjacent disks differ by an odd number.
Explanation : In step (01), disk 1 is transferred from pole A to pole B.
(00) (123456,,)
(01) (23456,1,) (AB)
(02) (3456,1,2) (AC)
(03) (3456,,12) (BC)
(04) (456,3,12) (AB)
(05) (1456,3,2) (CA)
(06) (1456,23,) (CB)
(07) (456,123,) (AB)
(08) (56,123,4) (AC)
(09) (56,23,14) (BC)
(10) (256,3,14) (BA)
(11) (1256,3,4) (CA)
(12) (1256,,34) (BC)
(13) (256,1,34) (AB)
(14) (56,1,234) (AC)
(15) (56,,1234) (BC)
(16) (6,5,1234) (AB)
(17) (16,5,234) (CA)
(18) (16,25,34) (CB)
(19) (6,125,34) (AB)
(20) (36,125,4) (CA)
(21) (36,25,14) (BC)
(22) (236,5,14) (BA)
(23) (1236,5,4) (CA)
(24) (1236,45,) (CB)
(25) (236,145,) (AB)
(26) (36,145,2) (AC)
(27) (36,45,12) (BC)
(28) (6,345,12) (AB)
(29) (16,345,2) (CA)
(30) (16,2345,) (CB)
(31) (6,12345,) (AB)
(32) (,12345,6) (AC)
(33) (,2345,16) (BC)
(34) (2,345,16) (BA)
(35) (12,345,6) (CA)
(36) (12,45,36) (BC)
(37) (2,145,36) (AB)
(38) (,145,236) (AC)
(39) (,45,1236) (BC)
(40) (4,5,1236) (BA)
(41) (14,5,236) (CA)
(42) (14,25,36) (CB)
(43) (4,125,36) (AB)
(44) (34,125,6) (CA)
(45) (34,25,16) (BC)
(46) (234,5,16) (BA)
(47) (1234,5,6) (CA)
(48) (1234,,56) (BC)
(49) (234,1,56) (AB)
(50) (34,1,256) (AC)
(51) (34,,1256) (BC)
(52) (4,3,1256) (AB)
(53) (14,3,256) (CA)
(54) (14,23,56) (CB)
(55) (4,123,56) (AB)
(56) (,123,456) (AC)
(57) (,23,1456) (BC)
(58) (2,3,1456) (BA)
(59) (12,3,456) (CA)
(60) (12,,3456) (BC)
(61) (2,1,3456) (AB)
(62) (,1,23456) (AC)
(63) (,,123456) (BC)
The number of steps required to solve the game of Tower of Hanoi of n disks is 2^n-1 where n is the number of disks.
In the example above, note that the number of steps taken = 63 = 2^6-1.
Strategy : When transferring the disks, make sure that the numbers representing the adjacent disks differ by an odd number.
Friday, May 13, 2011
Saturday, January 8, 2011
Tuesday, January 4, 2011
Subscribe to:
Posts (Atom)