c++代碼
#include<iostream>
struct Node{
int data;
Node* next;
};
class Stack{
public:
Stack(){
top = 0;
}
~Stack(){
Node* next;
while(top){
next = top->next;
delete top;
top = next;
}
}
void push(int d){
Node* p = new Node;
p->data = d;
p->next = top;
top = p;
}
int pop(){
int d;
Node* p = top;
d = top->data;
top = top->next;
delete p;
return d;
}
Node* top;
};
int count = 1;
Stack s[3];
void Hanoi(char A, char B, char C, int n){
if (n == 0)
return;
int a = A - 'A';
int c = C - 'A';
Hanoi(A, C, B, n-1);
std::cout<<count++<<":"<<A<<"->"<<C<<std::endl;
s[c].push(s[a].pop());
Hanoi(B, A, C, n-1);
}
int main(){
char A, B, C;
int n;
std::cin>>A>>B>>C>>n;
for(int i = n; i > 0; i--){
s[0].push(i);
}
Hanoi(A, B, C, n);
system("pause");
return 0;
}
復雜度分析
空間
按要求利用鏈表棧實現(xiàn)盗胀，應為O(n)時間
核心步驟是Hanoi函數(shù)的遞歸诀浪，次數(shù)看count即可，應為O(2^n)
有任何問題請回復提出纯蛾。然后歡迎關注微信公眾號格物致愚：
格物致愚
