Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

pleas explain In this assignment, you will write two short programs to solve problems using recursion. 1. Initial Setup 1. Log in to Unix. 2.

pleas explain
image text in transcribed
image text in transcribed
image text in transcribed
In this assignment, you will write two short programs to solve problems using recursion. 1. Initial Setup 1. Log in to Unix. 2. Run the setup script for Assignment 2 by typing: setup 2 2.Towers of Hanoi Legend has it that in a temple in the Far East, priests are attempting to move a stack of disks from one peg to another. The initial stack had 64 disks threaded onto one peg and arranged from bottom to top by decreasing size. The priests are attempting to move the stack from this peg to a second peg under the constraints at exactly one disk is moved at a time, and at no time may a larger disk be placed above a smaller disk. A third peg is available for temporarily holding the disks. According to the legend, the world will end when the priests complete their task. Consider three pegs numbered 1 through 3. Let us assume that the priests are attempting to move the 64 disks from peg 1 to peg 2, using peg 3 as a temporary holding peg, The problem is to design an algorithm that that will print the precise sequence of disk peg-to-peg transfers. If you were to approach this problem with conventional methods, you would rapidly find yourself hopelessly knotted up in managing the disks. Instead, if yo attack the problem with recursion in mind, it immediately becomes tractable. If we assume that we have a function that can move n - 1 disks from one peg to another using a third peg as a temporary holding peg, then we can easily formulate an algorithm to move n disks from peg 1 to peg 2 by using the function that moves n. 1 disks as follows: 1. Move n. 1 disks from peg 1 to peg 3, using peg 2 as a temporary holding peg. 2. Move the last disk (the largest) from peg 1 to peg 2. 3. Move the n. 1 disks from peg 3 to peg 2, using peg 1 as a temporary holding disk Write a recursive program that solves the Towers of Hanoi problem. Your solution must be recursive to be eligible for any credit. 2.1. Input Your program must accept a single command line argument, a positive integer. This integer n will represents the number of disks to move. Number the disks from 1 (the smallest disk) to n(the largest disk). You should always start with all the disks on peg 1 with pegs 2 and 3 empty. Your program should then produce the sequence of disk peg-to-peg moves to move all the disks from peg 1 to peg 2. 2.2. Output Your output should print one move per line. Each move must be in the following format, 1 2->3 which is interpreted as "move disk 1 from peg 2 to peg 3." Assuming that the name of your program is hanoi, below is an example of what an execution of your program should look like: 2123456@turing:-$ ./hanoi 2 11-> 21->2 13->2 2123456@turing: - The format of the output must be exactly has shown above. There is another program (described below) that we have written to check the output of your program. It expects exactly this format. WARNING: The number of moves it takes to transfer the disks from peg 1 to 2 grows exponentially as you increase the number of disks, (for n disks the number of moves is 2n . If each move produces 7 bytes of output, redirecting the 20 disk output to a file will produce a 7MB file. Take care not to do that. It is safe to run your program with as many disks as you want as long as the output goes to the screen. But be careful not to redirect the stdout of your program for large disk counts, e-8, do not do the following 21234568turing:-/sci241/Assign2$ ./hanos 20 > 20.out of this does happen, don't panic. Simply remove the file using the command um 20.out 23. File You Must Write Write the code for this part of the assignment in a single file which must be called hanoi.cpp: 24.Files We Give You if you use the setup command to get ready for this assignment, you will find an executable file called test_hanoi in your-/csci241/Assign2 directory You can use test_hanoi to test the output of your program (rather then checking it by hand), test_hanoi reads the output (in the format described above) of hanoi and prints either "SUCCESS" or "failure". test_hanoi also takes a command line argument that must match the command line argument passed to hanoi that generated the output file. You can run test_hanoi in one of two ways. 2123456@turing:-/esei 241/Assign25 ./hanoi 5 > 5.out z123456@turing /esci241/Assign25/test hanoi 5

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Data Management Databases And Organizations

Authors: Richard T. Watson

2nd Edition

0471180742, 978-0471180746

More Books

Students also viewed these Databases questions

Question

What is the orientation toward time?

Answered: 1 week ago

Question

4. How is culture a contested site?

Answered: 1 week ago