Towers of hanoi

Measuring Execution Time

To measure execution time, you will use a Timer implementation (ChronoTimer) to time sections of code. It acts like a stopwatch for system time. Take a look at the Timer interface declared in Timer.h and check out the operations that are implemented in ChronoTimer.cpp.

By including ChronoTimer.h and Timer.h you can declare and use a Timer object as follows:

Timer *stopwatch = new ChronoTimer{}; stopwatch->start(); // do some processing, i.e., make a function call stopwatch->stop(); std::cout << "The time taken for processing was " << *stopwatch << " nanoseconds.\n";

Notice the use of pointers and that the time is reported in nanoseconds.

Your First Example: The Towers of Hanoi Problem

The Towers of Hanoi is a classic problem in computer science. It illustrates the fact that for some kinds of problems the solution using a recursive algorithm is very easy to find whereas an iterative one is considerably more difficult.

The problem involves disks on three pegs, and to solve it you must move the disks from one peg to another according to the following rules:

1. When moving a disk, you must put it on a peg -- you may not simply set it to the side for later use.
2. You may move only one disk at a time, and it must be the top disk of one of the pegs.
3. You may never put a larger disk on top of a smaller one.

Consider how to solve this problem recursively. Remember that, as described in class, there are two parts to a recursive solution: the base case and the inductive case.

The Base Case

We begin by deciding what the base case is. It is usually a simple case, and here the simplest case is when there is only one disk. The the solution is trivial. You move the single disk from peg A to peg C; the problem is solved.

The Inductive Case

For more than one disk, we have to use the inductive case, which should look something like this:

1. Move the topmost n-1 disks from peg A to peg B, using peg C for temporary storage.
2. Move the final disk remaining from peg A to peg C (the base case).
3. Move the n-1 disks from peg B to peg C, using peg A for temporary storage.

As you can see by looking at the function move() in the program hanoi.cpp, it is easy to implement this algorithm in code.

Tasks

Part 1: Counting moves

Compile and execute the hanoi target. Once you understand how it operates, modify hanoi.cpp so that instead of prompting the user for the number of disks, it calls move() ten times so that data can be collected to fill in the results table found in questions.txt. With that data at hand, also answer the next question regarding the number of moves, in general.

When you have completed this task, commit your changes.

Part 2: Timing moves

Next, modify hanoi.cpp as follows:

1. Remove any iterative structures that you added when you worked on Part 1.
2. Comment out the output statement in function move().
3. Add statements in described earlier (and demonstrated in main.cpp) to time the call to move().
4. Compile and execute the program repeatedly until you find a value for the number of disks for which the execution time is at least 1/4 second (250,000,000 nanoseconds). Use it as the first entry in the results table found in Part 2 of questions.txt and then find the execution times for the next 4 values of n. Record the results in the aforementioned table and answer the last question as well

Question.txt file attached

All files needed are attached as lab04.zip file.(every basic codes are here as main,cpp, hanoi.cpp etc)