Write a C++ program that use\'s a recursion function to issue instructions to so

Question

Write a C++ program that use's a recursion function to issue instructions to solve the Towers of Hanoi puzzle and also write comments to explain how your code works and answer the following question on the bottom.

Recursion is a programming technique in which a function calls itself. It is another way of implementing repetitive computations, which we have previously associated with loops. When called to solve a problem, a recursive function passes a smaller version (or versions) of the problem to another instance (or other instances) of itself, then uses the results returned by the recursive call or calls to build the solution to the original problem.

THE TOWERS OF HANOI

A recursive function hanoi(n,source,destination) will write out the directions for moving a stack of n disks from post source to post destination. Assume that the posts are numbered 1, 2, and 3, as in the picture.

Note that when n is zero, there is nothing to do. Otherwise, we must move the top (n - 1) disks from the source post to the intermediate one, move the remaining disk to the destination post, and then move the (n - 1) disks from the intermediate post to the destination one, on top of the larger disk just moved there.

The program will assume that the disks will be moved from post 1 to post 3, and will read only the number of disks to be moved. A run of the program might look like this:

Hint: If the posts are numbered 1, 2, and 3, the sum of their numbers is 6. When we want to move disks from post x to post y, the number of the other post is 6 - x - y.

Question: What is the big-O behavior of your function's time? How do you know?

Explanation / Answer

#include #include #include using namespace std; /*************************************** **Function: buildBoard **Description: Initialize the game "board" for given number of disks--this happens in the form of a 2D-array where each disk number is in it's place, and the rest of the "spots" on the board are populated with 0s. Consider each column to be a peg. **Parameters: Dynamic array which represents the board, number of rows **Pre-conditions: User must have input valid int, and board must have initialized correctly. **Post-conditions: Board must contain one column of ints 1-x, where x is the number of rows, and be populated elsewhere by 0s. *****************************************/ void buildBoard(int array[][3], int rows); /************************************** **Function: printArray **Description: Prints the current state of the board to the terminal so that user can follow solution step-by-step and visualize what's happening. **Parameters: Dynamic array which represents the board, number of rows. **Pre-conditions: Board must have been initialized correctly, and caller function must have run properly. **Post-conditions: ***************************************/ void printArray(int array[][3], int rows); /*************************************** **Function: moveDisk **Description: Move "disk" (in form of an int representing the disk) from a to b within 2D array. **Parameters: Which disk is being moved, the 2D array representing the board, the column the disk is in (a), the column the disk is going to (b), the column which is not being used, and the number of rows. ***************************************/ void moveDisk(int disk, int b[][3], int from_column, int to_column, int rows); /**************************************** **Function: towers **Description: The meat of the program! Calls move disk and print board functions recursively. **Parameters: Which disk is being moved, board, from column, to column, spare column, and number of rows *****************************************/ void towers(int disks, int b[][3], int from_column, int spare, int to_column, int rows); /**************************************** **Function: checkInput **Description: Make sure user input is positive integer, and throw error if it's not. **Parameters: User input. **Pre-conditions: User must have input something. **Post-conditions: User must have input the input correct. ******************************************/ void checkInput(){ cin.clear(); cin.ignore(1000, ' '); cout

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.