1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
//Author Juan Enrique Hernández Pérez
//TowerOfHanoiIterative.cpp
//Iterative solution for the Towers of hanoi problem
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
bool isEven(int disks); //function prototype isEven
int moves(int disks); //function prototype moves
void MoveTower(int disks,int numberOfMovesToSolve,int src,int tmp,int dst);
//function prototype MoveTower
void MoveSingle(int src,int dst); //function prototype MoveSingle
int whichDisk(int movement,int disks); //function prototype whichDisk
int patronNumber(int movement,int whichDisk, int disks); //function prototype patronNumber
int main(){
int disks;
int src,tmp,dst;
int numberOfMovesToSolve;
cout<<"Number of disks: ";
cin>>disks;
cout<<"Initial peg: ";
cin>>src;
cout<<"Temporal peg: ";
cin>>tmp;
cout<<"Destination peg: ";
cin>>dst;
numberOfMovesToSolve=moves(disks);
MoveTower(disks,numberOfMovesToSolve,src,tmp,dst);
return 0;//indicates success
}//end main
bool isEven(int disks)
{
bool isEven;
if(disks%2==0) isEven=true;
else isEven=false;
return isEven;
}//end function isEven
int moves(int disks)
{
int moves=0;
for(int i=1;i<=disks;i++){
moves=(moves*2)+1;
}//end loop for
return moves;
}//end function moves
void MoveTower(int disks,int numberOfMovesToSolve,int src,int tmp,int dst){
if(!isEven(disks)){ //isNotEven
for(int movement=1;movement<=numberOfMovesToSolve;movement++){
switch(patronNumber(movement,whichDisk(movement,disks),disks)){
case 1:
if(!isEven(whichDisk(movement,disks)))MoveSingle(src,dst);
else MoveSingle(src,tmp);
break;
case 2:
if(!isEven(whichDisk(movement,disks)))MoveSingle(dst,tmp);
else MoveSingle(tmp,dst);
break;
case 3:
if(!isEven(whichDisk(movement,disks)))MoveSingle(tmp,src);
else MoveSingle(dst,src);
break;
}//end switch
}//end loop for
}else{ //isEven
for(int movement=1;movement<=numberOfMovesToSolve;movement++){
switch(patronNumber(movement,whichDisk(movement,disks),disks)){
case 1:
if(!isEven(whichDisk(movement,disks)))MoveSingle(src,tmp);
else MoveSingle(src,dst);
break;
case 2:
if(!isEven(whichDisk(movement,disks)))MoveSingle(tmp,dst);
else MoveSingle(dst,tmp);
break;
case 3:
if(!isEven(whichDisk(movement,disks)))MoveSingle(dst,src);
else MoveSingle(tmp,src);
break;
}//end switch
}//end loop for
}//end if...else
}//end function MoveTower
void MoveSingle(int src,int dst){
cout<<src<<"--->"<<dst<<'\n';
}//end function MoveSingle
int whichDisk(int movement,int disks){
int whichDisk;
int start=1;
int increment=2;
int movements=moves(disks);
for(int i=1;i<=disks;i++){
for(int j=start;j<=movements;j+=increment){
if(movement==j){
whichDisk=i;
}//end if
}//end inner loop
start*=2;
increment*=2;
}//end outer for loop
return whichDisk;
}//end function whichDisk
int patronNumber(int movement,int whichDisk,int disks){
int patronNumber=0;
int increment=2;
int start=1;
for(int i=1;i<=disks;i++){
if(i==whichDisk){
for(int j=start;j<=movement;j+=increment){
patronNumber++;
if(patronNumber==3&&j!=movement)patronNumber=0;
}//end inner for
}//end if
start*=2;
increment*=2;
}//end for loop
return patronNumber;
}//end patronNumber
|
