实验项目三：搜索算法.doc

《实验项目三：搜索算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》实验报告实验项目（三）搜索算法专业、班级学　　号姓　　名实验时间实验地点指导教师教学目标使学生掌握“算法设计与分析”中的基本原理、基本技术和方法，提升计算机问题求解的水平。熟练掌握编程中常见问题的求解策略，培养学生对算法复杂性进行正确分析的能力。（1）掌握编程求解问题的常用算法策略。（2）熟练强化深入计算机求解问题的过程。（3）增强理论结合实际能力，增强获得理论联系实际问题的能力。（4）培养系统分析能力和团队协作能力。一、实验目的及要求（1）练习搜索算法和分支限界算法中剪枝的使用；（2）初步掌握回溯法和分支限界的编码。二、实验设备（环境）及要求使用C/C

2、++语言，VisualStudio201X开发环境，Windows系列操作系统环境三、成绩评定题号题型能力分值成绩备注①设计分析题设计分析20②设计分析题设计分析30③设计分析题设计分析40④报告格式10总成绩一、实验内容与步骤1、容器里有10升油，现在只有两个分别能装3升和7升油的瓶子，需要将10升油等分成2个5升油。程序输出分油次数最少的详细操作过程。源程序：#includeusingnamespacestd;intpull(intm,intn){intn10=10,a=0,b=0,total=1;while(n10!=5){if(a==0){n1

3、0-=m;a+=m;//向3/7L杯子倒入cout<0&&b

4、total++<<":"<=n){if(a==5)break;}else{if(b==5)break;}}cout<<"10L容器中有"<pull(7,3))cout<<"第2种方案步

5、骤最少。";elsecout<<"第1种方案步骤最少。";return0;}运行结果：1、用非递归回溯算法完成数独求解。“数独”是一种智力游戏，一般认为起源于“正交拉丁方”，经日本人推广后风靡全球。下图是一个数独的示例，需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并且满足同一行、同一列、每一个同色九宫内的数字均含1~9不重复：数独的答案一般都是唯一的，如果有多个可行解也称为无解。实验要求：1)输入数据共9行，每行9个连续的数字，0代表未知，其它数字为已知。2)输出数据共9行，每行9个连续的数字表示该数独的解。源程序：#includeinta

6、[9][9];intjudge(intx,inty){intup,left;inti,j;up=x/3*3;left=y/3*3;for(i=0;i<9;i++){if(a[x][y]==a[i][y]&&i!=x&&a[i][y]!=0)return0;}for(i=0;i<9;i++){if(a[x][y]==a[x][i]&&i!=y&&a[x][i]!=0)return0;}for(i=up;i

7、

8、j!=y){if(a[i][j]==a[x][y]&&a[i][j]!=0)ret

9、urn0;}}}}voidbacktrack(intt){inti,j,x,y;if(t==81){printf("==============================");for(i=0;i<9;i++){for(j=0;j<9;j++){printf("%2d",a[i][j]);}printf("");}}else{x=t/9;y=t%9;if(a[x][y]!=0){backtrack(t+1);}else{for(i=1;i<=9;i++){a[x][y]=i;if(judge(x,y)){bac