Project Euler 14

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 を使って綺麗に書けそうな感じがする。