7-17 汉诺塔的非递归实现

标签：柱子 17 递归 int han char 汉诺塔 before

借助堆栈以非递归（循环）方式求解汉诺塔的问题（n, a, b, c），即将N个盘子从起始柱（标记为“a”）通过借助柱（标记为“b”）移动到目标柱（标记为“c”），并保证每个移动符合汉诺塔问题的要求。

输入格式:

输入为一个正整数N，即起始柱上的盘数。

输出格式:

每个操作（移动）占一行，按柱1 -> 柱2的格式输出。

输入样例:

3

 

输出样例:

a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

 

代码：

#include<bits/stdc++.h>
using namespace std;
stack<int>a[3];
char s[3]={'a','b','c'};
bool move(int before,int after){
    if(a[before].empty()){
        return false;
    }
    if(!a[after].empty()){
        if(a[after].top()-a[before].top()<0)
            return false;
    }
    a[after].push(a[before].top());
    a[before].pop();
    printf("%c -> %c\n",s[before],s[after]);
    return true;
    
}
int main(){
    int n,count=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        a[0].push(n-i);
    }
    if(n%2==1){
        s[1]='c';
        s[2]='b';
    }
    while(++count){
        move((count-1)%3,(count)%3);
        if(!move((count-1)%3,(count+1)%3))
            if(!move((count+1)%3,(count-1)%3))
                break;
    }
    
    return 0;
}

 

 

 

总结：

一个美国学者总结得到：所有的汉诺塔移动可以总结为重复的两步，我们假设现在最小的圆盘在a柱子上，柱子为a，b，c

第一步：将最小圆盘移动到下一个柱子上，也就是b

第二步：对a柱子和c柱子进行顶上最小的元素进行判断，把小一点的那个圆盘移动到大一点的那个圆盘（有空则摞在空柱子上）。

重复上述两步就可以得到答案。

注意：这样得到的最后的答案不一定是摞在c上，如果N是偶数将摞在b上，所以如果N是偶数我们就令第二个柱子为c，第三个柱子为b，这样就一定最后是摞在c上的。

 

补充递归写法：

 

#include<stdio.h>
void han(int n,char a,char b,char c)
{
    if(n==1) printf("%c -> %c\n",a,c);
    else
    {
        han(n-1,a,c,b);
        printf("%c -> %c\n",a,c);
        han(n-1,b,a,c);
        
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    han(n,'a','b','c');
    return 0;
}

 

标签：柱子,17,递归,int,han,char,汉诺塔,before
From： https://www.cnblogs.com/yccy/p/16607939.html