

首页  思维导图  详情



算法

2021-05-10 16:01:38   24  举报





AI智能生成

算法

模版推荐

作者其他创作

大纲/内容

算法

动态规划

贪心

迭代

介绍

称辗转法，是一种不断用变量的旧值递推出新值的解决问题的方法，迭代算法一般用于数值计算。累加，累乘都是迭代算法的基础应用。

迭代过程是通过小规模问题的解逐步求解大规模问题的解，表面上看正好与递归相反，但也找到了大规模问题与小规模问题的关系。

分类

精确迭代

近似迭代

步骤

1）确定迭代模型

根据问题描述，分析出前一个（或几个）值与下一个值的迭代关系数学模型。

2）建立迭代关系式

递推数学模型一般是带下标的字母，算法设计中要将其转化为“循环不变式”----迭代关系式，迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量。

3）对迭代过程进行控制。

① 所需的迭代次数是个确定的值，可以计算出来，可以构建一个固定次数的循环来实现对迭代过程的控制；

② 所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件。

示例

计算n的阶乘

解决

青蛙跳级问题

解决

斐波那契数列

解决

递归（20210510）

介绍

程序自身调用自身的编程技巧称为递归（ recursion）

分类

直接递归

函数在执行过程中调用本身

间接递归

函数在执行过程中调用其它函数再经过这些函数调用本身

四个特性

1.必须有可最终达到的终止条件，否则程序将陷入无穷循环；

2.子问题在规模上比原问题小，或更接近终止条件；

3.子问题可通过再次递归调用求解或因满足终止条件而直接求解；

4.子问题的解应能组合为整个问题的解。

优点

将大问题分解成小问题，将复杂的问题简单化；

使程序更易于理解，增强可读性；

实战演练四部曲

先定义一个函数，明确这个函数的功能，由于递归的特点是问题和子问题都会调用函数自身，所以这个函数的功能一旦确定了，之后只要找寻问题与子问题的递归关系即  可

接下来寻找问题与子问题间的关系（即递推公式），这样由于问题与子问题具有相同解决思路，只要子问题调用步骤 1 定义好的函数，问题即可解决。所谓的关系最好能用一个公式表示出来，比如 f(n) = n * f(n-) 这样，如果暂时无法得出明确的公式，用伪代码表示也是可以的, 发现递推关系后，要寻找最终不可再分解的子问题的解，即（临界条件），确保子问题不会无限分解下去。由于第一步我们已经定义了这个函数的功能，所以当问题拆分成子问题时，子问题可以调用步骤 1 定义的函数，符合递归的条件（函数里调用自身）

将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中

最后也是很关键的一步，根据问题与子问题的关系，推导出时间复杂度,如果发现递归时间复杂度不可接受，则需转换思路对其进行改造，看下是否有更靠谱的解法

示例

计算n的阶乘

解决

青蛙跳级问题

解决

斐波那契数列

解决

分治