回溯法 经典题目 八皇后 桥本分数

《回溯法 经典题目 八皇后 桥本分数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、回溯法经典题目八皇后问题的求解推广N皇后的求解#include//使用库函数printf、scanf#include//使用绝对值函数absconstintN=100;//假定最多求100皇后问题intx[N]={-1};//由于数组下标从0开始，将数组x[N]初始化为-1voidQueue(intn);//函数声明intPlace(intk);//函数声明intcount=0;//空行，以下是主函数intmain(){intn;cout<<"请输入皇后的个数:";//输出提示信息cin>>n;//输入皇后的个数Queue(n);//函数调用

2、，求解n皇后问题return0;//将0返回操作系统，表明程序正常结束}//空行，以下是其他函数定义voidQueue(intn)//函数定义，求解n皇后问题{intk=0;//num存储解的个数while(k>=0)//摆放皇后k，注意0≤k＜n{x[k]++;//在下一列摆放皇后kwhile(x[k]

3、t;//只求出一个解即可}elseif(x[k]

4、

5、abs(i-k)==abs(x[i]-x[k]))//违反约束条件return1;//冲突，返回1return0;//不冲突，

6、返回0}桥本分数回溯法解题/*将1-9九个数不重复地赋给不同的9个元素，实现形如a/bc+d/ef=f/hi的形式：例：1/26+5/78=4/391/32+5/96=7/84（注意：1/26+5/78=4/39和5/78+1/26=4/39只能算一种解）求满足条件的解共有多少个？*/#include"stdio.h"#include#includeusingnamespacestd;intmain(){clock_tnTimeStart;//计时开始clock_tnTimeStop;//计时结束nTimeStart=clock();//inti

7、,k,g,s;intm1,m2,m3,a[10];a[1]=1;i=1;g=1;s=0;while(1){g=1;for(k=i-1;k>0;k--)//注意此处很容易由于习惯错写成for(k=i-1;i>0;i--)if(a[k]==a[i]){g=0;break;}//两数相同，标记g=0if(i==9&&g==1&&a[1]

8、/%d+%d/%d=%d/%dt",a[1],m1,a[4],m2,a[7],m3);if(s%2==0)printf("");}}if(i<9&&g==1){i++;a[i]=1;continue;}//向前继续走,执行continue语句直接跳到while语句，则不在执行下面的语句while(a[i]==9&&i>1)i--;//向上一步回溯if(a[1]==9)break;//if(a[i]==9&&i==1)break;//注意此处不能简写成if(a[1]==9)elsea[i]++;}printf("共有%d个解！",s);cout<

9、clock();//cout<<"9的9次方次空循环耗时："<<(double)(nTimeStop-nTimeStart)/CLOCKS_PER_SEC<<"秒"<