Problem 14
- int で計算するとオーバーフローする。
- メモ化をしたいけど、上限値がわからない。そういう場合は、ある一定値までメモ化する、というように決めてしまえばよい。この問題では N = 1000000 までとする。
- ScalaでProject Euler(28) - 桃の天然水 がとても参考になりました。
F()
と Collatz()
の呼び出し方は、上記サイトを参考にしています。
using System;
public class PE014 {
static int N = 1000000;
static int[] memo = new int[N];
static int F(long n) {
if (n % 2 == 0) {
return 1 + Collatz(n / 2);
}
else {
return 1 + Collatz(3 * n + 1);
}
}
static int Collatz(long n) {
if (n < N && memo[n] > 0) return memo[n];
int chain = F(n);
if (n < N) memo[n] = chain;
return chain;
}
public static void Main() {
memo[1] = 1;
int maxChain = 0;
int ans = 0;
for (int i = 1; i < N; i++) {
int chain = Collatz(i);
if (maxChain < chain) {
maxChain = chain;
ans = i;
}
}
Console.WriteLine(ans + " " + maxChain);
}
}
- 最大値を求めるところ(for 文を回して、maxChain 変数を更新している箇所)は、Linq を使って綺麗に書けそうな感じがする。