1
1
常用算法设计(1)
孙甲松
清华大学电子工程系
sun@thsp.ee.tsinghua.edu.cn
2007.9.
2
1. 概述
算法是为解决某个问题的而设计的计算或者操作
的步骤和方法。有了算法,才可以编写程序
即使某人对某种计算机语言(C/C++语言)非
常熟悉,如果自己不会根据要解决的问题设计算
法,也不可能编写出程序解决相应的问题
对于只是简单叙述的问题,能自己想出合适的算
法来解决。比如,请编写程序给出从n个数中取k
个的全部解
对于给出的问题,不但要能设计出算法,而且要
能设计出简单易行的优秀算法
3
1. 概述(续1)
解决同一个问题不同的人(甚至同一个人)可能会
写出几种不同的算法。
但算法有优劣之分,往往差距很大。往往有这样的
情况:同样一个问题,根据一种算法编写的程序可
能需要几天甚至几个星期才能得到最终的解;而根
据另一个好的算法编写的程序可能只需要几小时甚
至几分钟就能得到同样的解。
追求的最优算法当然应该是计算次数最少、所需存
储空间最小的。
但这两者往往不可兼得。在解决实际问题时,经常
需要“以时间换空间”或“以空间换时间”的情况,这跟
所用的计算机的内存和速度有关,需要折中考虑。
4
1. 概述(续2)
虽然设计算法,尤其是设计出好的算法是一
件非常困难的工作,但是设计算法也不是没
有方法可循。
人们经过几十年来的工作,总结和积累了许
多行之有效的方法,了解和掌握这些方法会
给我们解决问题提供一些思路。
经常采用的算法设计技术主要有:
迭代法、穷举搜索法、递推法、递归法、
贪婪法、回溯法、分治法、动态规划法
等
5
2. 迭代法
内容要点
(1)迭代法是用来解决数值计算问题中的非
线形方程(组)求解或最优解的一种算法设
计方法,是许多方法的总称,包括了简单迭
代法、对分法、梯度法、牛顿法等。
(2)其主要思想是:从某个点出发,通过某
种方式求出下一个点,此点应该离要求解的
点(方程的解)更近一步,当两者之差接近
到可以接受的精度范围时,就认为找到了问
题的解。但问题的关键是要保证其收敛性
6
2. 迭代法(续1)
学习难点
简单迭代法将方程(组)f(x)=0变换成x=g(x)再迭代
求解的方法简单易懂。但此方法的缺点是:
(a)每次只能求出方程的一个解,而且需要人工先给
出方程解的近似初值,若初值选不好,经常会得不到解。
因此程序中应该加入一个迭代次数计数器,当到一定的
次数后,就认为找不到解,不再循环迭代下去,防止
“死循环”;
(b)在变换成x=g(x)格式时,不易保证其收敛性,因
为有时收敛性并不易证明。
因此这种并不是解方程的最好方法。下面介绍对分法和
梯度法,前者可用来求出方程f(x)=0在区间[a,b]内的
全部单实根,后者可用来求解非线形方程组的实根。
评论0