算法设计与分析课程设计6页

1、算法设计与分析课程设计一、 课程题目零钱问题贪心算法实现二、课程摘要1）题目描述使用贪心算法设计思想设计算法实现找零钱问题。例题13-4 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。1）在给定钱币面值的前提下，实现找回尽量少硬币的输出方案2）分析算法性能2）贪心算法

2、简述在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特

3、点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。三、课程引言首先，证明找零钱问题的贪婪算法总能产生具有最少硬币数的零钱。证明：（1）找零钱问题的最优解必以一个贪心选择开始，当总金额为N,硬币面值为25，10，5，1时。 设最大容许的硬币面值为m,最优解必包含一个面值为m的硬币: 设A是一个最优解，且A中的第i个硬币面值为f(i)。 当f(1)=m（此处为25）,得证； 若f(1)1)之和1时，若jTn,即第n种钱币面值比所兑换零钱数小,因此有。当k为时，C(n,j)达到最小值，有P(T(k0),j)=P(T()，j

4、-T()+1若j=Tn，即用n种钱币兑换零钱，第n种钱币面值与兑换零钱数j相等，此时有C(n,j)=C(n,Tn)=1；若jTn，即第n种钱币面值比所兑换零钱数大，因此兑换零钱只需考虑前n-1种钱币即可，故有C(n,j)=C(n-1,j)，且P(T(n-1),j)=0。从以上讨论可知该问题具有重叠子问题性质。（1） 根据分析建立正确的递归关系。答： （2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。答：算法的时间复杂度主要取决于程序的两个循环，所以算法的时间复杂度为；算法执行过程中引入了一个二维数组，随着输入规模的增大，所需要的空间复杂度为：考虑例1 3 - 4的找零钱问题，假设售货

5、员只有有限的2 5美分， 1 0美分， 5美分和1美分的硬币，给出一种找零钱的贪婪算法。这种方法总能找出具有最少硬币数的零钱吗？证明结论。源代码如下：# include using namespace std;const int C=33; const int M=100; /小孩给的钱数const int twentyfnum=3; /25美分硬币const int tennum=3; /10美分硬币const int fivenum=3; /5美分硬币const int onenum=3; /1美分硬币 const int tnum=twentyfnum+tennum+fivenum+on

6、enum; /硬币的总数量int main()int atnum,i; /数组初始化,数组中的元素由大到小排列int *p=a;for(i=0;itwentyfnum;i+) *p+=25;for(i=0;itennum;i+) *p+=10;for(i=0;ifivenum;i+) *p+=5;for(i=0;ionenum;i+) *p+=1;bool btnum; q,int n,int c);if(findmoney(a,b,tnum,M-C) int c4=0; /存放应找个各面值硬币的数量 bool findmoney(int *p,bool *for(i=0;itnum;i+)i

7、f(bi=true)switch(ai)case 25: c0+;break;case 10: c1+;break;case 5: c2+;break;case 1: c3+;break; cout找钱方案:endl; cout25美分:c0枚,10美分:c1枚,5美分:c2枚,1美分:c0枚endl;else cout零钱不够;system(pause); return 0;bool findmoney(int *p,bool *q,int n,int c) for(int i=0;in;i+) if(pi=c&c!=0) qi=true; c-=pi; if(c=0) break; if(

8、c=0) return true;else return false;在此程序中，程序没有实现输入和输出的模块，但是具有了找零钱问题的贪心算法解决模块，所以需要在此程序的基础上进一步优化，改进后的代码如下：#include using namespace std; void Zl(double num) int leave=0; double a8; leave = (int)(num*10)%10; a1 = leave/5; a0 = (leave%5)/1; a7 = num/50; a6 = (int)num%50)/20; a5 = (int)num%50)%20)/10; a4 =

9、 (int)num%50)%20)%10)/5; a3 = (int)num%50)%20)%10)%5)/2; a2 = (int)num%50)%20)%10)%5)%2)/1; if(a0!=0) cout需要找的0.1元个数为：a0endl; if(a1!=0) cout需要找的0.5元个数为：a1endl; if(a2!=0) cout需要找的1元个数为：a2endl; if(a3!=0) cout需要找的2元个数为：a3endl; if(a4!=0) cout需要找的5元个数为：a4endl; if(a5!=0) cout需要找的10元个数为：a5endl; if(a6!=0) c

10、out需要找的20元个数为：a6endl; if(a7!=0) cout需要找的50元个数为：a7endl; int main() double num; cout请输入你需要找的零钱数：num; Zl(num); coutendl; return 0;2）实验结果比较上一步骤中两个源代码运行结果分别如下：第一个的运行结果第二个运行结果比较上面两个算法，第二个算法在第一个的基础上增加了输入输出功能，方便得到任意数值零钱问题的最优解。五、结论与展望（1）算法实现的复杂度在问题规模很大时可以接受吗？答：可以接受，因为贪心算法有很好的效率，所以当问题复杂度很大时，就不会对算法的运行时间有太大的影响，

11、可以控制在用户可以接受的范围内。（2）如果不用贪心算法方法还能想到其他的解决方式吗？和贪心算法相比会有更好的效率吗？答：对于找硬币问题，有时候动态规划也能解决，前面也有叙述，动态规划求解要比贪心算法求解有效率，所以采用动态规划方法也是一个很好的选择。（3）所选用的数据结构合适吗？答：采用了数组的数据结构，合适，因为该数据结构能够支持对于数组中的元素的随机访问，而且方便查询。（4）该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到的这些情况吗，测试结果如何？答：基本上覆盖了所有可能的测试结果，但不排除结果出现错误的可能。（5）通过实验对贪心算法的理解及总结*贪心算法的特点从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程，后面的每一步都是当前看