(Towers of Hanoi) In this chapter, you studiedfunctions that can be easily imple
ID: 3614466 • Letter: #
Question
(Towers of Hanoi) In this chapter, you studiedfunctions that can be easily implemented both recursively anditeratively. In this exercise, we present a problem whose recursivesolution demonstrates the elegance of recursion, and whoseiterative solution may not be as apparent.
The Towers of Hanoi is one of the most famousclassic problems every budding computer scientist must grapplewith. Legend has it that in a temple in the Far East, priests areattempting to move a stack of golden disks from one diamond peg toanother (Fig.6.41). The initial stack has 64 disks threaded onto one peg andarranged from bottom to top by decreasing size. The priests areattempting to move the stack from one peg to another under theconstraints that exactly one disk is moved at a time and at no timemay a larger disk be placed above a smaller disk. Three pegs areprovided, one being used for temporarily holding disks. Supposedly,the world will end when the priests complete their task, so thereis little incentive for us to facilitate their efforts.
Let us assume that the priests are attempting tomove the disks from peg 1 to peg 3. We wish to develop an algorithmthat prints the precise sequence of peg-to-peg disk transfers.
If we were to approach this problem withconventional methods, we would rapidly find ourselves hopelesslyknotted up in managing the disks. Instead, attacking this problemwith recursion in mind allows the steps to be simple. Moving ndisks can be viewed in terms of moving only n1 disks (hence, therecursion), as follows:
Move n -1 disks from peg 1 to peg 2, using peg 3as a temporary holding area.
Move the last disk (the largest) from peg 1 topeg 3.
Move the n -1 disks from peg 2 to peg 3, usingpeg 1 as a temporary holding area.
The process ends when thelast task involves moving n = 1 disk (i.e., the base case). Thistask is accomplished by simply moving the disk, without the needfor a temporary holding area.
Write a program to solve the Towers of Hanoiproblem. Use a recursive function with four parameters:
Explanation / Answer
please rate - thanks #include using namespace std; void hanoi(int n, int from, int to , int use); main() {int n; coutn; coutRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.