n阶hanoi的非递归解法

nuclearweapon

#define MAX 300
#include<stdio.h>
struct state_style{
       int  num;
       char target;
       char middle;
       char source;};
struct state_style stack[MAX];
int s,top;
void set_state(int num,char x,char y,char z,struct state_style *state)
{
state->num=num;
state->source=x;
state->middle=y;
state->target=z;
}

void push(struct state_style state)
{
stack[top++]=state;
}

void pop(struct state_style *state)
{
*state=stack[--top];
}

int empty()
{
if (top==0) return 1;
return 0;
}

void han(int n)
{
struct state_style state;
char temp;
set_state(n,'x','y','z',&state);
do{
    if (state.num>0)
       {
        push(state);
        set_state(state.num-1,state.source,state.target,state.middle,&state);
       }
    else {
            pop(&state);
            printf("%d: Move %d from %c to %c.\n",++s,state.num,state.source,state.target);
            set_state(state.num-1,state.middle,state.source,state.target,&state);
             
         }
  }while(!((state.num==0)&&empty()));
}
         
         
               
int main()
{
int n;
scanf("%d",&n);
han(n);
}

quanliking

while(!((state.num==0)&&#8709;()));
这句看不懂。
还有感觉思路和递归一样呀！
不过递归是系统帮忙管理堆栈，你的就是自己做个堆栈，然后自己管理了。
这样能算真正非递归吗？

nuclearweapon

那一句因该是while(!((state.num==0)&&empty()))
如果直接用递归时效和空间不如此算法
这是一类问题都可以类似处理

kensta

关键部分在最后面，前面的是用于验证和演示的
http://www.156ok.com/article/article_list.asp?account_id=843