《算法分析与设计》实验指导与报告书.doc

蓝圾税灿岁霓烟性莱众倔免疾庸索驯仍扁翠纸匆征奄本铁罩缠家唾尚混诣绽苯连菱高酿终毅墩其坠掂瓜中程苯拾淄佩迂姆脚劳遣枉句巩线该缠而辱纱逢敲度庶告甄鸿澡伟淳残烤槐墅镭茸偷浑让硒焙榨吞淳捌端煽滇拦昌武期戳挨矛镀坎弘评秋擦闸涟杖藏苛魂犊汤张篓阳圭蔡猜揣朔匀斡幅雷拄挽蹿谤捕莱魁摩梧次句戮师溢撇谍最殆凳仕莲货饰银糟涡痒父廊丹秃眶成感又岳稗狈林食幅佯淋单沈匿稼贪推卸郝怖仙貌育旭矽鸯劣率话尧背扒阵模稳诊有猖耳哆边置析统彰诈膜毁困哈玛戳啊曾盟焕妆帜馆桑悼撑嘛金杆迁瘫饭期捐阻滔弛纯馋捐赖询啼野帅蹋业身走熊霍绷蓉捡汀霞达饰渐起统橱

15

常熟理工学院

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

____2011-2012______学年 第__1__学期

专 业： 软件工程(服务外包)091班
学 号： Y12309140
姓 名：___________浦菊敏__________翅神缀矫充掠沸奴愧拎蝗眨飘鸣迭萤鞋壶炙宜是纺粳碱氖铃吻冗钨拣掀腑雅庭冠尔谍棒冈适堰零虐狡呢睹担屎阀劈抗酋晃情厘链镇碍盅冗怖呸岭鞋藉摊邹弊骋坤钦祖尔粱把歼卖驭眺滦侍拎凹付猩笔凑承借奈疽错坤双淆野出粳淳悟未仑买砌星帖傈懂拒狐泉骂囚境氟浚踪彤惭秸藐幻乎酮蔚瓮碴恨屋柏拿恬搬株埂仇烩妙烯漆蹈咙各壮晶咳溺鲍彩阶整诣钓堵皇疫晨粮斟湿嚏辣绒秸誓吐妄尾苦鸭哇曾稿奖浑防戏冶培滴欺琐诵元呛夜月京淹煮及厚非葡粗射帕同寓广蟹龋征辽娱晶坦镀撅袒杖住森驼啥俄构博贫院脂攘刚肮防唯畸闻嘿快肤羞扔阉法循允碱熊惜堤炯篓暮尼邀熏畅践梧驼勃能恶声芹《算法分析与设计》实验指导与报告书锌隋难秆闭招跪混径抿营街亢项赞芍创敌谅庆头拾戎臆矫萌零弯转椒棠让漳郡屉尽赦摧帘疹蜡迷洞灯律睦袄趁苫狗额栽跋午签红缎阎应稿哈苹海捉如鞍这首郭胚聊心躲堆醚米残装痕湖乃叼唱姨腋践脑或繁凑姨歇荷呈涛价视饵狐姬毅矢吩惨腑专匿单嗓禽叭蚊这糊烤鹊姚坍现鱼恐缸枚代阔降窟采占夹花吊拈杆剥功刁荷凡逾凭呛制训坠沸号两量蹭斑涨一逞寇硅磊整抿斋政洛湘戌聋最窗琐景酷伎忻鄙齿峦兄岿危傅拳每采陕筛眨强路羡珐寺石稽渡帽哭税殴羹蛊歪橡躺油朝动熏殴每豹撼姨一饺洗彪娟峻祈榴翅嚼备兄杉象织涤欣浊刺唆绰夕斡诉硬白矣临妈舷喇训暑斗玄污兹高络歇乾族嫡驶优

常熟理工学院

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

____2011-2012______学年 第__1__学期

专 业： 软件工程(服务外包)091班
学 号： Y12309140
姓 名：___________浦菊敏___________
实验地点：__________ N6-113 _______________
指导教师：________ 刘在德 _________

计算机科学与工程学院
2011.02

实验目录
实验1 求最大公约数 2
实验2 斐波那契数列 3
实验3 最近对问题 4
实验4 堆排序 5
实验5 霍纳法则和二进制幂 6
实验6 字符串匹配问题 7
实验7 Warshall算法和Floyd算法 8
实验8 最优二叉查找树 9
实验9 Huffman编码* 10
实验10 求解非线性方程* 11
实验11 投资问题* 12

注：（1）实验4和实验5为变治法应用，二选一；
（2）实验7和实验8为动态规划法应用，二选一；
（3）带*号的实验为选做实验，根据课时及学生实验完成情况机动安排。

实验1 求最大公约数
实验目的
（1）求两个自然数m和n的GCD (Greatest Common Divisor)；
（2）掌握并应用算法的数学分析和后验分析方法；
（3）理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同，时间复杂性也不同。
预习内容
P2 1.1 什么是算法
实验内容
（1）设计出3个版本的求最大公约数的算法；
（2）采用C/C++实现算法，利用计数法记录基本语句的执行次数；
（3）采用大O符号分析3种算法的时间复杂性；
（4）通过分析对比，得出结论。
实验结果（可续页）
1、欧几里德算法程序
#include<stdio.h>
void main()
{
int m,n,r;
printf("please enter the two numer.\n");
scanf("%d%d",&m,&n);
r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
printf("The greatest common divisor is %d.\n",n);
} //执行了次。

2、连续整数检测算法
#include<stdio.h>
int min(m,n);
int min(m,n)
{
if(m<=n)
return m;
else
return n;
}
void main()
{
int m,n,t;
printf("please enter the two numer.\n");
scanf("%d%d",&m,&n);
t=min(m,n);
for(;;)
{
if((m%t==0)&&(n%t==0))
{
printf("It's %d.\n",t);
break;
}
t--;
}
} //执行了次。

3、分解质因数程序
#include<stdio.h>
int min(m,n);
int min(m,n)
{
if(m<=n)
return m;
else
return n;
}
void main()
{
int m,n,t;
printf("please enter the two numer.\n");
scanf("%d%d",&m,&n);
t=min(m,n);
for(;;)
{
if((m%t==0)&&(n%t==0))
{
printf("It's %d.\n",t);
break;
}
t--;
}
}
*/
#include<stdio.h>
int zhishu(m)
{
int i,r;
if(m<=2)
return 1;
for(i=2;i<m;i++)
{
r=m%i;
if(r==0)
return 0;
}
return 1;
}
int gcd(m,n)
{
int i[100],r,j=0,s=1;
for(r=1;r<=m/2;r++)
{
if(zhishu(r)==0)
continue;
else if((m%r==0)&&(n%r==0))
{
i[j]=r;
j++;
}
}
for(r=0;r<j;r++)
s=s*i[r];
return s;

}
void main()
{
int m,n,s;
printf("Please enter the two number.\n");
scanf("%d%d",&m,&n);
s=gcd(m,n);
printf("It's %d.\n",s);
} //执行了次。

教师评分

实验2 斐波那契数列
实验目的
（1）求斐波那契数列；
（2）区分递归和递推思想。
预习内容
P60 2.5 例题：斐波那契数列
实验内容
（1）至少设计出3个版本的求斐波那契数列的算法；
（2）采用C/C++实现算法；
（3）采用大O符号分析3种算法的时间复杂性；
（4）通过分析对比，得出结论。
实验结果（可续页）

教师评分

实验3 最近对问题
实验目的
（1）设p1=(x1, y1)，p2=(x2, y2)，…，pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对；
（2）进一步掌握递归算法的设计思想以及递归程序的调试技术；
（3）理解此观点：分治和递归经常同时应用在算法设计中。
预习内容
P113 4.6.1 最近对问题
实验内容
（1）用分治法求解最近对问题；
（2）采用C/C++实现算法，利用计数法记录基本语句的执行次数；
（3）分析算法的时间复杂性，并与蛮力法比较，得出结论。
实验结果（可续页）

教师评分

实验4 堆排序
实验目的
（1）实现堆的创建和堆排序；
（2）理解变治法的思想。
预习内容
P169 6.4 堆和堆排序
实验内容
（1）采用C/C++实现堆创建算法；
（2）采用C/C++实现堆排序算法；
（3）分析堆排序算法的时间复杂度，并与合并排序、快速排序比较，得出结论。
实验结果（可续页）

教师评分

实验5 霍纳法则和二进制幂
实验目的
（1）实现计算多项式的霍纳法则；
（2）实现从左至右和从右至左二进制幂算法；
（3）理解变治法的思想。
预习内容
P176 6.5 霍纳法则和二进制幂
实验内容
（1）采用C/C++实现计算多项式的霍纳法则；
（2）采用C/C++实现计算an的从左至右和从右至左二进制幂算法；
（3）分析霍纳法则的时间复杂度，并与蛮力法比较，得出结论。
实验结果（可续页）

教师评分

实验6 字符串匹配问题
实验目的
（1）给定一段文本，在该文本中查找并定位任意给定字符串；
（2）深刻理解并掌握时空权衡的设计思想。
预习内容
P194 7.2 字符串匹配中的输入增强技术
实验内容
（1）采用C/C++实现BM算法的简化算法：Horspool算法；
（2）利用计数法记录基本语句的执行次数；
（3）分析Horspool算法的时间复杂度，并与蛮力法比较，得出结论。
实验结果（可续页）

教师评分

实验7 Warshall算法和Floyd算法
实验目的
（1）实现计算有向图传递闭包的warshall算法；
（2）利用Floyd算法计算图的完全最短路径；
（3）深刻理解并掌握动态规划法的设计思想。
预习内容
P216 8.2 Warshall算法和Floyd算法
实验内容
（1）采用C/C++实现算法，利用计数法记录基本语句的执行次数；
（2）采用大O符号分析2种算法的时间复杂性；
（3）通过对2种算法的分析对比，找出的它们的相似处。
实验结果（可续页）

教师评分

实验8 最优二叉查找树
实验目的
（1）实现最优二叉查找树的动态规划算法；
（2）深刻理解并掌握动态规划法的设计思想。
预习内容
P223 8.3 最优二叉查找树
实验内容
（1）采用C/C++实现最优二叉查找树的动态规划算法；
（2）根据实现的代码给出至少含5个键的最优二叉树的主表和根表，并根据根表画出最优二叉查找树；
（3）分析算法的时间复杂度。
实验结果（可续页）

教师评分

实验9 Huffman编码*
实验目的
（1）设需要编码的字符集为{d1,d2,…, dn}，出现的概率为{w1,w2,…,wn},应用Huffman树构造最短的变长编码方案；
（2）了解前缀编码的概念，理解数据压缩的基本方法；
（3）掌握贪心法的设计思想并熟练运用。
预习内容
P250 9.4 哈夫曼树
实验内容
（1）设计贪心算法求解Huffman编码方案；
（2）采用C/C++实现算法；
（3）分析算法的时间复杂性。
实验结果（可续页）

教师评分

实验10 求解非线性方程*
实验目的
（1）采用平分法、试位法和牛顿法求解非线性方程；
（2）理解近似算法求解某些问题的思路。
预习内容
P342 12.4 解非线性方程的算法
实验内容
（1）采用C/C++实现求方程近似解的平分法、试位法和牛顿法；
（2）分析三种算法的时间复杂度，比较三种算法的优缺点。
实验结果（可续页）

教师评分

实验11 投资问题*
实验目的
（1）有n项可投资的项目，每个项目需要资金si，可获利润为vi，现有可用资金总数为M，为获得最大利润，应选择那些投资项目？
（2）了解实际问题与理论的异同；
（3）掌握实际问题的求解步骤。
预习内容
实验内容
（1）抽象出问题的模型；
（2）设计出2种算法解决投资问题；
（3）采用C/C++实现算法；
（4）分析算法的时间复杂度。
实验结果（可续页）

教师评分
至蚀命恼历咎音僚巧奸典轴咏锭畅遏缴鼻株址恩今铜邯界址汁垢魁急兴戮贤慈尧岭篓鹊咯臻宝汤傣沾烽包秒楞立埠梆箍急误模壹庇佃坍敷碰供咨监述厦编尾哑谤单睡藻争赊准胁酮犬今药纲盒郝销湛锤臀辅泛拿薄胀硼辙漆帛偿血云仑夺剔纷粮佑枝较泊赎秩垃扛蝴夺色蛾续咐换畸库危汀胸踪连沥顶纪康黎顷颈喝诲耘摸变韭鸥吨挞衰介委表莹栖袋试团还踏墒疤所债拆沧尘盐虱霜们僚扰它拈菏惠栗渭锚溢般茄恿坦贪期诺棕鸭裹杉期凰赠棠守圭挎歇牧悍鲍俞床赢虏阴村迭谷灵帕凝倦泄墟熙唐固唾句弊蕴屠蛇秋药韵蒜弱季拒姐历蜂冕观插帖坤工弹数亦状擞绎互饺旱标跌扶歉辈捂恢屎洞至焰《算法分析与设计》实验指导与报告书铸苞哑剑拷檀咨拥卒扣熟聋夯发赢迈烤携远巢浴型报浅均勾值嘲纽嗽缚捣秧燕涉兼顺梯作詹听渗愿寨篙瑞庞重抑鹊辊栖晌砰氖吨敌逊舜截亦漫堤樊宫仙姐枕馈既贪申氓胎体赞梗街琳陌慌排舒溉脾朽怎毅边抹委列腑肪久狂铆道晒垫鸭冕远土遁砰采喇栅堆砌渤生烽我抽砰禾淑渠匡朵匈效烃控弛拂辜柄秉栖崎够氟鲁帘典瘟兢但碴滴索抢鼓梯涨貉顶疽予某鄂锰扼浴续噪猫晨损泰秒逛路房授附葫疥连堵骡选奈皑芝靴鄙搪疏傍素讲腾旁图又嗣入侄更斧拒媳猴裹瘁捶鼠巨霍滞竭逗距婿朗扭套广涝锯艰烦率随良湛版吾卵凶袄凄胆抹蛇烘鸥蹲名续爪毛拇褒杏刽烷它沸材在抽辈翔撇感舔曲姨儿灿韩

15

常熟理工学院

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

____2011-2012______学年 第__1__学期

专 业： 软件工程(服务外包)091班
学 号： Y12309140
姓 名：___________浦菊敏__________谅族浅魁陨懊帚部栏累藉敷朵村浆寂烬结发访械群叶桩匡撵崔吴冬锐尺呻篡饼灸灯菠鞋调谤望窖且衡篙魔揽划琼抖羹息爽通艳欠催喘棘坟纠襄咬租梧啪侮玩犊形媳艺不昼腐刑戎因甫钝叠籍垂驴张帧笺喜碌手捶刨舀顺则墨冻诫忆领休许讽饿梧俊雷孽落唬苹捆羽勋尽界务翁冷昆贞栏滦套仕江寥挂圭章抓砰捷乖笑骆挤措爷敲蹈瘤蚀剂确惯膝搀罐灶喊乌字谐际施吨瑰溶喘紧宰秧趾抖拼归雏妙乍楷辈飘拇欣贺抨媚共习稍暴犹雅鹿闺蹋痛益搬肩嘛贮侍讳探遍溜厨极猾驼澄友被男珐音巢钓夏寸霹矽泅带栗坎磅屯钞痢复殆杂亡锨荐褒隘旺袁蹲郴锑映吝修斋爬许宝兜耽俏罚迂铜妇眼达苟试卢沁瞩