Question

Therefore, getx-log,n from 2on. So the time complexity of this loop is O logn). Eliminate low order terms 26 00:01 00:01 Homework #7 Homework #7 - 7.1 Design the algorithm of Towers of Hanoi. . Source peg, Destination peg, Auxlary peg s k disks on the source peg, a bigger disk can never be on top of a smaler dsk : Need to move al k disks to the destination peg using the auxillary peg, without ever keeping a bigger disk on the smaller disk. . 7.2 Analyze the time complex of your algorithm in 7.1. - 7.3 Do a program to resolve Towers of Hanoi 29 30 14:00

Answer 1

Algorithm for Tower of Hanoi:

For writhing the algorithm,first we have to write the steps for solving tower of hanoi when we have smaller number of disks i.e, number of disks=1,2.

If we have 1 disk −

• First we move the smaller one (top) disk to destination peg

If we have 2 disks −

• First we move the smaller one (top) disk to aux peg
• Then we move the larger one (bottom) disk to destination peg
• And finally, we move the smaller one from aux to destination peg.

Algorithm:

Input: All disks on source peg.

Output: All disks on destination peg.

IF disk is equal 1, THEN
      move disk from source to destination
   ELSE
      tower(disk - 1, source, destination, intermediate)   // Step 1
      move disk from source to destination                 // Step 2
      tower(disk - 1, intermediate, destination, source)   // Step 3
   END IF
   
END

Analyzing the time complexity of above algorithm:

Recursive Equation :

——-equation-1

Base Recursive equation is T(0) = 1

Solving it by BackSubstitution :
———–equation-2
———–equation-3

Put value of T(n-2) in equation–2 with help of equation-3
——equation-4

Put value of T(n-1) in equation-1 with help of equation-4

After Generalization :

Base condition T(0) == 1
n – k = 0
n = k;
put, k = n

It is GP series, and sum is

, or you can say $O(2^n)$ which is exponential

Program in C++ for Tower of hanoi problem:

#include <bits/stdc++.h>

using namespace std;

  void towerOfHanoi(int n, char from_rod,

                    char to_rod, char aux_rod)

{

    if (n == 1)

    {

        cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod<<endl;

        return;

    }

    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);

    cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl;

    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);

}

int main()

{

    int n = 4; // Number of disks

    towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods

    return 0;

}

Output:

 Move disk 1 from rod A to rod B
 Move disk 2 from rod A to rod C
 Move disk 1 from rod B to rod C
 Move disk 3 from rod A to rod B
 Move disk 1 from rod C to rod A
 Move disk 2 from rod C to rod B
 Move disk 1 from rod A to rod B
 Move disk 4 from rod A to rod C
 Move disk 1 from rod B to rod C
 Move disk 2 from rod B to rod A
 Move disk 1 from rod C to rod A
 Move disk 3 from rod B to rod C
 Move disk 1 from rod A to rod B
 Move disk 2 from rod A to rod C
 Move disk 1 from rod B to rod C

Answer 2

7.1 solution

We have three peg (Source Peg, Destination Peg ,Auxilliary Peg).

and k disk

Algorithm

1. Move all top k-1 disk from source peg to Auxilliary Peg.

2. Move last i.e bottom disk to destination Peg.

3. Now move all k-1 Peg from Auxilliary Peg to destination Peg.

Example with 3 disk

Initial Source 3 2 1, Destination , Auxilliary

step1 Source 3 2 Destination 1 , Auxilliary

step 2 Source 3 , Destination 1 , Auxilliary 2

step 3 Source 3 , Destination , Auxilliary 2 1

step 4 Source , Destination 3, Auxilliary 2 1

step 5 Source 1, Destination 3 , Auxilliary 2

step 6 Source 1, Destination 3 2 , Auxilliary

step 7 Source , Destination 3 2 1 , Auxilliary

Time complexcity

its uses recursion

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

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

= 2^2 T(k-2) +2 +1

= 2^3 T(k-3) + 2^2 + 2+ 1

:

= 2^(k-1) T(k-(k-1)) + 2^(k-2) +........+ 2+1   

= 2^(k-1) + 2^(k-2) +........+ 2+1 [ as T(1) =1]

= 2^k - 1 [expansion]

Code

//---------------------------------------

#include <bits/stdc++.h>
using namespace std;
  
void solveHanoi(int n, string from_rod,
string to_rod, string aux_rod)
{
if (n == 1)
{
cout << "Move disk 1 from Peg " << from_rod <<
" to Peg " << to_rod<<endl;
return;
}
solveHanoi(n - 1, from_rod, aux_rod, to_rod);
cout << "Move disk " << n << " from Peg " << from_rod <<
" to Peg " << to_rod << endl;
solveHanoi(n - 1, aux_rod, to_rod, from_rod);
}
  

int main()
{
int n ; // Number of disks

cin>>n;
solveHanoi(n, "Source ", "Destination ", "Auxilliary");
return 0;
}
  

Answer 3

7.1

START

Procedure TowerofHanoi(k, Source peg, Destination peg, Auxilary peg)

   IF k== 1, THEN

      move disk from Source peg to Destination peg

   ELSE

      TowerofHanoi(k- 1, Source peg, Auxilary peg, Destination peg)     // Step 1

      move disk from Source peg to Destination peg // Step 2

      TowerofHanoi(k- 1, Auxilary peg, Destination peg, Source peg)     // Step 3

   END IF

  

END Procedure

STOP

---------------------------------------------------------------------------------------------------------------------------------------------------------------------

7.2 - Time Complexity

Let the time required for n disks is T (n) . There are 2 recursive call for n-1 disks and one constant time operation to move a disk from ‘Source’ peg to ‘Destination’ peg.

Let it be k1.

Therefore, Recursive equation T (n) = 2 T (n-1) + k1

T (0) = k2, a constant.

T (1) = 2 k2 + k1

T (2) = 4 k2 + 2k1 + k1

T (3) = 8 k2 + 4k1 + 2k1 + k1

…………………………………………..

T (n) = (2^n) k2 + (2^n-1) k1 + (2^n-2) k1 + k1

Coefficient of k1 =2^n

Coefficient of k2 =2^n-1

Time complexity is O (2^n) or O (a^n)

Where a is a constant greater than 1.

---------------------------------------------------------------------------------------------------------------------------------------------------------

7.3

using namespace std;   

void TowerOfHanoi(int k, char SourcePeg,

                    char DestinationPeg, char AuxilaryPeg)

{

    if (k == 1)

    {

        cout << "Move disk 1 Source Peg " << SourcePeg <<

                            ”to Destination Peg" << DestinationPeg <<endl;

        return;

    }

    TowerOfHanoi (k - 1, SourcePeg, AuxilaryPeg, DestinationPeg);

    cout << "Move disk " << k << "Source Peg" << SourcePeg <<

                                "Destination Peg" << DestinationPeg << endl;

    TowerOfHanoi (k - 1, AuxilaryPeg, DestinationPeg, SourcePeg);

}

  

// Execution starts from here

int main()

{

    int k = 4; // Number of disks

    TowerOfHanoi (k, 'A', 'C', 'B'); // A, B and C are the names of pegs

    return 0;

}