资源描述：
《分治法实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、算法实验报告一分治法实验一、实验目的及要求利用分治方法设计大整数乘法的递归算法，掌握分治法的基本思想和算法设计的基本步骤。要求：设计十进制的大整数乘法，必须利用分治的思想编写算法，利用C语言(或者C++语言)实现算法，给出程序的正确运行结果。(必须完成)设计二进制的大整数乘法，要求利用分治的思想编写递归算法，并可以实现多位数的乘法(利用数组实现)，给出程序的正确运行结果。(任选)二、算法描述1、输入两个相同位数的大整数U,V输出UV的值判断大整数的位数i;w=u/107i/2);y=v/107i/2);x二u-w*l(T(i/2);z=V-y*l(T(i/
2、2);然后将w,x,y,z代入公式求得最后结果uv=wy10i+((w+x)(y+z)-wy-xz)10(i/2)+xz三、调试过程及运行结果在实验中我遇到的问题：原来以为这两个大整数的位数不同，结果题目要求是相同位数的大整数在写10的多少次方时，写的是10^1/2),1071),结果不对，我就将它改成了for循环语句四、实验总结在本次实验中，我知道了分治算法，以及分治算法的基本思想。我还掌握了编写大整数乘法的算法与步骤，以及如何修改在编写程序时遇到的问题。五、附录(源程序代码清单)1、#include<iostream.h>intweishu
3、(intx){inti;while(x!=0){x=x/10;i++；}returni;}voidmain(){intu,v;coutftlt;<输入两个位数相同的大整数:&11;&11;end1;cin>>u;cin>>v;inti,j,m,n;intP,x,y,z,w;inta=l;intb=l；i二weishu(u);for(intk二1二i;k++){a=a*10;)for(intq二l;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)*
4、(y+z)_w*y-x*z)*b+x*z;cout<&1t;u<<*&1t;&]t;v<<=<<p;}教师评语：成绩：丁优良中及格不及格算法实验报告二动态规划法实验一、实验目的及要求利用动态规划方法设计背包问题算法，掌握动态规划法的基本思想和算法设计的基本步骤。要求：设计0/1背包问题的动态规划算法，要求输出背包内物品的最大价值以及选入背包的物品种类。利用c语言(C++语言)实现算法，给出程序的正确运行结果。二、算法描述输入：各物品的体积、价值，背包容量输出：放入背包的物品的体积，放入物品的最大价值fori<
5、-0tonv[i,0]<-0endforforj<-0tocv[j,0]<-0endforfori<Ttonforj<~1tocv[i,j]<-v[i-l,j]if(si<=jandv[iT,j-si]+vi)>v[i,j])v[i,j]&It;-v[i-l,j-si]+viitem[j]=iendforendforfori&11;-cdownto1(i=i-item[i]的体积)printf(s[item[i]])endforreturnv[n,c]三、调试过程及运行结果在定义数组时数组的大小不能是变量，也
6、不能定义一个变量从键盘输入一个常数，再用这个变量定义数组，只能直接用常量定义数组或者用宏定义的量来定义数组。在进行多个for循环时，不管他们之间有没有关系，循环中定义的变量不能一样。在定义数组讥]□时，数组大小必须是n+1、c+k四、实验总结在进行本次实验时，我知道了背包程序的算法以及它的基本的意思，算法想要做什么。我还掌握了一些在学C++吋没有注意到的-些小问题。如在定义数组吋数组的大小不能是变量，也不能定义一个变量从键盘输入一个常数，再用这个变量定义数组，只能直接用常量定义数组或者用宏定义的量來定义数组。在进行多个for循坏时，不管他们之间有没有关系,
7、循环中定义的变量不能一样。在定义数组v[][]时，数组大小必须是n+1、c+lo五、附录(源程序代码清单)#inelude;iostream,h>#definen10^definec12voidmain(){ints[n],v[n];intv[n+l][c+1];intitem[c];cout<<物品的体积:<<endl;for(intf=0;f<n;f卄)cin>>s[f];cout<&11;物品的价值:&11;&11;endl;for(inth二O;h<n;h++)cin>>v[h
8、];for(intk二O;k<二n;k++){v[k][0]
