The classic example of a recursive solution to a relatively complex problem is t

Question

The classic example of a recursive solution to a relatively complex problem is the Tower of Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi - which is taught in every Computer Science program and in a lot of programming classes. As you add disks the solution becomes more complex, but it is a simple repetition of moves used in the 3 disk solution. Assignment We are not going to solve Tower of Hanoi, you are simply going to write a program to demonstrate computational complexity. Using the wikipedia article I want you to write a computer program that calculates the number of moves necessary to solve Tower of Hanoi given a number of disks. There are formulas that calaculate this - you are NOT going to use them. You will calculate by going through the recursive algorithm without making the actual moves (or you can if you want). What is the Complexity (In Big O)? Should we be concerned with concerned with the legend of the world ending when the 64 disk solution is physically solved it it takes 2 seconds for each move?

Explanation / Answer

algorithm:

fnTowers_hannoi(n,source,dest,spare,n)

// this algo finds the no. of moves required to solve the Tower of Hannoi problem for n discs.

{

If(n==1)

{

move top disc from source to destination; //base case

return;

}

else

{

fnTowers_hannoi(source,destination,spare,n-1);

fnTowers_hannoi(source,spare,destination,1);

fnTowers_hannoi(spare,source,destination,n-1);

}}//end of algorithm

The base case i.e when there is 1 disc then it requires only one move. so we can write T(1) =1

But when there is n number of discs then it requires three steps:

1)first it moves (n-1) discs to spare peg so it requires T(n-1) moves

2)The n th disc is moved using 1 move

3)Finally (n-1)disc tower is moved on top of n th disc so it requires T(n-1) moves

From the above we can write the recurrence realation in the following way:

T(n)= 2T(n-1)+1

Now, lets figure out the values of n for some numbers:

T(1)=1;

T(2)= 2T(1)+1=3

T(3)=2T(2)+1=7

T(4)=2T(3)+1=15

T(5)=2T(4)+1=31

From this we can say that

T(n)= 2n-1

So the Complexity is O(2n)

2 nd part

acoording do above complexity if we calculate then the no . of moves required for 64 discs is 264=18446744073709551616

each move requires 2 seconds . so the total time is 18446744073709551616*2=10248191152060862.008888888888889 hour

This is absolutely not feasible.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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