第四章    迭代法

前言

       简单的来说，算法就是用计算机程序代码来实现数学思想的一种方法。学习算法就是为了了解它们在计算机中如何演算，以及在当今的信息时代，它们是如何在各个层面上影响我们的日常生活的，从而提高我们的逻辑思维能力和处理实际问题的能力。善用算法、巧用算法，是培养程序设计逻辑的重中之重，许多实际的问题都可用多个可行的算法来解决， 但是要从中找出最优的解决算法却是一项挑战。

一、迭代法是什么？

1.简要介绍      

       迭代法指的是无法使用公式去一次性求解，而是需要使用重复结构循环来重复去执行一段程序代码去得到答案。

2.代码示例（简单理解）

       ①使用迭代法去直接计算10！

#include<iostream>
using namespace std;
void text()
{
  int sum = 1;
  for (int i = 1; i <= 10; i++)
  {
  sum *= i;
  }
  cout <<"10! = " << sum << endl;
}
int main()
{
  text();
}

        ②上述方法采用的是一种固定执行次数的迭代法，而当遇到一个无法一次用公式去求解，又不能要去确定将要执行多少次的情况，就需要去用到while循环。while循环必须去加入控制变量的起始值以及递增或递减的表达式，在编写该循环的过程中去检查离开循环体的条件是否存在。如果条件不存在，则会让循环去无限循环的执行下去。

#include<iostream>
using namespace std;
void text()
{
  cout << "请输入要计算的阶乘数：";
  int n; cin >> n;
  int sum=1,i=1;
  while (i <= n)
  {
  sum *= i;
  i++;
  } 
  cout <<n <<"! = " << sum << endl;
}
int main()
{
  text();
}

3.生活实例

       ① 按目前主流的生物进化论来说，生物的进化史，其实就很像一个迭代更新的过程。不同的生物在自己物种的基因下，经过长时间的生物变迁从而在基因和整体性状特征等等方面都会发生显著的变化。还有像在当今的互联网时代中，手机的更新过程就是一个迭代化的过程，通过这种迭代的方式对手机进行更新换代，从而不断地去完善技术突破并且满足不同用户群体的需求。

图片来源于百度百科

二、迭代法的典型案例——开平方&帕斯卡三角形

1.开平方

① 具体情况：

       在数学中，因为很多数的开平方都是无理数，所以我们需要借助数值计算的方式来进行近似值的求解。在数学中可以使用如下的迭代公式来求解a开平方的近似值：

迭代法求解开平方算法的操作步骤如下：

       1.选定一个迭代初值x0，将其带入上面的迭代公式中求解出x1

       2.计算x1-x0的绝对值，如果小于指定精度e，则退出迭代过程，否则继续迭代运算

       3.将x(n)带入上面的迭代公式，求解出x(n+1)。继续判断x(n+1)-x(n)的绝对值，如果小于指定精度e，则退出迭代过程，否则继续迭代运算......

② 代码展示（C++）：

       使用具体情况中的迭代公式法，去求解在精度0.000001下8的开平方值。

#include<iostream>
using namespace std;
class sqrtnum {
public:
  void sqrt()
  {
  double t=0;
  result = x;
  while (abs(result - t) > e)
  {
    t = result;
    result = 0.5 * (t + x / t);
  }
  cout << "结果为：" <<result << endl;
  }
  double e;  //精度
  double x;  //开平方数
  double result;   //迭代结果
};
void text()
{
  sqrtnum sn;
  cout << "请输入要开平方数：";
  cin >> sn.x;
  cout << "请输入开平方的精度数：";
  cin >> sn.e;
  sn.sqrt();
}
int main()
{
  text();
}

③结果展示：

2.帕斯卡三角形

① 具体情况

       帕斯卡三角形算法就是去计算出三角形每一个位置上的数值。在该三角上的每一个数字都各对应一个rCn，其中的r代表行，n代表列，它两都是从数字0开始。帕斯卡三角形如下：

使用以下公式去求解帕斯卡三角形中的对应值：

               rC0=1

               rCn=rCn-1*(r-n+1)/n

上面的两个式子代表的意义是每一行的第0列的数值一定是为1，例如上图所示，一旦每一行的第0列元素的值为数字1后，该行的每一列的元素值都可以从同一行前一列的值根据下面的公式计算得到：

               rCn=rCn-1*(r-n+1)/n

例如去求解3行的帕斯卡三角形的值，具体步骤：

               ①第0行帕斯卡三角的求值过程：当r=0，n=0时，即在第0行，第0列，对应的值为1；

               ②第1行帕斯卡三角的值求过程：当r=1，n=0时，即在第1行，第0列，对应的值为1；

当r=1，n=1时，即在第1行，第1列，对应的值为1C1=1C0*（1-1+1）/1=1；

               ③第2行帕斯卡三角的求值过程：当r=2，n=0时，即在第2行，第0列，对应的值为1；

当r=2，n=1时，即在第2行，第1列，对应的值为2C1=2C0*（2-1+1）/1=2；当r=2，n=2时，即在第2行，第二列，对应的值为2C2 =2C1*（2-2+1）/2；

② 代码展示（C++）：

       使用程序代码去展示10行的帕斯卡三角数值。

#include<iostream>
using namespace std;
class pascal {
public:
  void calculator()
  {
  int r=0, n;
  int column= 1;
  int result,record;
  while (column <= x)
  {
    int t = 1;
    n = 0;
    for (int i = 1; i <= column; i++)
    {
    if (i == 1) {
      result = 1;
    }
    else {
      result = t * (r - n + 1) / n;
      t = result;
    }
    n++;
    cout<<result<<" ";
    }
    cout << endl;
    r++;
    column++;
  }
  }
  int x;
};
void text()
{
  pascal psc;
  cout << "请输入要求解几行的帕斯卡三角数：" ;
  cin >> psc.x;
  psc.calculator();
}
int main()
{
  text();
}

③结果展示：

总结

       上面我们对迭代算法进行了细致的举例和经典代码的讲解。使用该算法时，要注意体会我们所要求的东西它在程序代码中的更新迭代过程，理解核心思想从而去更好的运用这种常用的经典算法解决常规问题。