Chinaunix首页 | 论坛 | 博客
  • 博客访问: 458798
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: C/C++

2011-08-27 22:51:13

一 简介

回溯法是一种非常常用的算法:在一个解空间中寻找一个满足限制条件的解,则继续寻找下一个,如果找不到,则抹去该解,回溯上一个,基本思路是:

1. 非递归版

  1. while(可行解范围内)
  2.     {
  3.      if(一个可行解产生了) 打印出来;
  4.      for(寻找可行解的解空间)
  5.         if(满足可行解的限制条件)
  6.             加入可行解空间
  7.      if(是否已经找到一个可行解)
  8.         继续寻找下一个
  9.      else     抹去该可行解,回溯到上一个
  10.     }
2.递归版
  1. function (int k)
  2.     {
  3.     if(一个可行解产生了) 打印出来;
  4.     寻找满足该k层的解;
  5.         if(找到了k层的可行解)
  6.      寻找下一层,function(k++);
  7.      else 回溯到上一层,抹去该k层的痕迹,function(k--);
  8.     }
n皇后问题

一个n*n矩阵中放置n颗棋子,要求每个棋子之间必须不能同一行列,正对角线,斜对角线放置。

1.非递归版
  1. /*
  2. * n 皇后问题:
  3. * 棋盘中不能横 竖 斜着放置
  4. */

  5. #include <stdio.h>
  6. #include <stdlib.h>

  7. #define N num
  8. //检查行 列 横竖对角线是否合法
  9. static int num;//记录皇后的阶数
  10. int x[20];//记录每一列的数据

  11. int isPlace(const int row,const int col)
  12. {
  13.     int i;
  14.     for(i=0;i<row;i++)
  15.         if((x[i]==col)||(x[i]-i==col-row)||(x[i]+i==col+row))
  16.             return 0;
  17.     return 1;
  18. }

  19. void nQueue()
  20. {
  21.    int k=0,i;
  22.    while(k>=0)
  23.    {
  24.     if(k==N)
  25.     {
  26.     for(i=0;i<N;i++)
  27.     printf(" %d ",x[i]);
  28.      printf("\n");
  29.      k=N-1;
  30.     }
  31.     for(i=x[k]+1;i<N;i++)
  32.     if(isPlace(k,i))
  33.     {
  34.      x[k]=i;
  35.      k++;
  36.      break;
  37.     }
  38.     if(i==N)
  39.     {
  40.         x[k]=-1;//抹去上次的痕迹
  41.      k--;
  42.     }
  43.    }
  44. }

  45. void main(int argc,char*args[])
  46. {    
  47.     int i;
  48.     if(argc!=2)
  49.     {
  50.     fprintf(stderr,"usage:%s num!\n",args[0]);
  51.     exit(-1);
  52.     }
  53.     num=atoi(args[1]);
  54.     for(i=0;i<N;i++)
  55.         x[i]=-1;
  56.     nQueue();
  57.     printf("It's over!\n");
  58. }
2.递归版
  1. /*
  2. *n皇后问题递归实现
  3. */
  4. #include <stdio.h>
  5. #include <stdlib.h>

  6. #define N num

  7. static int num;//记录皇后的阶数
  8. int x[20];//记录每一列的数据

  9. int isPlace(int row,int col)
  10. {
  11.     int i;
  12.     for(i=0;i<row;i++)
  13.     if(x[i]==col||(x[i]-i==col-row)||(x[i]+i==col+row))
  14.         return 0;
  15.     return 1;
  16. }

  17. void nQueue(int k)
  18. {
  19.     int i;
  20.     if(k==N)
  21.     {
  22.      for(i=0;i<N;i++)
  23.      printf(" %d ",x[i]);
  24.      printf("\n");
  25.      k=N-1;
  26.     }
  27.     for(i=x[k]+1;i<N;i++)
  28.     if(isPlace(k,i))
  29.     {
  30.      x[k]=i;
  31.      k++;
  32.      break;
  33.     }
  34.     if(i==N)
  35.     {
  36.     x[k]=-1;
  37.     k--;
  38.     }
  39.     if(0==k&&x[k]==N-1)
  40.     {
  41.      printf("It's over!\n");
  42.      return;
  43.     }
  44.     nQueue(k);
  45. }
  46. void main(int argc,char* args[])
  47. {
  48.     int i;
  49.     if(argc!=2)
  50.     {
  51.     fprintf(stderr,"usage:%s num!\n",args[0]);
  52.     exit(-1);
  53.     }
  54.     num=atoi(args[1]);
  55.     for(i=0;i<N;i++) x[i]=-1;
  56.     nQueue(0);
  57. }

阅读(1474) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~