算法分析实验报告.doc

该【算法分析实验报告 】是由【世界末末日】上传分享，文档一共【28】页，该文档可以免费在线阅读，需要了解更多关于【算法分析实验报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法分析实验报告算法设计与分析第三次实验报告学院:专业:学号:姓名:目录实验一(找零)..............................................................................................................................、目的...........................................................................................................................、算法思路...............................................................................................................................................................................................................................................................................................................................................................................3实验二(背包)..............................................................................................................................、目的...........................................................................................................................、算法思路...............................................................................................................................................................................................................................................................................................................................................................................7实验一(最小生成树)...................................................................................................................、目的...........................................................................................................................、算法思路.............................................................................................................................................................................................................................................................................................................................................................................11实验一(单源最短路径).............................................................................................................、目的.........................................................................................................................、算法思路.........................................................................................................................................................................................................................................................................................................................................................................、目的:内容:找零。在货币兑付问题中,如果出纳员手中的10元、5元、1元、5角、2角、1角各10张,他必须付给客户57元8角。为使付出的货币张数最少,他该按什么方式兑付才能使得付出的钱最快的满足要求,且付出的货币张数最少,目的:了解熟悉贪心算法。、算法思路://输入需要找零的钱数//输入找零货币的面值//输入各种货币的数量intchange(floatn){//n为需要找零数inttM=10*n;inti=0,j=0;if(n>||n<=0)return-1;for(i=0;i<9;i++)k[i]=0;for(i=0;i<9;i++){面值最大的货币最多几张;面值减小;}returnj;}:#include<>#include<iostream>usingnamespacestd;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;2for(i=0;i<9;i++){k[i]=tM/M[i];tM=tM-k[i]*M[i];j+=M[i];}returnj;}voidmain(){floatn;inti,j;cout<<"请输入你要找零多少钱:";cin>>n;j=change(n);cout<<"一共找你"<<j<<"张钱"<<endl;for(i=0;i<6;i++){if(k[i]==0)continue;cout<<k[i]<<"张"<<M[i]/10<<"元的"<<endl;}for(i=6;i<9;i++){if(k[i]==0)continue;cout<<k[i]<<"张"<<M[i]<<"角的"<<endl;}}::时间复杂度:O(n)。:处理器:Intel(R)Core(TM)i5-******@::MicrosoftWindows10家庭中文版软件:——运行时间图:(单位:毫秒3)、目的:内容:背包问题。已知有n种物品和一个可容纳c重量的背包,每种物品i的重量为wi。假定物品i的一部分放入背包会得到vixi的效益。其中0?xi?1,vi>,目的:了解熟悉贪心算法。、算法思路:输入:背包的容量C,物品重量W[n],物品价值V[n]输出:数组X[n]改变数组W和V的排列顺序,使其按单位重量价值V[i]/W[i]降序排列;将数组X[n]初始化为0;i=0;循环直到(W[i]>C)将第i个物品放入背包:X[i]=1;C=C-W[i];i++;X[i]=C/W[i]。:#include<iostream>usingnamespacestd;struct_Object//物品结构体{intValue;//物品价值intWeight;//物品重量intAveValue;//物品单位价值floatNum;//物品可以放入的数量};voidknaspsack(intn,floatM,_Objectobject[]){//n为物品个数,M为背包容量inti;floatC=M;for(i=0;i<n;i++){object[i].Num=0;//初始化放入背包的物品为0if(object[i].Weight>C)break;//当物品重量大于背包容量时5else//小于时{object[i].Num=1;//物品i放入一件C-=object[i].Weight;//背包容量减小}