Towers of HonoiSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Towers of Honoi An application of RecursionTowers of Hanoi Problem: Invented by French mathematician Lucas in 1880s.Original problem set in India in a holy place called Benares. There are 3 diamond needles fixed on a brass plate. One needle contains 64 pure gold disks. Largest resting on the brass plate , other disks of decreasing diameters. Called tower of Brahma. Priests are supposed to transfer the disks from one needle to the other such that at no time a disk of larger diameter should sit on a disk of smaller diameter. Only one disk can be moved at a time.Later setting shifted to Honoi, but the puzzle and legend remain the same. How much time would it take? Estimate…..Finding a Recursive strategy: Any tower with more than one disk must be moved in pieces. If there is just one disk, then move it.It must be possible to break the problem into simpler subproblems of same form.start temp finish 3 DisksIrrespective of number of disks, the following steps need to be carried out:The bottom most disk needs to be moved to finish tower.So the disks above it must be removed first in step 1.In step 2,the bottom most disk can be moved.In step 3, the disks above it must be replaced in proper position.Now let us consider the problem of 3 disks.start temp finish startStep 1:Move 2 disks from start to temp using finish Tower.To understand the recursive routine, let us assume that we know how to solve 2 disk problem, and go for the next step.start temp finish This does not involve recursion, and can be carried out without using temp tower.Step 2:Move the (remaining) single disk from start to finish.start temp finish Step 3: Now we are at the last step of the recursive routine. Move the 2 disks from temp tower to finish tower using the start tower ( recursively).start temp finish This will solve the 3 disk problem.Now let us see how the complete sequence can be worked outand find out how many steps are going to be actually needed.start temp finishThe Complete sequence for 3 Disksstart temp finish startstart temp finish1start temp finish 2start temp finish 3start temp finish 4start temp finish6start temp finish start temp finish 5 7void movetower ( n, start, finish, temp){if ( n==1) {movesingle ( start, finish);} else {movetower ( n-1, start, temp, finish);movesingle ( start, finish);movetower ( n-1, temp, finish, start);}T(n) = 2 T(n-1) + 1How many steps? disks No. of steps1 12 3 ( 1 + 1 + 1 )3 7 ( 3 + 1 + 3 )4 15 (7 + 1 + 7 )n use recurrence relationRecurrence relation:T(n) = 2 T(n – 1 ) + 1T(n) = 2 T(n – 1 ) + 1= 2 [ 2 T(n – 2) + 1] + 1= 4 T(n – 2) + 2 + 1= 4 [ 2 T(n – 3) + 1] + 3= 8 T(n – 3) + 7= 23 T(n – 3) + 23 – 1 =2k T(n – k) + 2k – 1 Now let n – k = 1= 2n-1 T(1) + 2n-1 – 1 as time for 1 disk: T(1) = 1= 2. 2n-1 – 1 = 2n – 1 = O( 2n
View Full Document
Unlocking...