C/C++知识点之C语言-回溯
小标 2018-09-19 来源 : 阅读 1148 评论 0

摘要:本文主要向大家介绍了C/C++知识点之C语言-回溯,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。

本文主要向大家介绍了C/C++知识点之C语言-回溯,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。

                      
回溯法解N皇后问题 
 1,代码分析:
使用一个一维数组表示皇后的位置 
 其中数组的下标表示皇后所在的行 
数组元素的值表示皇后所在的列 
 这样设计的棋盘,所有皇后必定不在同一行 
 假设前n-1行的皇后已经按照规则排列好 
 那么可以使用回溯法逐个试出第n行皇后的合法位置 
所有皇后的初始位置都是第1列 
 那么逐个尝试就是从1试到N  
 如果当前行的皇后的位置还是在1到N的合法范围内 
那么首先要判断该行的皇后是否与前几行的皇后互相冲突 
 如果冲突,该行的皇后的位置加1,继续尝试 
如果不冲突,判断下一行的皇后 
 如果已经是最后一行,说明已经找到一个解,输出这个解 
 然后最后一行的皇后的位置加1,继续尝试下一个解 
2,代码实现:

 1 /**************x皇后问题***************/
 2 #include 
 3 #define N 4//自定义皇后的个数
 4 int myabs(int a,int b)
 5 {
 6     return a>b?(a-b):(b-a);
 7 }
 8 int main()
 9 {
10     int i,j,num,a[100];
11     int k;
12     int flag;//设置标志位,用来判断是否满足约束条件
13     i=1;
14     a[1]=1;//设初值
15     num=0;//记录解得个数
16     while(1)
17     {
18         flag=1;
19         for(k=i-1;k>=1;k--)
20         {
21             if((a[k]==a[i])||myabs(a[k],a[i])==(i-k))//满足约束条件
22                 flag =0;//改变标志位,表示不满足条件
23         }
24         if(flag&&(i==N))//输出一组解
25         {
26             num++;
27             for(j=1;j<=N;j++)
28             {
29                 printf("%d",a[j]);
30             }
31             printf(" ");
32             if((num%8)==0)
33             {
34                 printf("\n");
35             }
36         }
37         if(flag&&i<=N)
38         {
39             i++;
40             a[i]=1;//取初值
41             continue;
42         }
43         while(a[i]==N&&i>1)i--;//回溯
44         if(a[i]==N&&i==1)
45         {
46             break;
47         }
48         else
49         {
50             a[i]++;//改变另一条路径
51         }
52     }
53     printf("\n解得个数为%d",num);
54     return 0;
55 }

运行结果:

3,代码实现:

 1 /**************x皇后问题***************/
 2 #include 
 3 #define N 8//自定义皇后的个数
 4 int myabs(int a,int b)
 5 {
 6     return a>b?(a-b):(b-a);
 7 }
 8 int main()
 9 {
10     int i,j,num,a[100];
11     int k;
12     int flag;//设置标志位,用来判断是否满足约束条件
13     i=1;
14     a[1]=1;//设初值
15     num=0;//记录解得个数
16     while(1)
17     {
18         flag=1;
19         for(k=i-1;k>=1;k--)
20         {
21             if((a[k]==a[i])||myabs(a[k],a[i])==(i-k))//满足约束条件
22                 flag =0;//改变标志位,表示不满足条件
23         }
24         if(flag&&(i==N))//输出一组解
25         {
26             num++;
27             for(j=1;j<=N;j++)
28             {
29                 printf("%d",a[j]);
30             }
31             printf(" ");
32             if((num%8)==0)
33             {
34                 printf("\n");
35             }
36         }
37         if(flag&&i<=N)
38         {
39             i++;
40             a[i]=1;//取初值
41             continue;
42         }
43         while(a[i]==N&&i>1)i--;//回溯
44         if(a[i]==N&&i==1)
45         {
46             break;
47         }
48         else
49         {
50             a[i]++;//改变另一条路径
51         }
52     }
53     printf("\n解得个数为%d",num);
54     return 0;
55 }

本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!

本文由 @小标 发布于职坐标。未经许可,禁止转载。
喜欢 | 1 不喜欢 | 0
看完这篇文章有何感觉?已经有1人表态,100%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:z_zhizuobiao
小职老师的微信号:z_zhizuobiao

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    

©2015 www.zhizuobiao.com All Rights Reserved

208小时内训课程