实验五(回溯算法).doc

华东师范大学计算机科学技术系学生上机实践报告华东师范大学计算机科学技术系上机实践报告课程名称： 算法设计与分析年级：05上机实践成绩：指导教师： 柳银萍姓名：张翡翡上机实践名称：回溯算法学号：10052130119上机实践日期：2007-5-15上机实践编号：NO.5组号：上机实践时间：10:00-11:30一、目的知道了解回溯算法的实质及在生活中的应用，用于求解潜在的大量解，但是有限个数的解衣镜检查过的问题，掌握回溯递归。二、内容与设计思想1. 设计一个回溯算法来生成数字1，2. . . . .n(n 10)的所有排列。要求：输入：输入一个正整数n(0nn then for i1 to n printf”ai” else for it to n pat atai aip all(t+1) pat atai aip return(0)2. 有一个箱子容量为V（正整数，0V20000），同时有n个物品（0n30），每个物品有一个体积（正整数）。要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。(此题建议不要用回溯算法，建议用其他方法)要求：输入：输入有多组测试数据，第一行一个正整数V,表示箱子的容量。第二行一个数据n表示物品个数。第三行有n个数据，描述每个物品的体积。输出：每个输出占一行，输出箱子最后剩下的最小体积。2.1其思路是： 1) 定义相关变量及赋初值；2) 编写递归函数backtrack(int t)，判断t和物品个数N大小，如果tN，则执行循环，循环只有两次，i等于0或者1，分别表示物品不装入箱子和装入箱子；3) 如果已有总数加上刚加入的物品重量小于箱子总重量，总数变为加上刚加入的物品重量；判断箱子还剩容量与剩下的物品中最小重量的大小，如果小于则剩余容量为箱子目前剩余容量，调用函数backtrack(t+1)；4) 如果已有总数加上刚加入的物品重量刚好等于箱子总重量，则箱子还剩容量为0，打断；5) 如果已有总数加上刚加入的物品重量大于箱子总重量，则打断，总数减去刚加入的物品重量；2.2具体算法是： while(scanf(%d%d,&V,&N)!=EOF) minV for j0 to N do wj输入 backtrack( int t) if tN then for i0 to 1 do if total+wt*iV then total+=wt*i min=V-totalV then break total-=wt*i return(0)3素数环问题一个由自然数 1.n (n 20)素数环就是如下图所示，环上任意两个节点上数值之和为素数。1/ 4 2 /3要求：输入：输入只有一个数n，表示你需要建立一个1.n的素数环。输出：按照字典序输出每一种情况。我们约定顺时针为正向，且第一个元素必须是1。3.1其思路是：3.2具体算法是：三、使用环境 Microsoft visual C+ 6.0四、调试过程1. 第一个程序函数调用不对，刚开始基本程序是正确的，但是就是在主函数中调用函数all(int t)时没有传入具体的参数t的值导致运行结果只有123；2. 第二个程序第一次递归调用错误，逻辑出现点问题，箱子还剩余容量没有考虑清楚导致问题不能解决，最后一个if语句处当箱子现有重量加上欲装入物品重量超过箱子总容量时没有减去此时的物品重量导致错误；五、总结1. 对递归函数的定义还没完全清楚，虽然能看懂递归函数但是让自己编写的话还是有一定难度，除非有人提点，因此与别人交流相当重要；2. 递归调用的时候主函数中调用递归函数时应接收进一个刚开始的数，但是我没搞清楚不完全清次参数的含义，通过编写回溯懂了很多；六、附录1. 数字排列问题的程序： （此处放程序）运行结果：2. 箱子剩余容积问题的程序：（此处放程序）#includeint V,N; int min;int total;int w40;void backtrack (int t) if(tN) for (int i=0;i=1;i+) if (total+wt*iV) total+=wt*i; min=V-totalV)break; total-=wt*i; int main() int j; while(scanf(%d%d,&V,&N)!=EOF) min=V; for(j=0;jN;j+) scanf(%d,&wj);