Scribd Logo
Upload

Welcome to Scribd!

  • 51 views

    Tower of Hanoi C Program Assignment.

    Uploaded by

    Robert Loitongbam
    The document describes the Tower of Hanoi puzzle problem. The problem involves moving a stack of discs of different sizes between three rods, obeying rules where only the top disc can be moved each time and no larger disc can be placed on top of a smaller disc. It can be solved recursively by moving the top n-1 discs to an auxiliary rod, then the largest disc to the destination rod, and finally the n-1 discs from auxiliary to destination rod. The document provides an example of solving the problem for 4 discs and includes C++ code to implement the recursive solution.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Tower of Hanoi C Program Assignment.

    Uploaded by

    Robert Loitongbam
    51 views8 pages
    The document describes the Tower of Hanoi puzzle problem. The problem involves moving a stack of discs of different sizes between three rods, obeying rules where only the top disc can be moved each time and no larger disc can be placed on top of a smaller disc. It can be solved recursively by moving the top n-1 discs to an auxiliary rod, then the largest disc to the destination rod, and finally the n-1 discs from auxiliary to destination rod. The document provides an example of solving the problem for 4 discs and includes C++ code to implement the recursive solution.

    Original Description:

    Tower of Hanoi using c++ .

    Original Title

    Tower of Hanoi c program assignment.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes the Tower of Hanoi puzzle problem. The problem involves moving a stack of discs of different sizes between three rods, obeying rules where only the top disc can be moved each time and no larger disc can be placed on top of a smaller disc. It can be solved recursively by moving the top n-1 discs to an auxiliary rod, then the largest disc to the destination rod, and finally the n-1 discs from auxiliary to destination rod. The document provides an example of solving the problem for 4 discs and includes C++ code to implement the recursive solution.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    51 views8 pages

    Tower of Hanoi C Program Assignment.

    Uploaded by

    Robert Loitongbam
    The document describes the Tower of Hanoi puzzle problem. The problem involves moving a stack of discs of different sizes between three rods, obeying rules where only the top disc can be moved each time and no larger disc can be placed on top of a smaller disc. It can be solved recursively by moving the top n-1 discs to an auxiliary rod, then the largest disc to the destination rod, and finally the n-1 discs from auxiliary to destination rod. The document provides an example of solving the problem for 4 discs and includes C++ code to implement the recursive solution.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 8

    Tower of Hanoi

    UNIT-2 ASSIGNMENT
    (02)

    FOR

    DATA STRUCTURE

    SUBMITTED BY:
    ROBERT LOITONGBAM
    SECOND YEAR(CSE)
    ROLL NO.:40
    Tower of Hanoi
    DEFINITION:

    Tower of Hanoi is a puzzle problem. Where we have three


    stands and n discs. Initially, Discs are placed in the first
    stand. We have to place discs into the third or destination
    stand, the second or auxiliary stand can be used as a
    helping stand.

    But there are some rules to follow:

     We can transfer only one disc for each movement.


     Only the topmost disc can be picked up from a stand.
     No bigger disc will be placed at the top of the smaller
    disc.

    EXPLANATION AND DIAGRAM:

    This problem can be solved easily by recursion. At first,


    using recursion the top (n-1) discs are placed from source
    to auxiliary stand, then place the last disc from source to
    destination, then again place (n-1) disc from auxiliary
    stand to destination stand by recursion.
    Tower of Hanoi

    Example:

    Suppose no of disks are 4 and the starting rod is ‘A’, the auxiliary
    rod is ‘B’ and the ending rod is ‘C’.

    In each step first we move the top most node of peg ‘A’ to auxiliary
    peg ‘B’ and then finally move to ‘C’ which is the desired peg.

    Initially:
    All disks are stack on peg ‘A’ with order of their size being Disk3 <
    Disk2 < Disk1

    Peg A Peg B Peg C

    Disc 3

    Disc 2

    Disc 1
    Tower of Hanoi
    Moving Disc 3 To Peg C:

    Peg A Peg B Peg C

    Disc 2

    Disc 1 Disc 3

    Moving Disc 2 To Peg B:

    Peg A Peg B Peg C

    Disc 1 Disc 2 Disc 3

    Moving Disc 3 To Peg B:

    Peg A Peg B Peg C

    Disc 3

    Disc 1 Disc 2

    Moving Disc 1 To Peg C:

    Peg A Peg B Peg C

    Disc 3

    Disc 2 Disc 1
    Tower of Hanoi

    Moving Disc 3 To Peg B:

    Peg A Peg B Peg C

    Disc 3 Disc 2 Disc 1

    Moving Disc 2 To Peg C:

    Peg A Peg B Peg C

    Disc 3 Disc 2

    Disc 1

    Moving Disc 3 To Peg C:

    Peg A Peg B Peg C

    Disc 3

    Disc 2

    Disc 1

    Now this is the desired solution as all of the disks are stacked on
    peg ‘C’.
    Tower of Hanoi

    Tower of Hanoi Algorithm:


    Step 1: Start the program.
    Step 2: Input number of disks.
    Step 3: Declare a function which takes the number of
    disks, starting disk, auxiliary disk and final disk as
    argument and recursively calls itself twice.
    Step 4: Call the function.
    Step 5: End the Program.

    PROGRAM:

    #include<bits/stdc++.h>
    void toh(int, char, char, char);

    int main(){
    char source = 'A', destination='B', Auxiliary='C';
    int n;
    cout<< "Enter value of n\t";
    cin>> n;
    toh(n, source, destination, Auxiliary);
    return 0;
    }

    void toh(int n, char source, char dest, char aux){


    if(n==1){
    cout<< "%c -> %c \n"<< source<< dest;
    return;
    }
    toh(n-1, source, aux, dest);
    cout<< "%c -> %c \n"<< source<< dest;
    toh(n-1, aux, dest, source);
    }
    Tower of Hanoi

    Output:

    Enter the number of disks: 3


    1. Move disk 1 from A to C
    2. Move disk 2 from A to B
    3. Move disk 1 from C to B
    4. Move disk 3 from A to C
    5. Move disk 1 from B to A
    6. Move disk 2 from B to C
    7. Move disk 1 from A to C

    Time Complexity: O(2n)

    In each function call, we are calling the function twice so time


    complexity of tower of hanoi program is O(2n).

    Space Complexity: O(n)

    Space of the recursive stack is of order n, so space complexity of


    tower of hanoi program is O(n).
    Tower of Hanoi

    Conclusion:

    In this Tower of Hanoi tutorial, you learned what the TOH


    problem is. After that, you discovered the logical approach
    to implement a solution for the TOH problem. Finally, you
    also looked at the programming implementation of the
    TOH solution using the C programming language.

    If you're looking for more in-depth training that goes


    beyond data structures and covers the foundations of
    interactive application development, Simplilearn's
    Software Development Courses will prove ideal for you.
    The courses in this catalog can help you improve your
    odds of becoming a software developer by aiding you in
    mastering the art of software development. So, go ahead
    and start exploring!

    Have any questions about this article on the Tower of


    Hanoi problem? If yes, please leave them in the
    comments section at the bottom of this page; we will
    respond to them soon!

    You might also like