算法

算法

动态规划

贪心

迭代

介绍

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

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

分类

精确迭代

近似迭代

步骤

1）确定迭代模型

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

2）建立迭代关系式

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

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

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

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

示例

计算n的阶乘

解决

青蛙跳级问题

斐波那契数列

递归（20210510）

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

直接递归

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

间接递归

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

四个特性

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

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

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

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

优点

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

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

实战演练四部曲

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

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

分治