The Tower of Hanoi is a well known mathematical puzzle. It consists of three rods, and...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
The Tower of Hanoi is a well known mathematical puzzle. It consists of three rods, and a number n of disks of different sizes which can slide onto any rod. The puzzle starts with all disks stacked up on the 1st rod in order of increasing size with the smallest on top. The objective of the puzzle is to move all the disks to the 3rd rod, while obeying the following rules. Only one disk is moved at a time Each move consists of taking one disk from top of a rod, and moving it on top of the stack on another rod No disk may be placed on top of a smaller disk. A recursive algorithm that solves this problem is as follows: We first move the top n - 1 disks from rod 1 to rod 2. Then we move the largest disk from rod 1 to rod 3 and then move the n - 1 smaller disks from rod 2 to rod 3. Using the symmetry between the rods, the number of steps that this algorithm takes is given by the recurrence T(n) 2T(n-1)+1, which can be solved to get T(n) = 2n-1. == (a) (5 points) Show that the above algorithm is optimal, i.e., there does not exist a strategy that solves the Tower of Hanoi puzzle in less than 2" - 1 steps. (b) (5 points) Suppose the moves are restricted further such that you are only allowed to move disks to and from rod 2. Give an algorithm that solves the puzzle in O(3") steps. (c) (6 points (Extra credit)) Suppose the moves are restricted such that you are only allowed to move from rod 1 to rod 2, rod 2 to rod 3, and from rod 3 to rod 1. Give an algorithm that solves the puzzle in O((1+ 3)") steps. A Go The Tower of Hanoi is a well known mathematical puzzle. It consists of three rods, and a number n of disks of different sizes which can slide onto any rod. The puzzle starts with all disks stacked up on the 1st rod in order of increasing size with the smallest on top. The objective of the puzzle is to move all the disks to the 3rd rod, while obeying the following rules. Only one disk is moved at a time Each move consists of taking one disk from top of a rod, and moving it on top of the stack on another rod No disk may be placed on top of a smaller disk. A recursive algorithm that solves this problem is as follows: We first move the top n - 1 disks from rod 1 to rod 2. Then we move the largest disk from rod 1 to rod 3 and then move the n - 1 smaller disks from rod 2 to rod 3. Using the symmetry between the rods, the number of steps that this algorithm takes is given by the recurrence T(n) 2T(n-1)+1, which can be solved to get T(n) = 2n-1. == (a) (5 points) Show that the above algorithm is optimal, i.e., there does not exist a strategy that solves the Tower of Hanoi puzzle in less than 2" - 1 steps. (b) (5 points) Suppose the moves are restricted further such that you are only allowed to move disks to and from rod 2. Give an algorithm that solves the puzzle in O(3") steps. (c) (6 points (Extra credit)) Suppose the moves are restricted such that you are only allowed to move from rod 1 to rod 2, rod 2 to rod 3, and from rod 3 to rod 1. Give an algorithm that solves the puzzle in O((1+ 3)") steps. A Go
Expert Answer:
Related Book For
Data Structures And Algorithms In C++
ISBN: 9780470383278
2nd Edition
Authors: Michael T. Goodrich, Roberto Tamassia, David M. Mount
Posted Date:
Students also viewed these programming questions
-
Beauty of Recursion. Tower of Hanoi Tower of Hanoi is a logic puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the...
-
Julio sold his corporation to a competitor, Exeter LLC, for $100,000,000. Julio incorporated his business 17 years ago by investing $500,000 plus his proprietary know-how. There have been no other...
-
Vanstone Corp., a public company, adopted a stock option plan on November 30, 2014, that designated 70,000 common shares as available for the granting of options to officers of the corporation at an...
-
Three charges with q = +7.5 ?C are located as shown in Figure P17.21, with L = 25 cm.? (a) What are the magnitude and direction of the total electric force on the charge at the bottom?? (b) What are...
-
Refer to the information in Exercise 17-1. Assume that the following information is available for the companys two products for the first quarter of 2017. Required Compute activity rates for each...
-
Recording Adopted Budget. The City of Marion adopted the following General Fund budget for fiscal year 2011: Estimated revenues: Taxes................$3,000,000 Intergovernmental revenues...........
-
Table 17-4 Features of alternative security issues Common Stock Preferred Stock Bonds 1.Ownership and control of the firm Belongs to common stockholders through voting rights and residual claim to...
-
Jordyn M. & Lindsay M. Surplus has a committed line of credit with a maximum of $1.2 million and interest rate of 3.5% (EAR). The loan has a commitment fee of 0.45% (EAR). If the firm borrows...
-
The FDA issued a final compliance guidance related to pharmacy compounding. In the guidance, the FDA clarified which activities compounding pharmacies could lawfully engage and which activities the...
-
You are the only pharmacist at a meeting with other healthcare professionals. A physician brings up the topic of DTC drug ads on television and in magazines, lamenting that the ads are so seductive...
-
A patient asks the pharmacist whether the FDA regulates cosmetics and if so, in what manner. How should the pharmacist answer the patient?
-
A patient purchasing syringes and needles for insulin injection asked the pharmacist whether the FDA regulates these products and if so, in what manner. Provide a complete response to this patient.
-
Which of the following are not examples of a vicious cycle of deleveraging? Explain. a. Your university decides to sell several commercial buildings in the middle of town in order to upgrade...
-
Gretchen Schmidt plans to buy shares of two stocks. One costs $32 per share and pays dividends of $1.20 per share. The other costs $23 per share and pays dividends of $1.40 per share. She has $10,000...
-
Why is it important to understand the macro-environment when making decisions about an international retail venture?
-
Write a short C++ function that takes an integer n and returns the sum of all the integers smaller than n.
-
Consider the voting problem from Exercise C-11.13, but now suppose that we know the number k < n of candidates running. Describe an O(nlog k)- time algorithm for determining who wins the election....
-
Form a three-programmer team and have each member implement a map using a different search tree data structure. Perform a cooperative experimental study to compare the speed of these three...
-
A client who is a director of a publicly listed corporation is required by law to refrain from trading that companys stock at certain points of the year when disclosure of financial results are...
-
Consider the pairwise correlations of monthly returns of the following asset classes: Based solely on the information in the preceding table, which equity asset class is most sharply distinguished...
-
Investing the majority of the portfolio on a passive or low active risk basis while a minority of the assets is managed aggressively in smaller portfolios is best described as: A. The coresatellite...
Study smarter with the SolutionInn App