|
●漢諾塔算法的非遞歸實現(xiàn)C++源代碼 #include <iostream> using namespace std; //圓盤的個數(shù)最多為64 const int MAX = 64; //用來表示每根柱子的信息 struct st{ int s[MAX]; //柱子上的圓盤存儲情況 int top; //棧頂，用來最上面的圓盤 char name; //柱子的名字，可以是A，B，C中的一個 int Top()//取棧頂元素 { return s[top]; } int Pop()//出棧 { return s[top--]; } void Push(int x)//入棧 { s[++top] = x; } } ; long Pow(int x, int y); //計算x^y void Creat(st ta[], int n); //給結(jié)構(gòu)數(shù)組設(shè)置初值 void Hannuota(st ta[], long max); //移動漢諾塔的主要函數(shù) int main(void) { int n; cin >> n; //輸入圓盤的個數(shù) st ta[3]; //三根柱子的信息用結(jié)構(gòu)數(shù)組存儲 Creat(ta, n); //給結(jié)構(gòu)數(shù)組設(shè)置初值 long max = Pow(2, n) - 1;//動的次數(shù)應(yīng)等于2^n - 1 Hannuota(ta, max);//移動漢諾塔的主要函數(shù) system(“pause”); return 0; } void Creat(st ta[], int n) { ta[0].name = ‘A’; ta[0].top = n-1; //把所有的圓盤按從大到小的順序放在柱子A上 for (int i=0; i<n; i++) ta[0].s = n - i; //柱子B，C上開始沒有沒有圓盤 ta[1].top = ta[2].top = 0; for (int i=0; i<n; i++) ta[1].s = ta[2].s = 0; //若n為偶數(shù)，按順時針方向依次擺放 A B C if (n%2 == 0) { ta[1].name = ‘B’; ta[2].name = ‘C’; } else //若n為奇數(shù)，按順時針方向依次擺放 A C B { ta[1].name = ‘C’; ta[2].name = ‘B’; } } long Pow(int x, int y) { long sum = 1; for (int i=0; i<y; i++) sum *= x; return sum; } void Hannuota(st ta[], long max) { int k = 0; //累計移動的次數(shù) int i = 0; int ch; while (k < max) { //按順時針方向把圓盤1從現(xiàn)在的柱子移動到下一根柱子 ch = ta[i%3].Pop(); ta[(i+1)%3].Push(ch); cout << ++k << “: “ << “Move disk “ << ch << ” from “ << ta[i%3].name << ” to “ << ta[(i+1)%3].name << endl; i++; //把另外兩根柱子上可以移動的圓盤移動到新的柱子上 if (k < max) { //把非空柱子上的圓盤移動到空柱子上，當(dāng)兩根柱子都為空時，移動較小的圓盤 if (ta[(i+1)%3].Top() == 0 || ta[(i-1)%3].Top() > 0 && ta[(i+1)%3].Top() > ta[(i-1)%3].Top()) { ch = ta[(i-1)%3].Pop(); ta[(i+1)%3].Push(ch); cout << ++k << “: “ << “Move disk “ << ch << ” from “ << ta[(i-1)%3].name << ” to “ << ta[(i+1)%3].name << endl; } else { ch = ta[(i+1)%3].Pop(); ta[(i-1)%3].Push(ch); cout << ++k << “: “ << “Move disk “ << ch << ” from “ << ta[(i+1)%3].name << ” to “ << ta[(i-1)%3].name << endl; } } } } |
|
|
