fork(2) download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int moves;
  5. /*
  6.   We have three pegs. On each of these pegs is a series
  7.   of disks decreasing in size from the bottom of the peg to the top of the peg. The goal is to move
  8.   all these disks to another peg following these rules:
  9.   -Only one disk can be moved at a time.
  10.   -Only the topmost disk of any given peg can be moved to another peg.
  11.   -A larger disk cannot be placed ontop a smaller disk.
  12.  
  13.   Params:
  14.   diskSize refers to the maximum number of disks we wish to move. If we have 5 disks and we wish
  15.   to move all five disks to another peg then this value should be 5.
  16.   5 = largest disk and 1 = smallest disk.
  17.  
  18.   source is the peg where the disks currently exist.
  19.  
  20.   dest is the peg we want the disks to be moved to.
  21.  
  22.   spare is the peg that temporally stores disks. This is necessary in order for us to shuffle disks
  23.   around without violating the rules.
  24. */
  25. void hanoi(int diskSize, int source, int spare, int dest)
  26. {
  27.  
  28. if (diskSize < 1) return;
  29.  
  30. cout << "Goal: Move disks 1 to " << diskSize << " from pin " << source << " to pin " << dest << endl;
  31.  
  32. //Move all disks smaller than this one over to the spare.
  33. //So if diskSize is 5, we move 4 disks to the spare. This leaves us with 1 disk
  34. //on the source peg.
  35. //Note the placement of the params.
  36. //We are now using the dest peg as the spare peg. This causes each recursion to ping-pong
  37. //the spare and dest pegs.
  38. hanoi(diskSize - 1, source, dest, spare);
  39.  
  40. //Move the remaining disk to the destination peg.
  41. cout << "Move disk " << diskSize << " from peg " << source << " to peg " << dest << endl;
  42. moves++;
  43.  
  44. //Move the disks we just moved to the spare back over to the dest peg.
  45. hanoi(diskSize - 1, spare, source, dest);
  46. }
  47.  
  48. int main()
  49. {
  50. moves = 0;
  51. //Move all 3 disks from peg 1 to peg 2 using peg 2 as a temporary.
  52. hanoi(3, 1, 2, 3);
  53. cout << "Done in " << moves << " moves." << endl;
  54. return 0;
  55. }
  56.  
Success #stdin #stdout 0s 3460KB
stdin
Standard input is empty
stdout
Goal: Move disks 1 to 3 from pin 1 to pin 3
Goal: Move disks 1 to 2 from pin 1 to pin 2
Goal: Move disks 1 to 1 from pin 1 to pin 3
Move disk 1 from peg 1 to peg 3
Move disk 2 from peg 1 to peg 2
Goal: Move disks 1 to 1 from pin 3 to pin 2
Move disk 1 from peg 3 to peg 2
Move disk 3 from peg 1 to peg 3
Goal: Move disks 1 to 2 from pin 2 to pin 3
Goal: Move disks 1 to 1 from pin 2 to pin 1
Move disk 1 from peg 2 to peg 1
Move disk 2 from peg 2 to peg 3
Goal: Move disks 1 to 1 from pin 1 to pin 3
Move disk 1 from peg 1 to peg 3
Done in 7 moves.