江苏龙网

  1. 主页 > 生活百科 > >

九大经典算法思想及其典型应用( 二 )

算法


3.2 算法中解决问题的步骤是明确且有限的；
3.3 计算机不靠直觉而是机械地解决问题（就是简单傻瓜式地一步一步做）；
3.4 了解并应用典型算法；
3.5 利用计算机的处理速度；无论是多么冗长繁琐的步骤，只要明确并且机械就是优秀的算法；
3.6 使用编程技巧提升程序执行速度；也就是说解决问题的方法是可以优化的，就像做事有方法，效率就会高一样，算法也是可以优化的；
3.7 找出数字间的规律；因为在计算机中所有的信息都可以用数字表示，因此构造算法，就可以利用到存在于数字间的规律 。规律+逻辑；
3.8 先在纸上考虑算法；也就是先在纸上把步骤用文字或图形表示出来，用简单的数字先做验证；
4 九种基本算法思想简述4.1枚举法Enumeration method
枚举算法思想的最大特点是，在面对任何问题时它会去尝试每一种解决方法 。在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这个结论是可靠的，这种归纳方法叫作枚举法 。
枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的 。在C语言中，枚举算法一般使用while循环实现 。使用枚举算法解题的基本思路如下 。
① 确定枚举对象、枚举范围和判定条件 。
② 逐一列举可能的解，验证每个解是否是问题的解 。
枚举算法一般按照如下3 个步骤进行 。
① 题解的可能范围，不能遗漏任何一个真正解，也要避免有重复 。
② 判断是否是真正解的方法 。
③ 使可能解的范围降至最小，以便提高解决问题的效率 。
 
4.2迭代法Iteration method
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程 。与迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题 。迭代法又分为精确迭代和近似迭代 。“二分法”和“牛顿迭代法”属于近似迭代法，功能都比较类似 。
迭代算法是用计算机解决问题的一种基本方法 。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值 。
在使用迭代算法解决问题时，需要做好如下3 个方面的工作 。
（1）确定迭代变量
在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量 。
（2）建立迭代关系式
迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系 。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键 。
（3）对迭代过程进行控制
在编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去 。通常可分为如下两种情况来控制迭代过程：
① 所需的迭代次数是个确定的值，可以计算出来，可以构建一个固定次数的循环来实现对迭代过程的控制；
② 所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件 。
4.3递推法Recurrence method
与枚举算法思想相比，递推算法能够通过已知的某个条件，利用特定的关系得出中间推论，然后逐步递推，直到得到结果为止 。由此可见，递推算法要比枚举算法聪明，它不会尝试每种可能的方案 。
递推算法可以不断利用已有的信息推导出新的东西，在日常应用中有如下两种递推算法 。
① 顺推法：从已知条件出发，逐步推算出要解决问题的方法 。例如斐波那契数列就可以通过顺推法不断递推算出新的数据 。
② 逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程 。
 
4.4递归法Recursion method
因为递归算法思想往往用函数的形式来体现，所以递归算法需要预先编写功能函数 。这些函数是独立的功能，能够实现解决某个问题的具体功能，当需要时直接调用这个函数即可 。
在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解 。递归算法有如下3 个特点 。
① 递归过程一般通过函数或子过程来实现 。
② 递归算法在函数或子过程的内部，直接或者间接地调用自己的算法 。
③ 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解 。


推荐阅读


上一篇：无语了，直到今天，我才揪出MySQL磁盘消耗迅猛的“真凶”

下一篇：Mac用什么音乐播放器好？