算法设计与分析(作业一)

《算法设计与分析(作业一)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学院。信息科学与技术学院专业班级软件工程3班学号20122668姓名王建君指导教师尹治本2014年10月实验一同时求最大元与次大元一、问题提出在N个元素中同时求出®大元与次大元。二、求解思路利用分治法解决问题。将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立II与原问题相同。递归地解这些子问题，然后将各个子问题解合并得到原问题的解。三、算法复杂度当时，不需要比较就可知最大元和次大元均为该数本身。当n=2时，一次比较就可以找出两个元素的最大元和次大元。当n〉2时，可以把n个数据元素分为大致相等的两半，一半有n/2个数据元素，而另

2、一半有n/2个数据元素。先分别找出各自组中的S大元和最小元，然后将两个最大元进行比较，就可得n个元素的最大元：将两个最小元屮的大元与两个最大元中的小元进行比较，就可得n个元素的次大元。在规模力n的数据元素集合中找出最大元和次大元，至少需要5n/2-4次比较，即5n/2-4是找最大次大元算法的下界，得算法S杂度T(Z1)=5zi/2-4=。四、源代码#include#include#defineN10//宏定义元素的个数intmax(inta，intb){if(a〉b)returna;elsereturnb;

3、)intmin(inta,intb){if(a

4、g,&maxlsecond1,m);for(i=0;i

5、，&a[i]);Search(a，&max，&second，N);printf("最大元为。/od次大元为。/odiT，max，second);return0;}五、结果分析运算结果截图如下软件3班王建君20122668请输入10个数字：12349687432342J大元为87茨大兀为43Pressanykeytocontinue依次输入10个数字12、3、4、9、6、87、34、23、4、2后求得最大元为87,次大元为34实验二实现两个大整数的乘法一、问题提出实现两个大整数的乘法。二、求解思路利用分治法解决问题。将一个规模为n的问题分解

6、为k个规模较小的子问题，这些子问题互相独立且与原W题相同。递归地解这些子问题，然后将各个子问题解合并得到原问题的解。三、算法复杂度设X和Y都是n位的二进制整数，现在要计算它们的乘积XY，我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，如下图所示：X=A，Y=CDm/2位w/2位m/2位n/2位由此，X=A2n/2+B,Y=C2n/2+D,这样，X和Y的乘积可表示为：XY=AC2n+[(A-B)(D-C)+AC+BDj2n/2+BD。它仅耑做3次n/2位整数的乘法(AC,BD和(A-B)(D-C)),6次

7、加、减法和2次移位，由此可得算法复杂度为：3Tfn/2)4-cn用解递归方程的套用法可得其解为:四、源代码#include^include^include#includeusingnamespacestd;//string类型转换成int类型T(n)=O(nlog23)=O("159)。t(h)=intstring_to_num(stringk)intback;stringstreaminstr(k);instr»back;returnback;}//整形数转换力stri

8、ng类型stringnum_to_string(intintValue){stringresult;stringstreamstream;stream