8 Replies - 6216 Views - Last Post: 01 May 2009 - 08:47 PM

#1 AfterBurner66   User is offline

  • D.I.C Head

Reputation: 16
  • View blog
  • Posts: 117
  • Joined: 02-August 08

Towers of Hanoi

Post icon  Posted 12 September 2008 - 03:25 PM

Hi all!
As a person who has not a Computer Science degree(I am a poor web developer!),but having much desire to learn as much as I can about CS topics,I have a (maybe easy :huh:) question about the recursive algorithm that solves the "Towers of Hanoi" puzzle.
I can understand that generally,having n discs and A,B,C pegs,the strategy is:
1.move (n-1) discs from A to B.
2.move nth disc from A to C.
3.move the (n-1) discs from B to C.Done!
but this is implemented in whatever procedural language with a function,and the one thing that changes,is the order of arguments.OK so far but how do we assure that algorithm does recursively the moves that must be done and not something else?In other words how to be sure that changing of passed arguments leads to the correct solution?Because of two recursive functions used(I have studied implementations in Pascal,C,Java so far),it was difficult for me to construct a tracetable,because at the point of second recursive function call,things get much complicated I think,due to the fact that on return of function call,first recursive function is encountered first and after that we go to second etc.
So is there any idea about how to construct a tracetable "safely",or at least how to trace the whole procedure?
I tried also to solve the problem with the physical moves of discs required,but I didn't manage to map this to the recursive function calls.And something maybe more elementary:in what sense do we have recursion in this problem/
Any help or resource would be appreciated.Thanks in advance!

Is This A Good Question/Topic? 1
  • +

Replies To: Towers of Hanoi

#2 AdamSpeight2008   User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Towers of Hanoi

Posted 12 September 2008 - 06:42 PM

I hope this helps. It is a vb.net console app version.
When run it will visually show you the current depth of recursion and the variables values.
Module Module1
    Const ShowTrace As Boolean = True
    Dim level As Integer = 0
    Dim i As Integer = 0
    Dim c As Char = " "

    Sub Main()
        Hanoi(6)
        Console.ReadKey()
    End Sub

    Private Sub Hanoi(ByVal n As Integer)
        i = 0
        Call DoHanoi(1, 2, 3, n)
    End Sub


    Private Sub DoHanoi(ByVal f As Integer, ByVal u As Integer, ByVal t As Integer, ByVal n As Integer)
        If ShowTrace Then level += 1
        If ShowTrace Then Console.WriteLine(Strings.StrDup(level, c) & "Entering DoHanoi({0},{1},{2},{3})", f, u, t, n)
        If n = 1 Then
            i += 1
            Console.WriteLine(IIf(ShowTrace, Strings.StrDup(level, c), "") & "{0}. Move {1} to {2} ", i, f, t)
        Else
            DoHanoi(f, t, u, n - 1)
            DoHanoi(f, u, t, 1)
            DoHanoi(u, f, t, n - 1)
        End If
        If ShowTrace Then Console.WriteLine(Strings.StrDup(level, c) & "Exiting DoHanoi")
        If ShowTrace Then level -= 1

    End Sub
End Module


Was This Post Helpful? 1
  • +
  • -

#3 AfterBurner66   User is offline

  • D.I.C Head

Reputation: 16
  • View blog
  • Posts: 117
  • Joined: 02-August 08

Re: Towers of Hanoi

Posted 13 September 2008 - 07:41 PM

Thanks a lot AdamSpeight2008!This really helps.Though I don't know much VB,this is the better "towers of hanoi" program I've ever seen, by far.I can trace the procedure very well.Thanks again!
Was This Post Helpful? 0
  • +
  • -

#4 crazydia143   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 30-March 09

Re: Towers of Hanoi

Posted 30 March 2009 - 08:35 AM

can ne1 pls give me src code 4 TOWERS OF HANOI using openGL.
in DEV C++
Was This Post Helpful? 0
  • +
  • -

#5 Gloin   User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Towers of Hanoi

Posted 30 March 2009 - 09:37 AM

*Sigh*
Was This Post Helpful? 0
  • +
  • -

#6 firebolt   User is offline

  • D.I.C Lover
  • member icon

Reputation: 93
  • View blog
  • Posts: 5,561
  • Joined: 20-February 09

Re: Towers of Hanoi

Posted 03 April 2009 - 05:19 AM

haha... why not i just say:

anyone have the code for VB6
Was This Post Helpful? 0
  • +
  • -

#7 griffinfujioka   User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 32
  • Joined: 26-October 08

Re: Towers of Hanoi

Posted 30 April 2009 - 06:03 PM

recursion :)
Was This Post Helpful? 0
  • +
  • -

#8 mattman059   User is offline

  • Epic Awesomeness
  • member icon

Reputation: 15
  • View blog
  • Posts: 538
  • Joined: 23-October 06

Re: Towers of Hanoi

Posted 30 April 2009 - 06:55 PM

View Postcrazydia143, on 30 Mar, 2009 - 09:35 AM, said:

can ne1 pls give me src code 4 TOWERS OF HANOI using openGL.
in DEV C++




*Sigh*..It's times like this when i want to say "Sure!"

cout << "The answer is: "<< endl;
cout << "IF (WINDOWS) THEN : Press Windows Key, U, U...Then step away" << endl;
cout << "IF (*NIX) THEN: Open Console, type sudo rm -r, your password ...Then step away" << endl;


Was This Post Helpful? 0
  • +
  • -

#9 jcmaster2   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 183
  • Joined: 27-April 09

Re: Towers of Hanoi

Posted 01 May 2009 - 08:47 PM

Towers of Hanoi is typically found in almost every programming book in most languages with recursion....look it up...also the web...
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1