分治法实验报告.doc

分治法实验报告算法实验报告一分治法实验一、实验目的及要求利用分治方法设计大整数乘法的递归算法,掌握分治法的基本思想和算法设计的基本步骤。要求:设计十进制的大整数乘法,必须利用分治的思想编写算法,利用c语言实现算法,给出程序的正确运行结果。设计二进制的大整数乘法,要求利用分治的思想编写递归算法,并可以实现多位数的乘法,给出程序的正确运行结果。二、算法描述1、输入两个相同位数的大整数u,v}voidmain{intu,v;coutcin>>u;cin>>v;inti,j,m,n;intp,x,y,z,w;inta=1;intb=1;i=weishu;for{a=a*10;}for{b=b*10;}w=u/b;y=v/b;x=u-w*b;z=v-y*b;p=w*y*a+*-w*y-x*z)*b+x*z;cout}教师评语:成绩:√优良中及格不及格算法实验报告二动态规划法实验一、实验目的及要求利用动态规划方法设计背包问题算法,掌握动态规划法的基本思想和算法设计的基本步骤。要求:设计0/1背包问题的动态规划算法,要求输出背包内物品的最大价值以及选入背包的物品种类。利用c语言实现算法,给出程序的正确运行结果。二、算法描述输入:各物品的体积、价值,背包容量输出:放入背包的物品的体积,放入物品的最大价值foriV[i,0]endforforjV[j,0]endforforiforjV[I,j]if>V[i,j])V[i,j]item[j]=iendforendforforiprintfendforreturnV[n,C]三、调试过程及运行结果在定义数组时数组的大小不能是变量,也不能定义一个变量从键盘输入一个常数,再用这个变量定义数组,只能直接用常量定义数组或者用宏定义的量来定义数组。在进行多个for循环时,不管他们之间有没有关系,循环中定义的变量不能一样。在定义数组V[][]时,数组大小必须是n+1、C+1。四、实验总结在进行本次实验时,我知道了背包程序的算法以及它的基本的意思,算法想要做什么。我还掌握了一些在学C++时没有注意到的一些小问题。如在定义数组时数组的大小不能是变量,也不能定义一个变量从键盘输入一个常数,再用这个变量定义数组,只能直接用常量定义数组或者用宏定义的量来定义数组。在进行多个for循环时,不管他们之间有没有关系,循环中定义的变量不能一样。在定义数组V[][]时,数组大小必须是n+1、C+1。五、附录#include#definen10#defineC12voidmain{ints[n],v[n];intV[n+1][C+1];intitem[C];coutforcin>>s[f];coutforcin>>v[h];for{V[k][0]=0;}for{V[0][m]=0;}for{for{V[i][j]=V[i-1][j];if{V[i][j]=V[i-1][j-s[i]]+v[i];item[j]=i;}}}cout{coutcout}coutcout}教师评语:成绩:√优良中及格不及格本科学生综合性实验报告姓名___刘春云学号_0103918___专业__软件工程__班级_103__实验项目名称_二分搜索问题的分治算法实验指导教师及职称_____赵晓平_____开课学期2016至_2016学年_3_学期上课时间2016年2月18日学生实验报