迭代算法的基本思想与例题

迭代

迭代法也称辗转法，是一种不断用变量的旧值推出新值的过程。

它是解决问题的一种基本方法，通过让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

迭代算法的基本思想是：为求一个问题的解x，可由给定的一个初值x0，根据某一迭代公式得到一个新的值x1，这个新值x1比初值x0更接近要求的值x；再以新值作为初值，即：x1→x0，重新按原来的方法求x1，重复这一过程直到|x1-x0|<ε(某一给定的精度)。此时可将x1作为问题的解x。

迭代算法解决问题，需要做好以下三个方面的工作：

1. 确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值推出新值的变量，这个变量就是迭代变量。

2. 建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键。

3. 对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

迭代也是用循环结构实现，只不过要重复的操作是不断从一个变量的旧值出发计算它的新值。其基本格式描述如下：

迭代变量赋初值
while (迭代终止条件){
  根据迭代表达式，由旧值计算出新值;
  新值取代旧值，为下一次迭代做准备;
}

例题1：

用迭代法求某个数的平方根。已知求平方根的迭代公式为：

$$ x_{1}= \frac{1}{2} \big(x_{0}+\frac{a}{x_{0}}\big) $$ C++实现：

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    double x0,x1,a;
    cin>>a;
    x0 =a/2;          // 迭代初值
    x1 =0.5*(x0 + a/x0);
    do{
       x0 = x1;  // 为下一次迭代作准备
       x1 = 0.5*(x0 + a/x0);
    } while (fabs(x1-x0)>0.000001);
    cout<<x1<<endl;       // 输出结果
    return 0 ;
}

例题2：

二叉树的中序遍历：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

输入：root = [1,null,2,3] //以前序给出
输出：[1,3,2]

C++实现：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};