Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Don't understand tower of Hanoi Program Stack

  1. Feb 10, 2017 #1
    1)I have two questions. I don't know why pegs[0].push(i); is used inside the for loop in the first void function. It makes sense that the program needs rings to be placed on a stack. But why pegs[0]? why not pegs[i]?
    Mod note: Edited pegs[ i] above to prevent the following text to be rendered as italic.
    2) What is the array <stack<int>,kNumPegs>pegs ? Is it a vector? Vectors have that <> symbol. And why is the stack inside? Is it because we need 3 pegs?


    3)Also, I can't get this to implement in the main. I got this code from my book but they didn't have a main function to test it. So I got a bunch of errors. My C++ is a bit rusty so I don't know what should be done in the main to implement this.




    Code (C):


    #include <iostream>

    using namespace std;
    const int kNumPegs=3;

    void ComputeTowerHanoi(int num_rings){
      array <stack<int>,kNumPegs>pegs; //initialize pegs
      for(int i=num_rings; i>=1; --i){
        pegs[0].push(i);
     
     
      }
     
     
      ComputeTowerHanoiSteps(num_rings,pegs,0,1,2);
     
    }


    void ComputeTowerHanoiSteps(int num_rings_to_move,array<stack<int>,kNumPegs>&pegs, int from_peg,int to_peg,int use_peg){
     
    if(num_rings_to_move>0){
     
      ComputeTowerHanoiSteps(num_rings_to_move-1,pegs,from_peg,use_peg,to_peg);
      pegs[to_peg].push(pegs[from_peg].top());
      pegs[from_peg].pop();
      cout<<"Move from peg "<<from_peg<<" to peg "<<to_peg<<endl;
      ComputeTowerHanoiSteps(num_rings_to_move-1,pegs,use_peg,to_peg,from_peg);
     
    }
     
     
     
     
    }


    int main() {
        ComputeTowerHanoi(3);
    }



     
     
    Last edited by a moderator: Feb 11, 2017
  2. jcsd
  3. Feb 10, 2017 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    All the disks start on the first peg, peg[0].
    The disks on each of the pegs are handled using the template for a LIFO stack (see http://www.cplusplus.com/reference/stack/stack/ ). That gives you methods for putting a disk on top (push) and removing the top disk (pop).
    This code uses C++ features like templates. Be sure that you are compiling and using it as you should for C++ rather than C. Beyond that, you need to say what the error messages are so you can get good help. The first error message should be addressed first, because the ones that follow may just be dominoing from the first.
     
  4. Feb 11, 2017 #3


    The error message is

    "main.cpp: In function 'void ComputeTowerHanoi(int)': main.cpp:7:3: error: 'array' was not declared in this scope"

    Which is strange because it is delared inside the function call for the purposes of computing the answer. It would disappear later, but that shouldn't matter.
     
  5. Feb 11, 2017 #4

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    I don't have a compiler here, so I can't help much. Try this at the top:
    #include <array>

    and reference the array and it's methods (xxxyyy) using "std::array" and "std::xxxyyy"
    (see http://en.cppreference.com/w/cpp/container/array )
    Maybe some of the other includes in the reference are also needed.

    Beyond that, I can't help since I don't have a C++ compiler and don't remember specifics. Hopefully someone else can provide more help.
     
  6. Feb 11, 2017 #5

    Mark44

    Staff: Mentor

    In addition to what @FactChecker said, you have to also #include <stack>.

    Also, in the code below, which is the code cited in the compiler error, since you haven't included the necessary header files, the compiler doesn't know what to make of "array" and "stack." The comment is misleading, as there is no initializing going on. This is only a declaration, and only a partial one at that.
    Before the array can be initialized (values stored in it), each of the three stack objects has to also be initialized.
    Code (C):
    void ComputeTowerHanoi(int num_rings){
      array <stack<int>,kNumPegs>pegs; //initialize pegs
      for(int i=num_rings; i>=1; --i){
        pegs[0].push(i);  
    }
     
  7. Feb 13, 2017 #6

    Svein

    User Avatar
    Science Advisor

    Here is a program stub in Pascal that implements the Towers of Hanoi.
    Code (Text):


    Const
      Hmax = 12;
      HWunit = 8;
      HSpace = 160;

    Type
    Skive = record
      sz: integer;
      w, h: integer;
      c: TColor;
      end;

    Stang = record
       Ramme: TRect;
       Tykkelse: integer;
       Antall: integer;
       stabel: Array[1..Hmax] of Skive;
       end;

    procedure Hanoi;
    var
      n: integer;
      Tavle: TRect;
      Rep: Variant;
      Stenger: Array[1..3] of Stang;

    Procedure Setup;
    Var
      i, j, k: Integer;
    Begin
      For i:=1 to 3 Do Begin
        Stenger[i].Tykkelse := HWunit div 2;
        Stenger[i].Ramme.Left := (i-1)*HSpace + xoffset;
        Stenger[i].Ramme.Right := Stenger[i].Ramme.Left + HSpace - 16;
        Stenger[i].Ramme.Bottom := Height;
        Stenger[i].Ramme.Top := Height - (Hmax + 4)*HWunit;
        if (i=1) then with Stenger[i] do begin
          Antall := n;
          for j := 1 to Antall do begin
            k := Antall + 1 - j;
            stabel[j].sz := k;
            stabel[j].w := (k + 2)*HWunit;
            stabel[j].h := HWunit;
            case j of
              1: stabel[j].c := clBlue;
              2: stabel[j].c := clFuchsia;
              3: stabel[j].c := clGreen;
              4: stabel[j].c := clLime;
              5: stabel[j].c := clMaroon;
              6: stabel[j].c := clNavy;
              7: stabel[j].c := clOlive;
              8: stabel[j].c := clPurple;
              9: stabel[j].c := clRed;
              10: stabel[j].c := clSilver;
              11: stabel[j].c := clTeal;
              12: stabel[j].c := clYellow;
              end;
            end;
          end else
          Stenger[i].Antall := 0;
        end;
    End;

    Procedure paintStack(i: integer);
    var
      j, k, l: integer;
      R: TRect;
    Begin
      if ((i>=1) and (i<=3)) then
        with Stenger[i] do Begin
          Lerret.Canvas.Brush.Color := clBtnFace;
          Lerret.Canvas.FillRect(Ramme);
          R.Left := Ramme.Left + 2;
          R.Right := Ramme.Right - 2;
          R.Bottom := Ramme.Bottom;
          R.Top := Ramme.Bottom - Tykkelse;
          Lerret.Canvas.Brush.Color := clAqua;
          Lerret.Canvas.FillRect(R);
          R.Bottom := Ramme.Bottom;
          R.Top := Ramme.Top;
          l := (Ramme.Right - Ramme.Left - Tykkelse) div 2;
          R.Left := Ramme.Left + l;
          R.Right := R.Left + Tykkelse;
          Lerret.Canvas.FillRect(R);
          k := Tykkelse + 1;
          l := (Ramme.Right + Ramme.Left) div 2;
          for j := 1 to Antall do begin
            R.Bottom := Ramme.Bottom - k;
            R.Top := R.Bottom - stabel[j].h;
            k := k + stabel[j].h + 1;
            R.Left := l - (stabel[j].w div 2);
            R.Right := R.Left + stabel[j].w;
            Lerret.Canvas.Brush.Color := stabel[j].c;
            Lerret.Canvas.FillRect(R);
            end;
        end;
    End;

    procedure PaintAll;
    Var
      p: integer;
    Begin
      if DoAll then begin
        while (not Lerret.forts) do
          Application.ProcessMessages;
        Lerret.forts := False;
        end;
      for p := 1 to 3 do
        paintStack(p);
    End;

    Procedure Move(a, b, c, num: Integer);
    Var
      na, nb: integer;
    Begin
      na := Stenger[a].Antall;
      nb := Stenger[b].Antall;
      if (num=1) then begin
        Inc(nb);
        Stenger[b].stabel[nb] := Stenger[a].stabel[na];
        Stenger[b].Antall := nb;
        Dec(na);
        Stenger[a].Antall := na;
        PaintAll;
        end
      else begin
        Move(a, c, b, num - 1);
        Move(a, b, c, 1);
        Move(c, b, a, num -1);
        end;
    End;


     
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Don't understand tower of Hanoi Program Stack
  1. 4 Pegs Hanoi Tower (Replies: 5)

Loading...