算法设计与分析作业一.docx

算法设计与分析作业一.docx

《算法设计与分析作业一.docx》由会员分享，可在线阅读，更多相关《算法设计与分析作业一.docx（16页珍藏版）》请在冰点文库上搜索。

算法设计与分析作业一

算法设计与分析

实验报告

学院信息科学与技术学院

专业班级软件工程3班

学号20122668

姓名王建君

指导教师尹治本

2014年10月

实验一同时求最大元与次大元

1、问题提出

在N个元素中同时求出最大元与次大元。

2、求解思路

利用分治法解决问题。

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。

递归地解这些子问题，然后将各个子问题解合并得到原问题的解。

3、算法复杂度

当n=1时，不需要比较就可知最大元和次大元均为该数本身。

当n=2时，一次比较就可以找出两个元素的最大元和次大元。

当n>2时，可以把n个数据元素分为大致相等的两半，一半有n/2个数据元素，而另一半有n/2个数据元素。

先分别找出各自组中的最大元和最小元，然后将两个最大元进行比较，就可得n个元素的最大元；将两个最小元中的大元与两个最大元中的小元进行比较，就可得n个元素的次大元。

在规模为n的数据元素集合中找出最大元和次大元，至少需要5n/2-4次比较，即5n/2-4是找最大次大元算法的下界，得算法复杂度

。

4、源代码

#include

#include

#defineN10//宏定义元素的个数

intmax（inta,intb）

{

if（a>b）

returna;

else

returnb;

}

intmin（inta,intb）

{

if（a

returna;

else

returnb;

}

voidSearch（inta[],int*max0,int*second0,intn）

{

intg[30];

inti,m;

intmax1,max2,second1,second2;

if（n==1）

{

*max0=a[0];

*second0=a[0];

}

elseif（n==2）

{

*max0=max（a[0],a[1]）;

*second0=min（a[0],a[1]）;

}

else

{

m=n/2;

for（i=0;i

g[i]=a[i];

Search（g,&max1,&second1,m）;

for（i=0;i

g[i]=a[i+m];

Search（g,&max2,&second2,n-m）;

*max0=max（max1,max2）;

*second0=max（min（max1,max2）,max（second1,second2））;

}

}

intmain（）

{

inta[N];

inti,max,second;

system（"title软件3班王建君20122668分治法求最大元与次大元"）;

printf（"请输入%d个数字:

\n",N）;

for（i=0;i

scanf（"%d",&a[i]）;

Search（a,&max,&second,N）;

printf（"最大元为%d\n次大元为%d\n",max,second）;

return0;

}

5、结果分析

运算结果截图如下

依次输入10个数字12、3、4、9、6、87、34、23、4、2后求得最大元为87，次大元为34。

实验二实现两个大整数的乘法

1、问题提出

实现两个大整数的乘法。

2、求解思路

利用分治法解决问题。

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。

递归地解这些子问题，然后将各个子问题解合并得到原问题的解。

3、算法复杂度

设X和Y都是n位的二进制整数，现在要计算它们的乘积XY，我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位（为简单起见，假设n是2的幂），如下图所示：

由此，X=A2n/2+B，Y=C2n/2+D，这样，X和Y的乘积可表示为：

XY=AC2n+[（A-B）（D-C）+AC+BD]2n/2+BD。

它仅需做3次n/2位整数的乘法（AC，BD和（A-B）（D-C）），6次加、减法和2次移位，由此可得算法复杂度为：

用解递归方程的套用法可得其解为：

。

4、源代码

#include

#include

#include

#include

usingnamespacestd;

//string类型转换成int类型

intstring_to_num（stringk）

{

intback;

stringstreaminstr（k）;

instr>>back;

returnback;

}

//整形数转换为string类型

stringnum_to_string（intintValue）

{

stringresult;

stringstreamstream;

stream<

stream>>result;

returnresult;

}

//在字符串str前添加s个零

stringstringBeforeZero（stringstr,ints）

{

for（inti=0;i

{

str.insert（0,"0"）;

}

returnstr;

}

//两个大整数字符串相加，超出计算机表示范围的数也能实现相加（本函数可以实现大整数加法运算）

stringstringAddstring（stringstr1,stringstr2）

{

//假定str1和str2是相等的长度，不相等时在前面自动补零，使两个字符串长度相等

if（str1.size（）>str2.size（））

{

str2=stringBeforeZero（str2,str1.size（）-str2.size（））;

}

elseif（str1.size（）

{

str1=stringBeforeZero（str1,str2.size（）-str1.size（））;

}

stringresult;

intflag=0;//前一进位是否有标志,0代表无进位，1代表有进位

for（inti=str1.size（）-1;i>=0;i--）

{

intc=（str1[i]-'0'）+（str2[i]-'0'）+flag;//利用ASCII码对字符进行运算,这里加上flag代表的是:

当前一位有进位时加1，无进位时加0

flag=c/10;//c大于10时，flag置为1，否则为0

c%=10;//c大于10时取模，否则为其本身

result.insert（0,num_to_string（c））;//在result字符串最前端插入新生成的单个字符

}

if（0!

=flag）//最后一为（最高位）判断，如果有进位则再添一位

{

result.insert（0,num_to_string（flag））;

}

returnresult;

}

/*两个大整数字符串相减，超出计算机表示范围的数也能实现相减（在这里比较特殊，第一个参数一定大于第二个参数,

因为：

a1*b0+a0*b1=（a1+a0）*（b1+b0）-（a1*b1+a0*b0）>0,所以（a1+a0）*（b1+b0）>（a1*b1+a0*b0）

这个函数的两个参数，第一个代表的其实就是（a1+a0）*（b1+b0），第二个代表的其实就是（a1*b1+a0*b0）

所以本函数里不用考虑最终得到结果为负数的情况，至于计算有关大整数负数相乘的问题可以通过其他途径判断

*/

stringstringSubtractstring（stringstr1,stringstr2）

{

//对传进来的两个数进行修剪，如果前面几位有0则先去掉，便于统一处理

while（'0'==str1[0]&&str1.size（）>1）

{

str1=str1.substr（1,str1.size（）-1）;

}

while（'0'==str2[0]&&str2.size（）>1）

{

str2=str2.substr（1,str2.size（）-1）;

}

//使两个字符串长度相等

if（str1.size（）>str2.size（））

{

str2=stringBeforeZero（str2,str1.size（）-str2.size（））;

}

stringresult;

for（inti=str1.size（）-1;i>=0;i--）

{

intc=（str1[i]-'0'）-（str2[i]-'0'）;//利用ASCII码进行各位减法运算

if（c<0）//当不够减时向前一位借位，前一位也不够位时再向前一位借位，依次如下

{

c+=10;

intprePos=i-1;

charpreChar=str1[prePos];

while（'0'==preChar）

{

str1[prePos]='9';

prePos-=1;

preChar=str1[prePos];

}

str1[prePos]-=1;

}

result.insert（0,num_to_string（c））;//在result字符串最前端插入新生成的单个字符

}

returnresult;

}

//在字符串str后跟随s个零

stringstringFollowZero（stringstr,ints）

{

for（inti=0;i

{

str.insert（str.size（）,"0"）;

}

returnstr;

}

//分治法大整数乘法实现函数

stringIntMult（stringx,stringy）//递归函数

{

//对传进来的第一个数进行修剪，如果前面几位有0则先去掉，便于统一处理

while（'0'==x[0]&&x.size（）>1）

{

x=x.substr（1,x.size（）-1）;

}

//对传进来的第二个数进行修剪，如果前面几位有0则先去掉，便于统一处理

while（'0'==y[0]&&y.size（）>1）

{

y=y.substr（1,y.size（）-1）;

}

/*这里的f变量代表在两个数据字符串长度不想等或者不是2的指数倍的情况下，所要统一的长度，这样做是为了让数据长度为2的n次方

的情况下便于利用分治法处理

*/

intf=4;

/*当两字符串中有任意一个字符串长度大于2时都要通过与上面定义的f值进行比较，使其达到数据长度为2的n次方，实现方式是在前面

补0，这样可以保证数据值大小不变

*/

if（x.size（）>2||y.size（）>2）

{

if（x.size（）>=y.size（））//第一个数长度大于等于第二个数长度的情况

{

while（x.size（）>f）//判断f值

{

f*=2;

}

if（x.size（）!

=f）

{

x=stringBeforeZero（x,f-x.size（））;

y=stringBeforeZero（y,f-y.size（））;

}

}

else//第二个数长度大于第一个数长度的情况

{

while（y.size（）>f）//判断f值

{

f*=2;

}

if（y.size（）!

=f）

{

x=stringBeforeZero（x,f-x.size（））;

y=stringBeforeZero（y,f-y.size（））;

}

}

}

if（1==x.size（））//数据长度为1时,在前面补一个0（这里之所以会出现长度为1的数据是因为前面对数据修剪过）

{

x=stringBeforeZero（x,1）;

}

if（1==y.size（））//数据长度为1时,在前面补一个0（这里之所以会出现长度为1的数据是因为前面对数据修剪过）

{

y=stringBeforeZero（y,1）;

}

if（x.size（）>y.size（））//最后一次对数据校正，确保两个数据长度统一

{

y=stringBeforeZero（y,x.size（）-y.size（））;

}

if（x.size（）

{

x=stringBeforeZero（x,y.size（）-x.size（））;

}

ints=x.size（）;

stringa1,a0,b1,b0;

if（s>1）

{

a1=x.substr（0,s/2）;

a0=x.substr（s/2,s-1）;

b1=y.substr（0,s/2）;

b0=y.substr（s/2,s-1）;

}

stringresult;

if（s==2）//长度为2时代表着递归的结束条件

{

intna=string_to_num（a1）;

intnb=string_to_num（a0）;

intnc=string_to_num（b1）;

intnd=string_to_num（b0）;

result=num_to_string（（na*10+nb）*（nc*10+nd））;

}

else{//长度不为2时利用分治法进行递归运算

/***************************************************

小提示:

c=a*b=c2*（10^n）+c1*（10^（n/2））+c0;

a=a1a0=a1*（10^（n/2））+a0;

b=b1b0=b1*（10^（n/2））+b0;

c2=a1*b1;c0=a0*b0;

c1=（a1+a0）*（b1+b0）-（c2+c0）;

****************************************************/

stringc2=IntMult（a1,b1）;//（a1*b1）

stringc0=IntMult（a0,b0）;//（a0*b0）

stringc1_1=stringAddstring（a1,a0）;//（a1+a0）

stringc1_2=stringAddstring（b1,b0）;//（b1+b0）

stringc1_3=IntMult（c1_1,c1_2）;//（a1+a0）*（b1+b0）

stringc1_4=stringAddstring（c2,c0）;//（c2+c0）

stringc1=stringSubtractstring（c1_3,c1_4）;//（a1+a0）*（b1+b0）-（c2+c0）

strings1=stringFollowZero（c1,s/2）;//c1*（10^（n/2））

strings2=stringFollowZero（c2,s）;//c2*（10^n）

result=stringAddstring（stringAddstring（s2,s1）,c0）;//c2*（10^n）+c1*（10^（n/2））+c0

}

returnresult;

}

intmain（）

{

intf=1;

stringA,B,C,D;

stringnum1,num2;

stringr;

system（"title软件3班王建君20122668分治法实现大整数乘法"）;

cout<<"请输入第一个大整数（任意长度）:

";

cin>>num1;

inti=0;

//判断第一个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入

for（i=0;i

{

if（num1[i]<'0'||num1[i]>'9'）

{

cout<<"您输入的数据不合法,请输入有效的整数!

"<

cin>>num1;

i=-1;

}

}

cout<<"请输入第二个大整数（任意长度）:

";

cin>>num2;

//判断第二个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入

for（i=0;i

{

if（num2[i]<'0'||num2[i]>'9'）

{

cout<<"您输入的数据不合法,请输入有效的整数!

"<

cin>>num2;

i=-1;

}

}

r=IntMult（num1,num2）;

//对求得的结果进行修剪，去掉最前面的几个0

while（'0'==r[0]&&r.size（）>1）

{

r=r.substr（1,r.size（）-1）;

}

cout<<"两数相乘结果为:

"<

cout<

}

5、结果分析

计算结果截图如下

即当00112233445566778899与99887766554433221100相乘得11210748210374098777790374124081568900