(软考软件设计师)专题十：算法分析与设计

《(软考软件设计师)专题十：算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、(软考软件设计师)专题十：算法分析与设计本文由flynetman贡献doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。书山有路勤为径专题十:专题十:算法分析与设计1．常用的算法设计方法：常用的算法设计方法：1.1迭代法1.2穷举搜索法1.3递推法1.4递归法1.5贪婪法1.6分治法1.7动态规划法1.8回溯法算法基础部分:算法基础部分:算法是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。个属性：算法具有以下5个属性有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条

2、指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。所以对应的算法设计的要求：所以对应的算法设计的要求：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所

3、需要的最大存储空间。一般这两者与问题的规模有关。1.1迭代法：迭代法：迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：（1）选一个方程的近似根，赋给变量x0；（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为：【算法】迭代法求方程的根{x0=初始近似根；do{x1=x0；

4、x0=g(x1)；/*按特定的方程计算新的近似根*/}while(fabs(x0-x1)>Epsilon)；printf(“方程的近似根是%f”，x0)；}迭代算法也常用于求方程组的根，令X=（x0，x1，…，xn-1）设方程组为：xi=gi(X)(I=0，1，…，n-1)则求方程组根的迭代算法可描述如下：【算法】迭代法求方程组的根{for(i=0;i

5、)if(fabs(y[i]-x[i])>delta)delta=fabs(y[i]-x[i])；}while(delta>Epsilon)；for(i=0;i

6、索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。要解决的问题只有有限种可能，在没有更好算法时总可以用穷举搜索的办法解决，即逐个的检查所有可能的情况。可以想象，情况较多时这种方法极为费时。实际上并不需要机械的检查每一种情况，常常是可以提前判断出某些情况不可能取到最优解，从而可以提前舍弃这些情况。这样也是隐含的检查了所有可能的情况，既减少了搜索量，又保证了不漏掉最优解。【问题】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一

7、个解。程序引入变量a、b、c、d、e、f，并让它们分别顺序取1至6的整数，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。#includevoidmain(){inta,b,c,d,e,f;for(a=1;a<=6;a++)//a,b,c,d,e依次取不同的值for(b=1;b<=6;b++){if(b==a)continue;fo