To shift 1 disk from source to destination peg takes only one move, so T(1) = 1. Similarly, replace n by n – 2 in Equation (1), Let us solve this recurrence using forward and backward substitution:īy putting this value back in Equation (1), And each call corresponds to one primitive operation, so recurrence for this problem can be set up as follows: Step 3: Every call makes two recursive calls with a problem size of n – 1. Step 2: Primitive operation is to move the disk from one peg to another peg Step 1:Move disk C from the src peg to dst peg There can be n number of disks on source peg. If priests transfers the disks at a rate of one disk per second, with optimum number of moves, then also it would take them 2 64 – 1 seconds, which is around 585 billion years, which is 42 times the age of the universe as of now. According to legend, the world will end when the final move of the puzzle is completed. As a result, the puzzle is also known as the Tower of Brahma. Since that time, Brahmin priests have been rotating these disks in line with the unchanging laws of Brahma, fulfilling the order of an ancient prophesy. Almost soon, stories about the ancient and magical nature of the puzzle surfaced, including one about an Indian temple in Kashi Vishwanath having a huge chamber with three time-worn pillars in it, encircled by 64 golden disks.
Édouard Lucas, a French mathematician, developed the puzzle in 1883. Final position Story, Fun, Myth, Truth – What not?
0 kommentar(er)
