JavaScript で競技プログラミングでよくあるアルゴリズムを実装してみた。

最近、アルゴリズムを勉強しています。アルゴリズムを本などで勉強すると、 C言語や Java などの言語で解説されていることが多いのですが、これを JavaScript で実装するとどうなるのだろうと思ったため、いくつかのアルゴリズムを JavaScript で実装してみました。この記事では実装したプログラムをメモ書きレベルで書き殴っていきます。

素数判定

const isPrime = (n) => {
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

約数を列挙する

const getDivisors = (n) => {
    let divisors = []
    for (let i = 0; i <= Math.sqrt(n); i++) {
        if (n % i !== 0) continue;
        divisors.push(i);
        if (i !== n / i) {
            divisors.push(n / i)
        }
    }
    return divisors;
}

flatMap を使用して約数を列挙する

const range = (start, stop, step) =>
  Array.from({ length: (stop - start) / step + 1 }, (_, i) => start + i * step);

const getDivisors = (n) => range(1, Math.sqrt(n), 1).flatMap((i) => {
  if (n % i !== 0) {
    return [];
  }
  if (i !== n / i) {
    return [i, n / i];
  }
  return [i];
});

console.log(getDivisors(286).sort((a, b) => a -b)); //結果: (8) [1, 2, 11, 13, 22, 26, 143, 286]

最大公約数を求める（ユークリッドの互除法）

function GCD (A, B) {
  while (A >= 1 && B >= 1) {
    if (A < B) {
      B = B  % A;
    } else {
     	A = A % B;
    }
  }
  
  return A >= 1 ? A : B;
}

再帰関数をつかったユークリッドの互除法

function GCD (A, B) {
  if (B === 0) return A;
	return GCD(B, A % B);
}

最小公倍数を求める

function LCM (A, B) {
  return Math.floor(A / GCD(A, B)) * B;  
}

n個のモノからr個を選ぶ方法の数を求める（二項定理）

function binomialTheorem (n, r) { 
  let fact_n = 1, fact_r = 1, fact_nr = 1;
  for (let i = 1; i <= n; i++) fact_n *= i;
  for (let i = 1; i <= r; i++) fact_r *= i;
  for (let i = 1; i <= n - r; i++) fact_nr *= i;
  
  return fact_n / (fact_r * fact_nr);
}

階乗

function factorial(n) {
	if (n === 1) return 1;
	return factorial(n - 1) * n
}

累積和

function prefixSum(...nums) {
  return [0, ...nums.map((sum => value => sum += value)(0))]
}

繰り返し2乗法

function modpow(a, b, m) {
  // 繰り返し二乗法（p は a^1, a^2, a^4, a^8, ... といった値をとる）
  let p = a, 
      answer = 1;
  
  for (let i = 0; i < 30; i++) {
    if ((b & (1 << i)) != 0) {
      answer = (answer * p) % m;
    }
    p = (p * p) % m;
  }
  return answer; 
}

a ÷ b (mod m)

function division (a, b, m) {
  // division(a, b, m) は a÷b mod m を返す関数
  return (a * modpow(b, m - 2, m)) % m; 
}

まとめ

短いですが今回の記事はこれで終わりです。アルゴリズムの勉強は難しくて大変でしたが、わかったときの爽快感がすごいのでまたコツコツ趣味程度にやっていきたいなと思いました。また、他のアルゴリズムについても実装でき次第追記していきます。ただ、JavaScript だと組み込みの number 型で表せる数値に限界があり、Bigint 型を使用しないとうまく実装できないといったことが多々ありまして、アルゴリズムの勉強や競技プログラミングをやる際は、C言語や Java などをつかったほうが変なところで躓かなくて済むなという印象です。