TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

DAA Tower of Hanoi

DAA Tower of Hanoi with daa tutorial, introduction, Algorithm, Asymptotic Analysis, Control Structure, Recurrence, Master Method, Recursion Tree Method, Sorting Algorithm, Bubble Sort, Selection Sort, Insertion Sort, Binary Search, Merge Sort, Counting Sort, etc.

<< Back to DAA

Tower of Hanoi

1. It is a classic problem where you try to move all the disks from one peg to another peg using only three pegs.

2. Initially, all of the disks are stacked on top of each other with larger disks under the smaller disks.

3. You may move the disks to any of three pegs as you attempt to relocate all of the disks, but you cannot place the larger disks over smaller disks and only one disk can be transferred at a time.

This problem can be easily solved by Divide & Conquer algorithm

DAA Tower of Hanoi

In the above 7 step all the disks from peg A will be transferred to C given Condition:

  1. Only one disk will be shifted at a time.
  2. Smaller disk can be placed on larger disk.

Let T (n) be the total time taken to move n disks from peg A to peg C

  1. Moving n-1 disks from the first peg to the second peg. This can be done in T (n-1) steps.
  2. Moving larger disks from the first peg to the third peg will require first one step.
  3. Recursively moving n-1 disks from the second peg to the third peg will require again T (n-1) step.

So, total time taken T (n) = T (n-1)+1+ T(n-1)

Relation formula for Tower of Hanoi is:

DAA Tower of Hanoi

We get,

DAA Tower of Hanoi

It is a Geometric Progression Series with common ratio, r=2
          First term, a=1(20)

DAA Tower of Hanoi

B equation is the required complexity of technique tower of Hanoi when we have to move n disks from one peg to another.

T (3) = 23- 1
          = 8 - 1 = 7 Ans

[As in concept we have proved that there will be 7 steps now proved by general equation]

Program of Tower of Hanoi:

#include<stdio.h>
void towers(int, char, char, char);
 int main()
 {
       int num;
       printf ("Enter the number of disks : ");
        scanf ("%d", &num);
      printf ("The sequence of moves involved in the Tower of Hanoi are :\n");
      towers (num, 'A', 'C', 'B');
      return 0;
 
}
     void towers( int num, char from peg, char topeg, char auxpeg)
 {
           if (num == 1)
 {
       printf ("\n Move disk 1 from peg %c to peg %c", from peg, topeg);
           return;
 }
   Towers (num - 1, from peg, auxpeg, topeg);
    Printf ("\n Move disk %d from peg %c to peg %c", num, from peg, topeg);
   Towers (num - 1, auxpeg, topeg, from peg);
 }

Output:

Enter the number of disks: 3
The sequence of moves involved in the Tower of Hanoi is
Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg
DAA Tower of Hanoi
Next TopicBinary Heap Sort




Related Links:


Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf