さえめろ の めも🐰

さえめろの備忘録です。twitter : @sae_mero_

プロジェクトオイラー #1~#5


JSで挑むプロジェクトオイラー





#1「3と5の倍数」

10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.
同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.

process.stdin.resume();
process.stdin.setEncoding('utf8');
 
var total =0;
for(var i = 0; i<1000; i++){
  if(i % 3 === 0 || i % 5 === 0){
     total += i;
  }
}
  console.log(total);

素直なやり方。解答:233168(反転)



#2「偶数のフィボナッチ数」
フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

process.stdin.resume();
process.stdin.setEncoding('utf8');

function fib(i) {
  return (function(i) {
    if(i === 0) return [0, 1];
    return (function(a){ 
        return [a[1], a[1] + a[0]]
    })(arguments.callee(i-1));
  })(i)[0]
}

function aaa() {
    var x = 0;
    for (var i = 1; i<1000; i++) {
          var f = fib(i);
          if (f > 4000000){
              break;
          }
     // 偶数判定
          if (f % 2 === 0){
            x += f;
          }
    }
      return x;
  }
  console.log(aaa());

arguments.calleeは無名関数の再帰呼び出しに使用する
(calleeどころかarguments自体が非推奨なんだって)
あまりに苦しすぎるので今度自分でもうちょっと考えます。解答:4613732(反転)



#3「最大の素因数」
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.

process.stdin.resume();
process.stdin.setEncoding('utf8');

var x = 2;

function soinnsuu(a){
    while(a !== x) {
        if(a % x === 0){
            a = a / x;
            x = 2;
        }else{
            x++;
        }
    }
}
soinnsuu(600851475143);
console.log(x);

割とらくちん。解答:6857(反転)



#4「最大の回文積」
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.

process.stdin.resume();
process.stdin.setEncoding('utf8');

var x = 0;
var max = 0;
// 3桁の積なので1000*1000で回す
for(var i = 1000; i > 0; i--){
    for(var j = i; j>0; j--){
        x =  i * j;
        var s = x.toString();
    // 配列に入れて反転させてもう一度文字列に戻す(=文字列を反転させる)
        var sr = s.split("").reverse().join("");
        if(s === sr ){
            if(x >= max){
                max = x;
            }
        }
    }
}
console.log(max);

回文の判定は今後も使いそうな予感がしますが、取り敢えずはこのやり方で。
JSの配列操作なのでいつかTimeoutする日が来るのかな~やだな~~。解答:906609(反転)



#5「最小の倍数」
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

process.stdin.resume();
process.stdin.setEncoding('utf8');

// 最大公約数を求める関数
function gcd(a,b){
    if(a === b){
        return a;
    }
    var r;
    while(b !== 0){
        r  = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 最小公倍数を求める関数
function lcm(a,b){
    return a * b / gcd(a,b); //公式
}

var total = 1;
for(var i=2; i <= 20; i++){
    total = lcm(i, total);
}

console.log(total);


手で計算したほうが絶対に早い。
自然数の最大公約数を求めるにはユークリッドの互除法を使用する。解答:232792560(反転)




プロジェクトオイラー死ぬほど楽しいです。
定理・数学手法などの根本的見直しが必要だな~と思いました。
あとこういう問題解決におけるJSの限界が意外と近い。精進します。