算法实验报告一---分治法实验(共7页)

1、精选优质文档-倾情为你奉上算法实验报告一 分治法实验一、实验目的及要求利用分治方法设计大整数乘法的递归算法，掌握分治法的基本思想和算法设计的基本步骤。要求：设计十进制的大整数乘法，必须利用分治的思想编写算法，利用c语言（或者c+语言）实现算法，给出程序的正确运行结果。（必须完成）设计二进制的大整数乘法，要求利用分治的思想编写递归算法，并可以实现多位数的乘法（利用数组实现），给出程序的正确运行结果。（任选）二、算法描述1、输入两个相同位数的大整数u，v输出uv的值判断大整数的位数i；w=u/10(i/2);y=v/10(i/2);x=u-w*10(i/2);z= v-y*10(i/2);然后将w

2、,x,y,z代入公式求得最后结果uv=wy10i+(w+x)(y+z)-wy-xz)10(i/2)+xz三、调试过程及运行结果在实验中我遇到的问题：原来以为这两个大整数的位数不同，结果题目要求是相同位数的大整数在写10的多少次方时，写的是10(i/2),10(i)，结果不对，我就将它改成了for循环语句四、实验总结在本次实验中，我知道了分治算法，以及分治算法的基本思想。我还掌握了编写大整数乘法的算法与步骤，以及如何修改在编写程序时遇到的问题。五、附录（源程序代码清单）1、#include<iostream.h>int weishu(int x)int i;while(x!=0)x=

3、x/10;i+;return i;void main()int u,v;cout<<"输入两个位数相同的大整数:"<<endl;cin>>u;cin>>v;int i,j,m,n;int p,x,y,z,w;int a=1;int b=1;i=weishu(u);for(int k=1;k<=i;k+)a=a*10;for(int q=1;q<=i/2;q+)b=b*10;w=u/b;y=v/b;x=u-w*b;z=v-y*b;p=w*y*a+(w+x)*(y+z)-w*y-x*z)*b+x*z;cout<&

4、lt;u<<"*"<<v<<"="<<p;教师评语： 成绩：优 良 中 及格 不及格算法实验报告二 动态规划法实验一、实验目的及要求利用动态规划方法设计背包问题算法，掌握动态规划法的基本思想和算法设计的基本步骤。要求：设计0/1背包问题的动态规划算法，要求输出背包内物品的最大价值以及选入背包的物品种类。利用c语言（c+语言）实现算法，给出程序的正确运行结果。二、算法描述输入：各物品的体积、价值，背包容量输出：放入背包的物品的体积，放入物品的最大价值for i<-0 to nVi,0<-0 end

5、 for for j<-0 to C Vj,0<-0 end for for i<-1 to n for j<-1 to C VI,j<-Vi-1,j if(si<=j and Vi-1,j-si+vi)>Vi,j ) Vi,j<-Vi-1,j-si+vi itemj=i end for end for for i<-C downto 1 (i=i-itemi的体积) printf(sitemi) end for return Vn,C三、调试过程及运行结果在定义数组时数组的大小不能是变量，也不能定义一个变量从键盘输入一个常数，再用这个变量

6、定义数组，只能直接用常量定义数组或者用宏定义的量来定义数组。在进行多个for循环时，不管他们之间有没有关系，循环中定义的变量不能一样。在定义数组V时，数组大小必须是n+1、C+1。四、实验总结在进行本次实验时，我知道了背包程序的算法以及它的基本的意思，算法想要做什么。我还掌握了一些在学C+时没有注意到的一些小问题。如在定义数组时数组的大小不能是变量，也不能定义一个变量从键盘输入一个常数，再用这个变量定义数组，只能直接用常量定义数组或者用宏定义的量来定义数组。在进行多个for循环时，不管他们之间有没有关系，循环中定义的变量不能一样。在定义数组V时，数组大小必须是n+1、C+1。五、附录（源程序代

7、码清单）#include<iostream.h>#define n 10#define C 12void main()int sn,vn;int Vn+1C+1;int itemC;cout<<"物品的体积:"<<endl;for(int f=0;f<n;f+)cin>>sf;cout<<"物品的价值:"<<endl;for(int h=0;h<n;h+)cin>>vh;for(int k=0;k<=n;k+)Vk0=0;for(int m=0;m<

8、;=C;m+)V0m=0;for(int i=1;i<=n;i+)for(int j=1;j<=C;j+)Vij=Vi-1j;if(si<=j && Vi-1j-si+vi>Vij)Vij=Vi-1j-si+vi;itemj=i;cout<<"放入背包的物品的体积:"<<endl;for(int p=C;p>=1;p=p-sitemp)cout<<sitemp;cout<<endl;cout<<"背包的最大价值:"cout<<VnC<

9、;<endl;教师评语： 成绩：优 良 中 及格 不及格算法实验报告三 贪心法实验一、实验目的及要求利用贪心方法设计分数背包问题算法，掌握贪心法的基本思想和算法设计的基本步骤。要求：设计分数背包问题的贪心算法，要求输出背包内物品的最大价值以及选入背包的物品种类。利用c语言（c+语言）实现算法，给出程序的正确运行结果。二、算法描述输入：物品的个数、重量、价值，背包容量输出：背包的最大价值用物品的价值除以重量将物品的价值与重量的比进行排序将比值最大的物品放入背包中三、调试过程及运行结果在进行排序的时候总会出现错误，所以我就直接应用了直接调用程序中自带的排序算法。四、实验总结 在进行本次实验时

10、，我掌握了算法的基本应用，我还掌握了一些在学C+时没有注意到的一些小问题。我还充分了解了普通的背包程序与分数背包程序的异同点。五、附录（源程序代码清单）#include<iostream>#include<algorithm>using namespace std;struct good/表示物品的结构体 double p;/价值 double w;/重量 double r;/价值与重量的比a100;bool bigger(good a,good b) return a.r>b.r;void main()double s,value,m;int i,n;print

11、f("输入物品个数:");scanf("%d",&n);/物品个数for (i=0;i<n;i+)printf("输入物品的重量和价值:"); scanf("%lf%lf",&ai.w,&ai.p); ai.r=ai.p/ai.w;sort(a,a+n,bigger);/调用sort排序函数，你大概不介意吧，按照价值与重量比排序贪心printf("输入背包容量:");scanf("%lf",&m);/读入包的容量ms=0;/包内现存货品的重量valu