实验五(回溯算法)

《实验五(回溯算法)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华东师范大学计算机科学技术系学生上机实践报告华东师范大学计算机科学技术系上机实践报告课程名称：算法设计与分析年级：05上机实践成绩：指导教师：柳银萍姓名：张翡翡上机实践名称：回溯算法学号：10052130119上机实践日期：2007-5-15上机实践编号：NO.5组号：上机实践时间：10:00-11:30一、目的知道了解回溯算法的实质及在生活中的应用，用于求解潜在的大量解，但是有限个数的解衣镜检查过的问题，掌握回溯递归。二、内容与设计思想1.设计一个回溯算法来生成数字1，2.....n(n<10)的所有排列。要求：输入：输入一个正

2、整数n(0nthenforiß1tonprintf”a[i]”

3、第7页共7页华东师范大学计算机科学技术系学生上机实践报告elseforißttonpßa[t]a[t]ßa[i]a[i]ßpall(t+1)pßa[t]a[t]ßa[i]a[i]ßpreturn(0)2.有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0

4、描述每个物品的体积。输出：每个输出占一行，输出箱子最后剩下的最小体积。2.1其思路是：1)定义相关变量及赋初值；2)编写递归函数backtrack(intt)，判断t和物品个数N大小，如果t

5、子还剩容量为0，打断；5)如果已有总数加上刚加入的物品重量大于箱子总重量，则打断，总数减去刚加入的物品重量；第7页共7页华东师范大学计算机科学技术系学生上机实践报告2.2具体算法是：while(scanf("%d%d",&V,&N)!=EOF)minßVforjß0toNdow[j]ß输入backtrack(intt)ift

6、t]*i==Vthenminß0breakelseiftotal+w[t]*i>Vthenbreaktotal-=w[t]*ireturn(0)3．素数环问题一个由自然数1..n(n<20)素数环就是如下图所示，环上任意两个节点上数值之和为素数。1/42/3要求：第7页共7页华东师范大学计算机科学技术系学生上机实践报告输入：输入只有一个数n，表示你需要建立一个1..n的素数环。输出：按照字典序输出每一种情况。我们约定顺时针为正向，且第一个元素必须是1。3.1其思路是：3.2具体算法是：三、使用环境Microsoftvisual

7、C++6.0四、调试过程1.第一个程序函数调用不对，刚开始基本程序是正确的，但是就是在主函数中调用函数all(intt)时没有传入具体的参数t的值导致运行结果只有123；2.第二个程序第一次递归调用错误，逻辑出现点问题，箱子还剩余容量没有考虑清楚导致问题不能解决，最后一个if语句处当箱子现有重量加上欲装入物品重量超过箱子总容量时没有减去此时的物品重量导致错误；五、总结1.对递归函数的定义还没完全清楚，虽然能看懂递归函数但是让自己编写的话还是有一定难度，除非有人提点，因此与别人交流相当重要；2.递归调用的时候主函数中调用递归函数时应

8、接收进一个刚开始的数，但是我没搞清楚不完全清次参数的含义，通过编写回溯懂了很多；六、附录1.数字排列问题的程序：（此处放程序）第7页共7页华东师范大学计算机科学技术系学生上机实践报告运行结果：2.箱子剩余容积问题的程序：（此处放程序）#includ