Project_Euler-14 题解

题目

思路

从暴力枚举出发，枚举100万以内的所有数字，对于每一个数，维护一个长度，每根据公式执行一次运算就加一。

最后取最大值。

暴力枚举代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#define ll long long
#define MAX_N 1000000

ll get_lens(ll n) {
    ll ans = 1;
    while(n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = 3 * n + 1;
        }
        ans++;
    }
    return ans;
}

int main(int argc, int *argv[]) {
    ll n = MAX_N, ans = 0, num;
    for(ll i = 1; i <= n; i++) {
        ll len = get_lens(i);
        if (len < ans) continue;
        ans = len;
        num = i;
    }
    printf("ans = %lld, num = %lld\n", ans, num);
    return 0;
}

优化思路

观察下面的例子：

当 $i=8$ 时：

$$8\to 4\to 2\to 1$$

当 $i=32$ 时：

$$32\to 16\to 8\to 4\to 2\to 1$$

我们发现后半部分是重复计算的，因此可以在此进行优化。

可以使用记忆化，维护一个数组，在计算 $i$ 的时候，将其变换的项数记录下来，如果遇到之前计算过的，直接加上这个项数。

例如，我们维护一个数组keep，计算 $8$ 时，发现有 $4$ 项，因此可以让a[8] = 4
当计算 $32$ 时，运算到 $8$ 的时候，直接 $2+4=6$ 得出结果。

记忆化代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#define ll long long
#define MAX_N 1000000

ll keep[MAX_N + 5]; 

ll get_lens(ll n) {
    ll ans = 1, firn = n;
    while(n != 1) {
        if (n & 1) {
            n = 3 * n + 1;
        } else {
            n /= 2;
        }
        if (n < MAX_N && keep[n]) {
            keep[firn] = keep[n] + ans;
            return keep[n] + ans;
        }
        ans++;
    }
    keep[firn] = ans;
    return ans;
}

int main() {
    ll n = MAX_N, ans = 0, num;
    for(ll i = 1; i <= n; i++) {
        ll len = get_lens(i);
        if (len < ans) continue;
        ans = len;
        num = i;
    }
    printf("ans = %lld, num = %lld\n", ans, num);
    return 0;
}

优化比较

暴力代码：

记忆化代码：

快了 $17+$ 倍。