算法设计与分析课程报告

《算法设计与分析课程报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析》课程考试报告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.1算法基本思想；（2分）答：蛮力算法是根据问题的定义，根据问题的步骤，直接了当地对问题进行求解。蛮力算法的核心就是直接去做，直接去解决问题。1.2算法描述（可以用流程图、自然语言或伪代码来描述）；（3分）答：据p(x)=a0x0+a1x1+…+an-2xn-2+an-1xn-1基于问题定义设计算法：

2、直接先分别算出两个乘数，再求两个数的成绩，最后累加。1.3算法实现的C源程序代码；（6分）#include#includevoidmain(){intx,n,i,A,X;doublep=0,sum=0;printf("请输入xn：");scanf("%d%d",&x,&n);for(i=0;i

3、等角度来分析）。（6分）答：①该算法时间复杂度为O（n），简短清晰便于阅读。②8《算法设计与分析》课程考试报告在健壮性方面，此算法只对少量输入能做出正确的处理，在使用范围上有很大的限制性。如输入x=2,n=32，结果出错，如下图所示：2.分治算法（25分）查找问题：输入100个整数，使用分治算法实现折半查找，统计某个整数出现的次数。2.1算法基本思想；（2分）答：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解

4、为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。步骤：①划分②求解子问题③合并2.2算法描述（可以用流程图、自然语言或伪代码来描述）；（3分）答：1、low=1;high=n;//设置初始查找区间2、测试查找区间[low，high]是否存在，若不存在，则查找失败；否则3、取中间点mid=(low+high)/2;比较k与[mid],有一下三种情况：①若kr[mid],则low=mid+1;查找在左半区进行，转2；③若k

5、计k出现次数，返回统计记录2.3算法实现的C源程序代码；（6分）#includeusingnamespacestd;voidInsertSort(intA[],intn)//插入排序{inti,j,temp;for(i=1;i0&&temp

6、ntj=0;while(low<=high){mid=(low+high)/2;if(key==A[mid]){j++;BinSearch(A,key,low,mid-1);BinSearch(A,key,mid+1,high);returnj;}elseif(key

7、n];printf("请输入要排序的数：");for(i=0;i

8、}2.4程序运行结果的屏幕截图；（6分）2.5算法分析（可以从算法复杂度、优缺点或改进方法等角度来分析）。（6分）答：该算