资源描述：
《算法分析实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、算法设计与分析第三次实验报告学院:专业:学号:姓名:目录实验一（找零）21•实验内容、目的22.实验原理、算法思路22.程序源代码23.实验分析及结论3实验二（背包）51•实验内容、目的52.实验原理、算法思路53.程序源代码54.实验分析及结论7实验一（最小生成树）81•实验内容、目的82.实验原理、算法思路83.程序源代码84.实验分析及结论11实验一（单源最短路径）121•实验内容、目的132.实验原理、算法思路163.程序源代码164.实验分析及结论16实验一1•实验内容、目的：内容：找零。在货币兑付问题中，如果出纳员手中的10
2、元、5元、1元、5角、2角、1角各10张，他必须付给客户57元8角。为使付出的货币张数最少,他该按什么方式兑付才能使得付出的钱最快的满足要求，冃付出的货币张数最少？目的：了解熟悉贪心算法。2.实验原理、算法思路:〃输入需要找零的钱数〃输入找零货币的面值〃输入各种货币的数量intchange(floatn){〃n为需要找零数inttM=10*n;inti=0,j=0;if(n>57.8
3、
4、n<=0)return-1;for(i=0;i<9;i++)k[i]=O;for(i=0;i<9;i++){而值最大的货币最多几张；面值减小；}retu
5、rnj;}3•程序源代码：#inelude#includeusingnamespacestd;intM[9]={1000,500,200,100,50,10,5,2,1};intk[9];intchange(floatn){〃n为需要找零数inttM=10*n;inti=0,j=0;for(i=0;i<9;i++)k[i]二0;for(i=0;i<9;i++){k[i]=tM/M[i];j+=M[i];}returnj;}voidmain(){floatn;inti,j；cout«H请输入你要找零多
6、少钱：”；cin〉>n;j=change(n);cout«H一共找你n«j«H张钱n«endl;for(i=0;i<6;i++){if(k[i]==0)continue;cout«k[i]«"张元的"«endl;}for(i=6;i<9;i++){if(k[i]==O)continue;cout«k[i]«H张”角的H«endl;}}4.实验分析及结论：a.理论分析及比较：时间复杂度:0(n)ob.实验环境：处理器:Intel(R)Core(TM)i5-4200MCPU@2.50GHz2.49GHz系统内存：3.89G操作系统：Micr
7、osoftWindows10家庭中文版软件：MicrosoftVisualStudioc・实验对比算法及数据一一运行吋间图：(单位：毫秒)实验二1•实验内容、目的：内容：背包问题。已知有n种物品和一个可容纳c重量的背包，每种物品i的重量为wi。假定物品i的一部分放入背包会得到vixi的效益。其中OWxiWl,vi>0・采用怎样的装包方法才会使装入背包物品的总效益最大呢？日的：了解熟悉贪心算法。2•实验原理、算法思路：输入：背包的容量C,物品重量W[n],物品价值V[n]输出：数组X[n]改变数组W和V的排列顺序，使其按单位重量价值V[i
8、]/W[i]降序排列；将数组X[n]初始化为0；i=0；循环直到(W[i]>C)将第i个物品放入背包：x[i]二1;C=c-W[i];i++；X[i]=C/W[i]o3•程序源代码：#includeusingnamespacestd;struct_Object//物品结构体{intValue;//物品价值intWeight;//物品重量intAveValue;//物品单位价值floatNum;//物品可以放入的数量}；voidknaspsack(intn,floatM,_Objectobject[]){〃n为物品个数
9、，M为背包容量inti;floatC=M;for(i=0;i;i++){object[i].Num=0;//初始化放入背包的物品为0if(object[i].Weight>C)break;//当物品重量大于背包容量时else//小于时{object[i].Num=l;//物品i放入一件C-=object[i].Weight;//背包容量减小}}if(i<=n)//当不能放入整个物品时，选取物品一部分放入object[i].Num=C/object[i].Weight;for(i=0;i;i++){if(object[i].Num>0)c
10、out«"重量为:"«object[i].Weight«"价值为:"«object[i].Value«"的物品放入,,«object[i].Num«H4"«endl;}}voidSortObject(_Ob
