2011级《算法设计与分析》

《2011级《算法设计与分析》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》课程考试报告《算法设计与分析》课程考试报告姓名：学号：班别：任课教师：黄海滨2013年06月25日《算法设计与分析》课程考试要求本课程考试要求对给定问题编写C语言程序求解，以打印文档形式提交《算法设计与分析》课程考试报告算法设计报告及程序清单，同时在实验室运行程序进行验收。一．考试内容1.蛮力算法（25分）数值问题：设x=2，n=30，a0=n，a1=n-1，a3=n-2，…，an-2=2，an-1=1，要求用蛮力算法求解多项式p(x)=a0x0+a1x1+…+an-2xn-2+an-1xn-1的值。（1）算法基本思想；（2分）蛮力算法

2、根据问题的定义，按照问题的步骤，直截了当地对问题进行求解，借助计算机的运算能力，简单、自然，然而往往又非常有效。（2）算法描述（可以用流程图、自然语言或伪代码来描述）；（3分）首先定义所要求的数据变量，然后运用一个循环语句对一遍一遍地对语句进行搜索计算，直到最后得出最终结果。（3）算法实现的C源程序代码；（6分）#include#includevoidmain(){intsum=0;inta,c,x,i;intb=0;a=30;x=2;c=0;for(i=0;i<30;i++){b=a*pow(x,c);sum=sum+

3、b;a=a-1;c=c+1;}printf("sum=%d",sum)；}（4）程序运行结果的屏幕截图；（6分）（5）算法分析（可以从算法复杂度、优缺点或改进方法等角度来分析）。（6分）蛮力算法的应用有通用性《算法设计与分析》课程考试报告

4、、启发性、实用性、准绳性的优点，但是缺点也很明显就是蛮力算法的效率不是很高。2.分治算法（25分）查找问题：输入100个整数，使用分治算法实现折半查找，统计某个整数出现的次数。（1）算法基本思想；（2分）这是一种将复杂难解的问题分割为规模和结构相同或相似的子问题，通过对简单问题的求解而达到对原问题的求解的目的的算法

5、设计方法。分治算法能够使原本纷繁复杂的问题变得清晰明朗，而且能够通过将问题的规模变小而降低问题求解的难度。（2）算法描述（可以用流程图、自然语言或伪代码来描述）；（3分）BINARY-SEARCH(A,T)L<--0R<---n-1Whilel<=rDom<--(l+r)/2IfT=A[m]ThenreturnmElseifvoidmain(){intlow=0,high=99,x,a[100],i,k;intSe

6、arch(intlow,inthigh,intx,inta[100]);//变量赋值初始化printf("输入一百个数:");for(i=0;i<100;i++)scanf("%d",&a[i]);printf("输入要查找的数：");scanf("%d",&x);k=Search(low,high,x,a);printf("%d",k);}intSearch(intlow,inthigh,intx,inta[100]){《算法设计与分析》课程考试报告intmid;intk=0,j;while(low<=high){mid=(low+high

7、)/2;if(a[mid]==x){k++;for(j=0;j

8、度、优缺点或改进方法等角度来分析）。（6分）分治算法将问题分解为了一些更小更容易解决的问题，它具有分解性、递归性、综合性的特点。本题用先将问题进行折半分解，大大地提高了算法运行的效率，也使降低了代码的复杂性使其更容易被人理解。令外它很好地应用了递归的特性，使问题得到了很好的划分和求解。3.贪心算法（25分）活动安排问题：根据下表各个活动的时间，用贪心算法找出一个最大兼容活动集合。活动编号12345678910开始时间3251712861113结束时间749613151081714（1）算法基本思想；（2分）从问题的某一个初始解出发逐步逼近给定的目标，以尽

9、可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。（2）