The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
166 views

In Tower of Hanoi problem, when we move 3 disk , it will rotate like

Input : 3
Output : Disk 1 moved from A to C
         Disk 2 moved from A to B
         Disk 1 moved from C to B
         Disk 3 moved from A to C
         Disk 1 moved from B to A
         Disk 2 moved from B to C
         Disk 1 moved from A to C

Now if we move it in a recursive function , it looks like

void move(int n, char A, char B, char C) {
    if (n > 0) {
        move (n-1, A, C, B);
        printf("Move disk %d from pole %c to pole %c\n", n, A, C);
        move (n-1, B, A, C);
    } 
}

But there is no move from C to B in recursive function call, which should be 3rd call according to logic.

means there should be a call from move(n-1,C,B,A) which is not there.

Where am I missing plz help

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

According to the link https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

Some disk move I have shown here with recursion tree. Plz help me some moves of disk after this move

asked in DS by Veteran (96k points)
edited by | 166 views
0
can you please specify you want to move disk from $A \rightarrow B$ using $C$or $A \rightarrow C$  using $B$?
0
function is like that

move(from_vertex,to_vertex,auxiliary_vertex);
0
 move (n-1, A, C, B); ------------------ move n-1 disks from A to B using C
  printf("Move disk %d from pole %c to pole %c\n", n, A, C); 
 move (n-1, B, A, C);--------------------move n-1 disks from B to C using A.

source = A , destination= C

as per code.

0
yes then where move from C to B

I want to match code with real scenario
0
disk 2 is moved from C to B because we have to shift disk3 (biggest) from A to C.
0

That I know , but i want approach through recursion tree

https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

0

this answer need a correction, rt?

https://gateoverflow.in/864/gate2002-11

1 Answer

+1 vote
Best answer

function is like that

move(from_vertex,to_vertex,auxiliary_vertex)

void move(int n, char A, char B, char C)

The above $2$ taken from your question proves that you want to transfer $A$ to $B$ using $C$

How tower of hanoi works?

  • Move $n-1$ disks from $A \rightarrow C$ using $B$
  • Move $n^{th}$ disk of $A$ to $B$
  • Move all $n-1$ disks $C \rightarrow B$ using $A$

Code-:

#include<stdio.h>
void toh(int n,char from_peg,char to_peg,char via_peg)
{
if(n==1)
{
printf("MOVE DISK %d  FROM %c TO %c\n ",n,from_peg,to_peg);
}
else
{
toh(n-1,from_peg,via_peg,to_peg);
printf("MOVE DISK %d  FROM %c TO %c \n",n,from_peg,to_peg);
toh(n-1,via_peg,to_peg,from_peg);
}
}

int main()
{
int num;
printf("\n*****Tower of hanoi using 3 pegs*******\n");
printf("from peg A to peg B via peg C\n");
printf("enter the number of disks\n");
scanf("%d",&num);
toh(num,'A','B','C');
return 0;
}

Output-:

*****Tower of hanoi using 3 pegs*******
from peg A to peg B via peg C
enter the number of disks
3
MOVE DISK 1  FROM A TO B
MOVE DISK 2  FROM A TO C
MOVE DISK 1  FROM B TO C
MOVE DISK 3  FROM A TO B
MOVE DISK 1  FROM C TO A
MOVE DISK 2  FROM C TO B
MOVE DISK 1  FROM A TO B

Your issue -:

First of all your output is for the input transfer peg $A \text{to peg } C \text{via peg}B$

your issue in the code is

line 3rd

move (n-1, C, B, A);
answered by Boss (16.1k points)
selected by
0

sourav it is not much easy I think

Can see recursive tree approach here

https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

I will show u in picture more about it

But still problem remain

I cannot match recursive tree with function call of ur program

0
chk question now
0

chk question now

chk answer now

0

so this answer need to change

https://gateoverflow.in/864/gate2002-11

As we generally take move(from_vertex,to_vertex,auxiliary_vertex); this convension

+1

Regarding  https://gateoverflow.in/864/gate2002-11

it is absolutely correct.

Catch of the question is -:

printf("Move disk %d from pole %c to pole %c\n", n, A, C);

Using this, we can say that 

A is source

C is destination 

B is intermediate

So parameter to the function move()is arranged  as(source, intermediate,destination)

code should be 

void move(int n, char A, char B, char C) {
    if (n > 0) {
        move (n-1, A, C, B);
        printf("Move disk %d from pole %c to pole %c\n", n, A, C);
        move (n-1, B, A, C);
    } 
}


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,753 questions
46,768 answers
140,672 comments
58,545 users