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 1000000ll 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 1000000ll 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+$ 倍。