In general, Time complexity can be written as 1+2+2^2+2^3+.+2^(n-1) Number of Disks Minimum number of disk movements of disk movements can be written as follows. of disks=2, moving top 1 disk form source to auxiliary and move left over disk on start pole to end pole and then move auxiliary tower disk to end pole, on the whole constituting minimum of 3 disk movements. For no.of disks =1, moving from source to destination requires only 1 movement. We devise time complexity by looking at different number of disks, which would take the minimum number of disk movements. Move n-1 disks from auxiliary tower (B) to end pole (C)Ībove step 1 & 3, transferring the top n-1 disks, can be thought as a fresh problem and can be solved in a similar fashion.Move “n” th disk from start pole (A) to end pole (C).Move top n-1 disks form start pole (A) to auxiliary tower (B).Goal of the game is to move all the disks from tower A to tower C, find smallest number of disk movements required. You can’t keep larger diameter disk on top of smaller diameter disk.Only one disk can be moved to the other tower at a time.The puzzle will start with whole disks on the one tower in the ascending order of their diameter, top one is the smallest diameter thus forming a conical shape when we look at disks on the single tower. Towers of Hanoi is a mathematical puzzle, consists of three towers (rods or pegs) and number of disks of different size which can slide on to any tower.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |