算法实验报告一分治法实验
一、实验目的及要求
利用分治方法设计大整数乘法的递归算法，掌握分治法的基本思想和算法设计的基本步
骤。
要求：设计十进制的大整数乘法，必须利用分治的思想编写算法，利用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,x,y,z代入公式求得最后结果
uv=wy10^i+((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=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<<u<<*<<v<<=<<p; }
教师评语：
成绩：√优良中及格不及格
算法实验报告二动态规划法实验
一、实验目的及要求
利用动态规划方法设计背包问题算法，掌握动态规划法的基本思想和算法设计的基本步
骤。
要求：设计0/1背包问题的动态规划算法，要求输出背包内物品的最大价值以及选入背
包的物品种类。利用c语言（c++语言）实现算法，给出程序的正确运行结果。
二、算法描述
输入：各物品的体积、价值，背包容量
输出：放入背包的物品的体积，放入物品的最大价值
for i<-0 to n
v[i,0]<-0
end for
for j<-0 to c
v[j,0]<-0
end for
for i<-1 to n
for j<-1 to c
v[i,j]<-v[i-1,j]
if(si<=j and v[i-1,j-si]+vi)>v[i,j] ) v[i,j]<-v[i-1,j-si]+vi
item[j]=i
end for
end for
for i<-c downto 1 (i=i-item[i]的体积) printf(s[item[i]])
end for
return v[n,c]
三、调试过程及运行结果
在定义数组时数组的大小不能是变量，也不能定义一个变量从键盘输入一个常数，再用
这个变量定义数组，只能直接用常量定义数组或者用宏定义的量来定义数组。
在进行多个for循环时，不管他们之间有没有关系，循环中定义的变量不能一样。
在定义数组v[][]时，数组大小必须是n+1、c+1。
四、实验总结
在进行本次实验时，我知道了背包程序的算法以及它的基本的意思，算法想要做什么。
我还掌握了一些在学c++时没有注意到的一些小问题。如在定义数组时数组的大小不能是变
量，也不能定义一个变量从键盘输入一个常数，再用这个变量定义数组，只能直接用常量定
义数组或者用宏定义的量来定义数组。在进行多个for循环时，不管他们之间有没有关系，
循环中定义的变量不能一样。在定义数组v[][]时，数组大小必须是n+1、c+1。
五、附录（源程序代码清单）
#include<iostream.h> #define n 10
#define c 12
void main()
{
int s[n],v[n];
int v[n+1][c+1];
int item[c];
cout<<物品的体积:<<endl; for(int f=0;f<n;f++)
cin>>s[f]; cout<<物品的价值:<<endl; for(int h=0;h<n;h++)
cin>>v[h];
for(int k=0;k<=n;k++)
{
v[k][0]=0;
}
for(int m=0;m<=c;m++)
{
v[0][m]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c;j++)
{
v[i][j]=v[i-1][j];
