分治法实验报告

算法实验报告一 分治法实验

一、实验目的及要求

利用分治方法设计大整数乘法的递归算法，掌握分治法的基本思想和算法设计的基本步骤。

要求:设计十进制的大整数乘法,必须利用分治的思想编写算法，利用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＆lt;iostream。h＆gt；

int weishu(int x）

{

int i;

while(x！=0）

｛

x=x/10；

i++;

｝

return i;

｝

void main(）

{

int u,v;

cout<<；输入两个位数相同的大整数：＆lt；<；endl;

cin＆gt;>u;

cin>＆gt;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＆lt；=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＆lt;<u＆lt;<*＆lt；<；v＆lt；＆lt；=＆lt;<p;

}

教师评语：

成绩：√优 良 中 及格 不及格

算法实验报告二 动态规划法实验

一、实验目的及要求

利用动态规划方法设计背包问题算法，掌握动态规划法的基本思想和算法设计的基本步骤.

要求：设计0/1背包问题的动态规划算法，要求输出背包内物品的最大价值以及选入背包的物品种类。利用c语言（c++语言）实现算法,给出程序的正确运行结果.

二、算法描述

输入：各物品的体积、价值，背包容量

输出:放入背包的物品的体积,放入物品的最大价值

for i＆lt；-0 to n

v[i,0］<；-0

end for

for j＆lt；-0 to c

v[j，0］<；-0

end for

for i<；-1 to n

for j＆lt;—1 to c

v［i,j］＆lt；-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＆gt;

#define n 10

#define c 12

void main(）

｛

int s[n],v[n];

int v[n+1］［c+1］；

int item[c］;

cout<；<；物品的体积：<＆lt；endl;

for(int f=0；f<；n;f++)

cin＆gt;＆gt;s[f]；

cout<<物品的价值:＆lt;＆lt;endl；

for（int h=0;h＆lt；n；h++)

cin＆gt;>；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＆lt；=c；j++）

｛

v［i］［j]=v[i-1］[j］；

if（s［i]<=j &；＆amp; v［i-1][j-s[i］]+v[i]＆gt;v［i]［j]） ｛

v[i］［j]=v[i-1][j—s［i］]+v[i］； item[j]=i；

｝

｝

}

cout<<；放入背包的物品的体积:<；<endl； for（int p=c；p＆gt；=1;p=p—s［item［p]］)

{

cout<；＆lt；s[item[p］］;

cout＆lt;<endl;

｝

cout<＆lt;背包的最大价值:；

cout＆lt;<；v［n］［c］＆lt;＆lt；endl；

}

教师评语：

成绩：√优 良 中

及格 不及格篇二：分治算法实验报告

本科学生综合性实验报告

姓名＿＿＿ 刘春云 学号＿ 0103918＿＿

＿

专 业＿ ＿软件工程＿＿ 班级＿ 103＿ ＿

实验项目名称＿二分搜索问题的分治算法实验 指导教师及职称＿＿＿＿＿赵晓平＿＿＿ ＿ ＿ 开课学期 2011

至＿ 2012 学年＿ 3 ＿学期

上课时间 2012 年 2 月 18 日

学生实验报告（1）

一、问题描述

二分查找又称折半查找,即在一串已排好序的需要处理的数据中多次用折半的方法查找出要搜索出的数据.

二、解题思路

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较，如果两者相等,则查找成功；否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功,或直到子表不存在为止，此时查找不

成功。

三、算法描述

用一个数组来存储数据，具体的结构体为： typedef struct list ｛

double elem[100］； int length;

}list;其中length是数据的总个数

比较表中间位置记录的关键字与查找关键字的大小，逐步缩小查找范围 实现代码为： while（low＆lt；high）

{

mid=（low+high）/2； if(l。elem［mid]==key） ｛ ｝

else if(l。elem［mid］<key）

low=mid；

outfile＆lt;<你所要搜索的数据在第<；<；mid+1＆lt;＆lt；个位置＆lt；<；endl； break；

else

high=mid;

if（high==low+1） {

outfile＆lt;<；抱歉！你所要搜索的数据不在你所输入的数据中break；

＆lt;＆lt；endl;

范围

｝

}在上段代码中low表示搜索区间的最小范围,hiah则表示搜索区间的最大

在代码中出现的int init_list（list&；l)是一个初始函数用于从input.txt文件中读入

数据并判断数据是否升序排列。int search(int low,int high,list＆amp;l)是查找函数用于折半查找。

四、算法实现

#include <iostream＆gt； #include<fstream>； using namespace std; typedef struct list ｛

double elem[100］； int length;

｝list；

int init_list（list&l）//初始化函数 ｛ ｝

int search(int low，int high，list&；l）//查找函数 ｛

int search（int low,int high,list＆amp;l）； int n=0； ifstream infile;

cout＆lt；＆lt；请输入数据(必须是从小到大排序的)<<endl; infile。open（input。txt,ios：:in）； ofstream outfile;

outfile.open(output。txt，ios：：app);

while(infile>；＆gt;l.elem［n］）//从文件中输入已排序数组，直到文件中无数据读取

n++；

infile。close（）； l.length=n;

for(int i=0；i<l.length—1;i++)//判断输入的数据是否有序 {

if(l。elem[i]>l。elem［i+1］） { ｝

outfile＆lt;<朋友请不要玩我!<＆lt;endl; return 0；

｝//判断输入的数据是否有序

cout<；<；二分查找中。。.。。。<<endl； search（0,l.length—1，l）;

return 1；

ofstream outfile;

outfile.open(output。txt,ios：：app)； int mid=0；//中点篇三：分治法实验报告

石家庄经济学院

《算法设计与分析》实验报告

姓 名：

班 级：

学 号:

指导教师：

完成日期:

一、实验名称

分治法实验

二、实验目的

1. 掌握分治法的基本思想、求解问题的基本步骤;

2. 掌握分支算法的一般模式;

3. 根据问题采取有效的分解和合并的方式,能够分析确定问题的阈值;

4. 掌握分治算法的时间复杂度,并能利用c语言实现算法.

三、实验内容及要求

1. 大整数乘法。

要求:

(1） 求解两个n位的二进制整数的乘法，设n=2k；

(2） 利用分治的思想分析和求解问题；

(3） 利用c语言实现算法，要求结果正确。

2. 矩阵相乘（选做)

（1） 求解两个n阶方阵的乘法,设n=2k；

（2） 可利用基本的分解方法或者stranssen方法求解;

(3） 利用c语言实现算法，要求结果正确.

四、问题分析及算法设计

1. 大整数乘法

问题分析:

算法设计：

算法复杂度分析：

2. 矩阵乘法

问题分析：

算法设计：

算法复杂度分析:

五、代码及运行结果

六、实验总结

（要求总结本次实验遇到的问题及解决方法，收获和不足，300字以上，提交报告时删去此行）

教师评语：

成绩： 优 良 中 及格 不及格篇四：算法-实验报告-分治法

年级 2012 学院 专业班级 学生姓名 学号

《 算法分析与设计 》实验报告(1）

篇五：算法实验四分治法实验报告

算法实验四 分治法实验

实验一 最近点对

最近点对问题描述：对平面上给定的n个点,给出所有点对的最短距离即，输入是平面上的n个点，输出是n点中具有最短距离的两点要求随机生成n个点的平面坐标，应用穷举法编程计算出所有点对的最短距离要求随机生成n个点的平面坐标，应用分治法编程计算出所有点对的最短距离.

二、实验数据及分析

平面点数为100：

平面点数为 500

平面点数为1000:

可以看出，分治法的运行效率要明显比直接法要高。