c：递归算法的三个demo：八皇后问题、台阶问题、汉诺塔-白红宇

c：递归算法的三个demo：八皇后问题、台阶问题、汉诺塔

阅读量：6591 次

发布时间：2019-06-24

本文共 3029 字，大约阅读时间需要 10 分钟。

一：八皇后问题

一个8*8的棋盘中放有8个皇后，每两个皇后不能处在同一行同一列同一斜线中

（在我用vc++测试时只出来52种结果，但别人用我的代码测出来了所有答案，我怀疑是函数栈不够的原因，还请大神指点）

#include 
    
     #include 
     
      #include 
      
       typedef struct Arr{    int len;    int cnt;    int * pBase;}ARR,* PARR;void init_arr(PARR pArr,int val){//初始化    pArr->pBase=(int *)malloc(sizeof(int)*val);    if(NULL==pArr->pBase){        printf("内存不足");        exit(-1);    }    pArr->cnt=0;    pArr->len=val;}bool is_full(PARR pArr){//判满    if(pArr->cnt==pArr->len){        return true;    }else{        return false;    }}bool is_empty(PARR pArr){//判空    if(pArr->cnt==0){        return true;    }else{        return false;    }}bool append_arr(PARR pArr,int val){//追加    if(is_full(pArr)){        printf("已满");        return false;    }else{        pArr->pBase[pArr->cnt]=val;        pArr->cnt=pArr->cnt+1;        return true;    }}void show_arr(PARR pArr){//遍历    for(int i=0;i
       
        cnt;i++){        printf("%d    ",pArr->pBase[i]);    }    printf("\n");}bool check(PARR pArr,int y){    for(int i=0;i
        
         cnt;i++){        if(pArr->pBase[i]==y||abs(pArr->pBase[i]-y)==abs(pArr->cnt-i)){            return false;        }     }    return true;}int pop(PARR pArr){//回溯    pArr->cnt=pArr->cnt-1;    return pArr->pBase[pArr->cnt];}void f(PARR pArr,int y,int z){//y代表要插入的值，z代表结果个数    int x=pArr->cnt+1;    if(x==1&&y<9){        append_arr(pArr,y);        f(pArr,1,z);    }else if(x==1&&y==9){        printf("结束");    }else if(x>1&&x<9&&y<9){        if(check(pArr,y)){            append_arr(pArr,y);            f(pArr,1,z);        }else{            f(pArr,y+1,z);        }    }else if(x>1&&x<9&&y==9){        int val=pop(pArr);        f(pArr,val+1,z);    }else if(x==9){        z++;        show_arr(pArr);        printf("结果个数：%d\n",z);        int temp=pop(pArr);        f(pArr,temp+1,z);    }}int main(void){    ARR arr;    init_arr(&arr,8);    f(&arr,1,0);    return 0;}

二：台阶问题

一个人每次可以走1、2、3个台阶，共有5个台阶，求可能情况

（index--总是忘，要保证实现一种情况后进行第二种情况的时候各项参数都是正确的）

#include 
    
     #define STAIR_NUM 5int index=0;int list[STAIR_NUM];void show(){    for(int i=0;i
     
      
       =1){        list[index]=1;        index++;        f(n-1);        index--;    }    if(n>=2){        list[index]=2;        index++;        f(n-2);        index--;    }    if(n>=3){                list[index]=3;        index++;        f(n-3);        index--;    }}int main(void){    f(5);    return 0;}

三：汉诺塔

    #include 
    
         #include 
     
          #include 
      
           void f(int n,char x,char y,char z){                if(n==1){            printf("将编号为1的盘子从%c柱子移到%c\n",x,z);        }else{            f(n-1,x,z,y);            printf("将编号为%d的盘子从%c柱子移到%c\n",n,x,z);            f(n-1,y,z,x);        }    }    int main(void){        char ch1='A';        char ch2='B';        char ch3='C';        int n;        printf("请输入盘子个数：");        scanf("%d",&n);        f(n,'A','B','C');        return 0;    }