- 1、本文档共21页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
专题算法分析与设计.doc
专题十:算法分析与设计
1.常用的算法设计方法:
1.1 迭代法
1.2 穷举搜索法
1.3 递推法
1.4 递归法
1.5 贪婪法
1.6 分治法
1.7 动态规划法
1.8 回溯法
算法基础部分:
算法是对特定问题求解步骤的一种描述,算法是指令的有限序列,其中每一条指令表示一个或多个操作。
算法具有以下5个属性:
有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。
确定性:算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
可行性:一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入:一个算法有零个或多个输入,这些输入取自于某个特定对象的集合。
输出:一个算法有一个或多个输出,这些输出同输入有着某些特定关系的量。
所以对应的算法设计的要求:
正确性:算法应满足具体问题的需求;
可读性:算法应该好读,以有利于读者对程序的理解;
健壮性:算法应具有容错处理,当输入为非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。
效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。
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;
????????????? x0=g(x1);??? /*按特定的方程计算新的近似根*/
????????????? } while ( fabs(x0-x1)Epsilon);
?????? printf(“方程的近似根是%f\n”,x0);
}
迭代算法也常用于求方程组的根,令
????????????? X=(x0,x1,…,xn-1)
设方程组为:
????????????? xi=gi(X)???????? (I=0,1,…,n-1)
则求方程组根的迭代算法可描述如下:
【算法】迭代法求方程组的根
?????? { ??? for (i=0;in;i++)
???????????????????? x[i]=初始近似根;
????????????? do {
???????????????????? for (i=0;in;i++)
??????????????????????????? y[i]=x[i];
???????????????????? for (i=0;in;i++)
??????????????????????????? x[i]=gi(X);
???????????????????? for (delta=0.0,i=0;in;i++)
if (fabs(y[i]-x[i])delta)???????
?delta=fabs(y[i]-x[i]);
???????????????????? } while (deltaEpsilon);
????????????? for (i=0;in;i++)
???????????????????? printf(“变量x[%d]的近似根是 %f”,I,x[i]);
????????????? printf(“\n”);
?????? }
?????? 具体使用迭代法求根时应注意以下两种可能发生的情况:
(1)如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制;
(2)方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。
1.2 穷举搜索法:
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从中找出那些符合要求的候选解作为问题的解。
要解决的问题只有有限种可能,在没有更好算法时总可以用穷举搜索的办法解决,即逐个的检查所有可能的情况。可以想象,情况较多时这种方法极为费时。实际上并不需要机械的检查每一种情况,常常是可以提前判断出某些情况不可能取到最优解,从而可以提前舍弃这些情况。这样也是隐含的检查了所有可能的情况,既减少了搜索量,又保证了不
文档评论(0)