C++ 归纳算法

zltzlt

归纳算法

归纳算法的思想是通过列举少量的特殊情况，经过分析，最后找出一般性的规律或关系。

从本质上讲，归纳算法就是观察一下简单而特殊的情况，最后总结出有用的结论或解决问题的有效途径。

归纳算法举例

求汉诺塔移动次数。

输入：一个整数 n（不超过 50），表示汉诺塔层数。
输出：一个整数 s（不超过 long long 范围），表示需要移动的次数。

汉诺塔问题如果按照传统的递归的方式进行处理，递归时运行一次计一次数，那就很容易因为数目巨大而超时了。

怎么办？找规律。

如果 n = 1，s = 1；
如果 n = 2，s = 3；
如果 n = 3，s = 7；
如果 n = 4，s = 15；
如果 n = 5，s = 31；
……
规律：s = 2ⁿ - 1

所以写出如下程序：

// 求汉诺塔移动次数

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    long long n;
    cin >> n;
    cout << (long long)(pow(2, n)) - 1;
    return 0;
}

运行结果：

49
562949953421311

归纳算法总结

归纳算法从问题的简单具体状态入手，目的是去寻求可以推广的一般性规律，因此应考虑简单状态与一般状态间的联系。

从简单状态中分析出来的规律特征应能够被验证是正确的，不能想当然或任意地提出猜想，否则归纳出来的结论是错误的，必然导致整个问题的解是错解。