算法设计基本方法

《算法设计基本方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计基本方法（1）列举法(穷举法):指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。例：百鸡问题（教材p6）特点：算法简单，可读性强，直观易于理解和设计适用范围：解决“是否存在”或者“有多少种可能”问题缺点：运算工作量巨大改进方法：分析实际问题，缩小列举范围以减少运算量软肋：不能用以解决列举量无限的问题,或列举量非常大的问题算法设计基本方法（2）归纳法：通过分析少量特殊情况，找出关系，得到结论例：搏彩问题这期彩票该买几呢？第一期3十一2二5十二1三6十三1四8十四0五

2、9十五2六8十六2七7十七3八5十八4九5十九4十3二十4根据曲线，买5比较好归纳法特点：适用面广，高效使用，常能解决许多实际问题适用范围：样本空间有一定规律，多用于预测领域，数据难以获得的工程计算科学计算等领域缺点：归纳出的数学模型需要证明，且代码实现不规范改进方法：常采用不同归纳方法共同求解一个问题软肋：不能求解样本空间过于零散的问题算法设计基本方法（3）递推从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果特点：采用递推关系式数学模型，理论正确性得到保证，由于递推关系式来源于归纳，所以本质上属于归纳法适用范围：数值计算等工程

3、应用缺点：需考虑数值计算中稳定性问题，易产生蝴蝶效应软肋：无递推关系式的问题不可解NYBJ递推据说，美军1910年的一次部队的命令传递是这样的:营长对值班军官:明晚大约8点钟左右，哈雷彗星将可能在这个地区看到，这种彗星每隔76年才能看见一次。命令所有士兵着野战服在操场上集合，我将向他们解释这一罕见的现象。如果下雨的话，就在礼堂集合，我为他们放一部有关彗星的影片。值班军官对连长:根据营长的命令，明晚8点哈雷彗星将在操场上空出现。如果下雨的话，就让士兵穿着野战服列队前往礼堂，这一罕见的现象将在那里出现。连长对排长:根据营长的命令，明晚8点，非

4、凡的哈雷彗星将身穿野战服在礼堂中出现。如果操场上下雨，营长将下达另一个命令，这种命令每隔76年才会出现一次。排长对班长:明晚8点，营长将带着哈雷彗星在礼堂中出现，这是每隔76年才有的事。如果下雨的话，营长将命令彗星穿上野战服到操场上去。班长对士兵:在明晚8点下雨的时候，著名的76岁哈雷将军将在营长的陪同下身着野战服，开着他那“彗星”牌汽车，经过操场前往礼堂。例：计算公式一：记为则初始误差????!!!Whathappened?!注意此公式精确成立考察第n步的误差我们有责任改变。造成这种情况的是不稳定的算法/*unstablealgori

5、thm*/迅速积累，误差呈递增走势可见初始的小扰动公式二：注意此公式与公式一在理论上等价。方法：先估计一个IN,再反推要求的In(n<

6、ctorial(intn){inti,result;result=1;if(n>0){for(i=1;i<=n;i++)result=result*i;}/*endif*/returnresult;}intfactorial(intn){if(n>0)returnn*factorial(n1);elsereturn1;}例:斐波那契(Fibonacci)序列：F0=F1=1Fi=Fi-1+Fi-2（i>1)算法求斐波那契数intF(n){//返回第n个斐波那契数//intn;if(n<=1)return(1);elsereturnF(n

7、-1)+F(n-2);}算法效率：对F(n-1)、F(n-2)存在大量的重复计算改进：保存中间结果例:欧几里得算法已知两个非负整数a和b，且a＞b≥0，求这两个数的最大公因数。辗转相除法：若b=0，则a和b的最大公因数等于a；若b＞0，则a和b的最大公因数等于b和用b除a的余数的最大公因数。算法求最大公因数GCD(inta,intb)//约定a>b//{if(b==0)return(a);elsereturn(GCD(b,a%b));}例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;递归特点：结构清晰，可

8、读性强，容易用数学归纳法证明算法正确性适用范围：难以用循环或递推直观描述的复杂问题缺点：资源耗费多，执行效率低，所以在算法优化时采用消递归策略算法设计基本方法（5）减半递推技术（分治法）所谓“