kostumブログ

勉強したことやノート代わりのアウトプットに使っています。

project Euler 014

環境

問題

正の整数に以下の式で繰り返し生成する数列を定義する.

 n → n/2 (n が偶数)  n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる.

 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題) さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか. 注意: 数列の途中で100万以上になってもよい

考え方

  1. 始める数を設定する
  2. n が偶数の時は 1/2 する
  3. nが奇数の時は 3 倍して 1 を足す
  4. 2, 3 の数の結果を配列に追加していく。
  5. 計算終了後、4 の配列の長さを算出する
  6. 配列の長さを比較して、最長の場合は、連想配列にその時の配列の長さ、数を設定する
  7. 3 ~ 6 を、始める数から 1 まで繰り返す

コード

  let num = 1000000;
  let max = { arrayLength: 0, n: 0 };
  for (let i = num; i > 0; i--) {
    let n = i;
    let array = [i];
    while (n !== 2) {
      if (n % 2 == 0) {
        n = n / 2;
      }
      if (n % 2 == 1) {
        n = 3 * n + 1;
      }
      array.push(n);
    }
    if (max.arrayLength < array.length) {
      max.arrayLength = array.length;
      max.n = array[0];
    }
  }
  return max.n;

説明

  • 始める数、最長数列の変数を設定する
  • 始める数から 1 まで繰り返す
  • その中で、数列を入れる配列を設定し、n を計算する
  • n が偶数の時は、1/2 奇数の時は 3n+1 を計算する
  • 算出した n は配列に格納する
  • 最長数列の変数と配列の長さを比較し、配列の長さの方が大きい場合、最長数列の変数に上書きする