回溯算法-n后问题和符号三角形java算法源程序

《回溯算法-n后问题和符号三角形java算法源程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告10课程数据结构与算法实验名称回溯法第页班级11计本学号105032011130姓名风律澈实验日期：2013年5月6日报告退发(订正、重做)一、实验目的掌握回溯法的原理和应用。二、实验环境1、微型计算机一台2、WINDOWS操作系统，JavaSDK，Eclipse开发环境三、实验内容必做题：1、编写程序，实现符号三角形问题算法。2、编写程序，实现n后问题算法。四、实验步骤和结果(附上代码和程序运行结果截图)1.符号三角形importjava.util.Scanner;publicclassTriangles{/***@paramargs*/staticintn,/

2、/第一行符号总数half,//一半符号数量count;//当前+号个数staticintp[][];//符号三角数组staticlongsum;//已找到的符号三角数量publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubScannerin=newScanner(System.in);intnn=in.nextInt();longresult=compute(nn);System.out.println(result);}privatestaticlongcompute(intnn){//TODO

3、Auto-generatedmethodstub//类变量初始化n=nn;count=0;sum=0;half=n*(n+1)/2;if(half%2==1)return0;//防止不合法输入half=half/2;p=newint[n+1][n+1];for(inti=0;i<=n;i++)for(intj=0;j<=n;j++)p[i][j]=0;//开始算法backtrack(1);//返回结果returnsum;}privatestaticvoidbacktrack(intt){//TODOAuto-generatedmethodstubif((count>hal

4、f)

5、

6、(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(inti=0;i<2;i++){p[1][t]=i;count+=i;for(intj=2;j<=t;j++){//至上而下构造符号数组p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}backtrack(t+1);//对t以后的每一个执行上述操作//操作执行完成后恢复工作；for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}}1.N后问题impo

7、rtjava.util.Scanner;publicclassnqueen{/***@paramargs*/staticintn;//皇后个数staticintx[];//当前解，表示x[i]表示第i行皇后位置staticlongsum;//当前已找到的可行方案数publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubScannerin=newScanner(System.in);intnn=in.nextInt();longresult=nQueen(nn);System.out.println(

8、result);}privatestaticlongnQueen(intnn){//TODOAuto-generatedmethodstub//初始化n=nn;sum=0;x=newint[n+1];//尝试第一行的所有位置for(inti=0;i<=n;i++)x[i]=0;backtrack(1);returnsum;}privatestaticvoidbacktrack(intt){//TODOAuto-generatedmethodstubif(t>n)sum++;elsefor(inti=1;i<=n;i++){//从第一行开始往下放置，放置陈功继续x[t]=i

9、;if(place(t))backtrack(t+1);}}privatestaticbooleanplace(intt){//TODOAuto-generatedmethodstubfor(intj=1;j

10、

11、(x[j]==x[t]))//检验放置陈功与否，对角线和同行的都要去掉returnfalse;returntrue;}}五、实验总结(本次实验完成的情况，心得体会)