You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in Tower of Hanoi

Hi, I'v been stuck on Tower of Hanoi for quite some time now. I have a fair bit of understanding of recursion and the way function calls itself. But here in Tower of Hanoi, I am unable to understand the flow of the algorithm. Here's the algorithm I'm following:

T(N, Beg, Aux, End)

 1. T(N-1, Beg, End, Aux)
 2. T(1, Beg, Aux, End)
 3. T(N-1, Aux, End)

So, according to the above algorithm, First we swap N-1 disks to an auxiliary peg, then we swap the Nth peg to the destination peg and repeat the following. But, When I take an example Say T(3, A, B, C) where I have to move disks from A to C, here are the steps that I follow:

 1. (2, A, C, B) ... T(N-1, Beg, End, Aux) 
 2. (1, A, B, C) ... T(1, Beg, Aux)
 3. ?

I am really confused as which step(s) will follow afterwards. Please help me in figuring out this algorithm. Also, if possible please help me in understanding which functions would go in the stack sequentially..

asked 30 Nov '17, 22:13

montycs's gravatar image

0★montycs
1057
accept rate: 0%

edited 30 Nov '17, 22:13


Consider you only know how to move one ring.

Now you are asked to move 4 rings from tower A to tower C.

Understand this notation $<$n P Q R$>$, this means I want to move n rings from P to Q using R, we are going to pass n = 4, P = A, Q = C, R = B in the function.

Now we have $<$4 A C B$>$ i.e. move 4 rings from A to C using B.

You : I want to move 4 rings from A to C.$<$4 A C B$>$ (our first function call)

Me : move 3 rings from A to B $<$3 A B C$>$ (first recursive call). alt text

then move one (yellow) ring from A to C $<$1 A C B$>$ (this is the only move you know). alt text

then move those three rings from B to C $<$3 B C A$>$ (we will make this call when we have moved 3 rings from A to B).

thus, **a <4 A C B> call is <3 A B C>,<1 A C B>,<3 B C A> executed in order.

You: I don't know how to move 3 rings from A to B(thus we have a three ring problem <3 A B C> ).

ME: move 2 rings from A to C <2 A C B> (second recursive call). alt text

<1 A B C> alt text

then <2 C B A > alt text

thus a <3 A B C> call is <2 A C B><1 A B C><2 C B A> executed in order.****

But the thing is you didn't know how to how to move the 2 rings<2 A C B >.

thus, we have a 2 ring problem.<2 A C B>(third recursive call).

this is how <2 A C B> executes (you know all the moves in this call as you know how to move 1 ring):-

<2 A C B> call is <1 A B C> <1 A C B > <1 B C A> executed in order

<1 A B C> return; alt text

<1 A C B >return; alt text

<1 B C A>return; alt text

this completes the <2 A C B> call, hence it also returns to the calling function

<3 A B C >;

next is <1 A B C> return; alt text

next call is made to <2 C B A> all the subsequent move are the base condition recursive calls

<1 C A B>return; alt text

<1 C B A> return; alt text

<1 A B C> return; alt text

This concludes the <3 A B C> call and it returns;

Next call is <1 A C B> return; alt text

Next call is <3 B C A>

you must have an idea now how it would be done.

<3 B C A> is <2 B A C><1 B C A><2 A C B>

now we will execute <2 B A C>

<2 B A C> is <1 B C A><1 B A C ><1 C A B>executed in order.

<1 B C A>return; alt text

<1 B A C >return; alt text

<1 C A B>return; alt text

this concludes the <2 B A C> part of <3 B C A>. i.e. <2 B A C>returns;

next call is:-

<1 B C A>return; alt text

next call is <2 A C B>

<2 A C B> is <1 A B C><1 A C B><1 B C A> executed in order.

<1 A B C>return; alt text

<1 A C B>return; alt text

<1 B C A>return; alt text

<2 A C B> returns; alt text

<3 B C A> returns;

<4 A C B >returns;

You: I want to move n rings from A to C.<n a="" c="" b="">
Me: $<$n-1 A B C$>$$<$1 A C B$>$$<$n-1 B C A$>$....
Source : Quora

link

answered 30 Nov '17, 22:46

codex0196's gravatar image

2★codex0196
3579
accept rate: 16%

edited 30 Nov '17, 22:52

@codex0196 please check my answer

(02 Dec '17, 16:16) montycs0★

@montycs Sorry for the late reply, I was busy in my exams so thats why i was not able to answer.

(01 Jan '18, 12:48) codex01962★

Hey @codex0196 thanks for such detailed answer.. But can you help me with the order of execution here.. See the first step is < n-1, A, B, C > i.e move n-1 disks from A to B so when the execution reaches this point so function call would be returning to this function itself right? i.e after < n-1, A, B, C > the next call should be <n-2, a,b,c=""> until n==1 right?

link

answered 02 Dec '17, 16:15

montycs's gravatar image

0★montycs
1057
accept rate: 0%

edited 02 Dec '17, 16:17

@montycs Figure it out by yourself because it is just a basic thing. If you can figure it out an aptitude will be built and it will help you in future.

(01 Jan '18, 12:47) codex01962★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×348

question asked: 30 Nov '17, 22:13

question was seen: 710 times

last updated: 01 Jan '18, 12:48