算法大作业.doc-资料库

weixin_44036164-10860117-4744302543016750662.doc.pdf-第1页.png

第1页 / 共25页

weixin_44036164-10860117-4744302543016750662.doc.pdf-第2页.png

第2页 / 共25页

weixin_44036164-10860117-4744302543016750662.doc.pdf-第3页.png

第3页 / 共25页

weixin_44036164-10860117-4744302543016750662.doc.pdf-第4页.png

第4页 / 共25页

weixin_44036164-10860117-4744302543016750662.doc.pdf-第5页.png

第5页 / 共25页

weixin_44036164-10860117-4744302543016750662.doc.pdf-第6页.png

第6页 / 共25页

weixin_44036164-10860117-4744302543016750662.doc.pdf-第7页.png

第7页 / 共25页

weixin_44036164-10860117-4744302543016750662.doc.pdf-第8页.png

第8页 / 共25页

《算法设计与分析》课程大作业姓学专院名：号：业： 16 计科（软件）本 1 班系：信息工程学院授课老师：袁张露完成时间： 2018 年 10 月 19 日

安徽新华学院 16 级算法设计与分析大作业目录 1 问题描述..................................................................................................1 1.1 0/1 背包问题.....................................................................................................1 1.2 八皇后问题......................................................................................................1 1.3 假币问题..........................................................................................................1 1.4 兔子产仔问题..................................................................................................2 2 问题分析..................................................................................................3 2.1 0/1 背包问题.....................................................................................................3 2.2 八皇后问题......................................................................................................3 2.3 假币问题..........................................................................................................4 2.4 兔子产仔问题..................................................................................................4 3 问题解决..................................................................................................5 3.1 0/1 背包问题..................................................................................................5 3.2 八皇后问题......................................................................................................6 3.3 假币问题..........................................................................................................7 3.4 兔子产仔问题..................................................................................................9 4 实验结果与总结................................................................................... 10 4.1 运行结果........................................................................................................10 4.1.1 0/1 背包问题........................................................................................................10 4.1.2 八皇后问题...........................................................................................................10 4.1.3 假币问题............................................................................................................... 11 4.1.4 兔子产仔问题.......................................................................................................12 4.2 总结................................................................................................................12 5 附录及源程序....................................................................................... 13 5.1 0/1 背包问题...................................................................................................13 5.2 八皇后问题....................................................................................................15

安徽新华学院 16 级算法设计与分析大作业 5.3 假币问题........................................................................................................18 5.4 兔子产仔问题................................................................................................20

安徽新华学院 16 级算法设计与分析大作业 1 问题描述 1.1 0/1 背包问题给定 n 种物品和一个背包。物品 i（1≤i≤n）的重量是 wi,其价值为 vi，背包的容量为 C。问应该如何选择装入背包的物品，使得装入背包的物品的总价值为最大？在选择物品的时候，对每种物品只有两种选择：装入背包或不装入背包。不能将物品 i 装入多次，也不能只装入物品的一部分。 1.2 八皇后问题八皇后问题是数学家高斯于 1850 年提出的，这是一个典型的回溯算法问题。八皇后问题的大意如下：国际象棋的棋盘有 8 行 8 列共 64 个单元格，在棋盘上摆放 8 个皇后，使其不能互相攻击，也就是说任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到 n 皇后问题，即在 n×n 的棋盘上摆放 n 个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。 1.3 假币问题在 n 枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。但是，从外观和做工上无法分辨哪枚是真币哪枚是假币，只知道假币的重量要比真币稍轻。所以，我们可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些。假币问题就是要求我们设计一个高效的算法来检测出这枚假币。 1

安徽新华学院 16 级算法设计与分析大作业 1.4 兔子产仔问题兔子产仔是一个非常古老而经典的问题，其与数论有关。兔子产仔问题最早记载与 13 世纪意大利数学家斐波那契的《算盘书》，其大意如下：如果一对两个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子出生两个月后才可以生小兔子。也就是说，1 月份出生，3 月份才可以产仔。那么假定一年内没有发生兔子死亡事件，那么 1 年后共有多少对兔子呢？ 2

安徽新华学院 16 级算法设计与分析大作业 2 问题分析 2.1 0/1 背包问题令 V(i,j)表示在前 i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) jwi (1) 式表明：如果第 i 个物品的重量大于背包的容量，则装人前 i 个物品得到的最大价值和装入前 i-1 个物品得到的最大价是相同的，即物品 i 不能装入背包；第(2) 个式子表明:如果第 i 个物品的重量小于背包的容量，则会有一下两种情况： (a)如果把第 i 个物品装入背包，则背包物品的价值等于第 i-1 个物品装入容量位 j-wi 的背包中的价值加上第 i 个物品的价值 vi； (b)如果第 i 个物品没有装入背包，则背包中物品价值就等于把前 i-1 个物品装入容量为 j 的背包中所取得的价值。显然，取二者中价值最大的作为把前 i 个物品装入容量为 j 的背包中的最优解。 2.2 八皇后问题显然，棋盘的每一行可以并且必须摆放一个皇后，所以，n 皇后的可能解用一个 n 元向量（x1,x2,…xn）表示，即第 i 个皇后摆放在第 i 行第 x1 列的位置（1 ≤i≤n 且 1≤x1≤n）。由于八皇后不能位于同一列，所以，n 皇后问题的解向量必须满足约束条件 x1≠xj。可以将 n 皇后问题的 n×n 棋盘看成是矩阵，设皇后 i 和皇后 j 的摆放位置分别是（i,xi）和（j,xj）,则在棋盘上斜率为-1 的同一条斜线上，满足条件 i-xi=j-xj，在棋盘上斜率为 1 的同一条斜线上，满足条件 i+xi=j+xj，综合上述两种情况，n 皇后问题的解必须满足约束条件：|i-j|≠|xi-xj|。 3

安徽新华学院 16 级算法设计与分析大作业 2.3 假币问题首先我们来分析一下寻找假币问题。其实寻找假币并不难，一种最基本的方法便是一分为二，也就是把 n 枚硬币分成两组，每组有 n/2 枚硬币，如果 n 为奇数，就留下一枚硬币，然后把两组硬币分别放在天平的两端。如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理。在假币问题中，尽管我们把硬币分成了两组，但每次用天平比较后，只需解决一个规模减半的问题，所以，它属于一个减治算法。该算法在最坏情况下满足如下递推式： T(n) { T(n)   0 T(n/2) 1  当  当 1时时 1时  应用扩展递归技术求解这个递推式，得到 )(T = On ( log2n ) 。 2.4 兔子产仔问题先来分析一下兔子产仔问题。下面逐月分析每月的兔子对数。第一个月：1 对兔子；第二个月：1 对兔子；第三个月：2 对兔子；第四个月：3 对兔子；第五个月：5 对兔子； ...... 可以看出，从第 3 个月开始，每个月的兔子总数等于前两个月兔子数的总数。这其实就是著名的斐波那契数列。 4

安徽新华学院 16 级算法设计与分析大作业 3 问题解决 3.1 0/1 背包问题设 n 个物品的重量存储在数组 w[n]中，价值存储在数组 v[n]中，背包容量为 C，数组 V[n+1][C+1]存放迭代结果，其中 V[i][j]表示前 i 个物品装入容量为 j 的背包中获得的最大值，数组 x[n]存储装入背包的物品，利用动态规划法求解 0/1 背包问题。主函数部分代码如图 3.1：图 3.1 0/1 背包主函数主要算法代码如图 3.2： 5

资料库

算法大作业.doc

相关推荐

课程资源

热门标签

最新资料