G21|新汉诺塔题解——找规律公式法

G21|新汉诺塔题解——找规律公式法

——————看之前先点个赞吧，谢谢！——————

较详细题解

大概思路:

数一数，发现规律：

结果为：
g(n) = 2 · g(n-1) + f(n-1) + 2
其中f(n) = 2 · g(n-1)+1

综上，写出代码：

#include<bits/stdc++.h>
using namespace std;
//初始化1
int n, f[1005], g[1005];

int main(){
    //输入
    cin >> n;
    //初始化2
    f[0] = 1;
    g[0] = 2;
    //使用公式
    for (int i = 0; i < n; i++){
        f[i] = 2 * g[i - 1] + 1;
        g[i] = 2 * g[i - 1] + f[i - 1] + 2;
    }
    //输出
    cout << g[n - 1] << endl;
    return 0;
}

时间复杂度是

O(n)

解析：主体部分一层循环循环n次