アルゴリズムの勉強(7)

円周率

相加相乗平均を使ったアルゴリズムで実装。 相加相乗平均がなんだかわからない人はヨビノリの動画をみたらいいよ。スルッと理解できちゃうから。


「相加相乗平均の関係」を視覚的に理解する!

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

let a = 1;
let b = 1 / Math.sqrt(2.0);

// s = 分母
// k=0 のときの計算結果がここには含まれている
// 2じゃなくて1だよ
let s = 1;

// t = 分母にでてくる2^kの係数
let t = 4;

for (let k = 1; k <= 3; k++) { // パラメータ(ak, bk)の計算
  let prev_a = a;
  // パラメータ(ak, bk)の計算
  a = (a + b) / 2;
  b = Math.sqrt(prev_a * b);

  // 分母の計算
  s -= t * (a - prev_a) * (a - prev_a);
  t *= 2;

  // 式全体の計算
  // 分子の計算で2を掛けてないのは a k+1 を計算した結果 1/2が出てきてて、
  // それは分子側に押し付けてるから
  let pi = (a + b) * (a + b) / s;

  console.log(pi);
}

実行結果

$ tsc pi.ts && node pi.js
3.1405792505221686
3.141592646213543
3.141592653589794

所感

書籍に載っているコードと式が異なっているので、tやsの変数の初期値をみたとき 「?」ってなってしまった。 落ち着いて理解すればなんのことはないので、理解できてすっきり。

検算のために電卓アプリを購入してしまった。

書籍を前から順にできるやつだけやっていくという方針だったけど、他の項目を前提にしてコードが書かれている部分があるので苦しくなってきた。 今後は興味の赴くままに気になったやつを見ていくことにする。

アルゴリズムの勉強(6)

エジプトの分数

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

// フィボナッチの貪欲アルゴリズム(再帰)
function frac(m: number, n: number) {
  const q_plus1 = Math.floor(n / m) + 1;
  if (n % m == 0) {
    return ("1/" + n/m);
  } else {
    const m_prime = m * q_plus1 - n;
    const n_prime = n * q_plus1;
    return ("1/" + q_plus1 + ' + ' + frac(m_prime, n_prime));
  }
}

// m = 分子, n = 分母
let m = 2;
let n = 5;
console.log(m + "/" + n + " = " + frac(m, n));

実行結果

$ tsc egypfrac.ts && node egypfrac.js
2/5 = 1/3 + 1/15

所感

リンド・パピルスの話が出てきて興味をそそられる。 古代エジプト数学に関する書籍は出版されているので、いずれ読みたい。

今回のコードはアルゴリズム事典に載っているループ式ではなく再帰的な形にした。 載ってるコードをそのまま引き写すだけだと頭に残らなかったので、少し実装を工夫するようにしてみた。

アルゴリズムの勉強(5)

異性体の問題

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

const C = 17;
const L = 2558;
let size = Array(L);
let _length = Array(L);
let count = Array(C + 1);
for (let i = 0; i < L; ++i) { size[i] = 0; }
for (let i = 0; i < L; ++i) { _length[i] = 0; }
for (let i = 0; i < C+1; ++i) { count[i] = 0; }

let i, j, k, h, len, n, si, sj, sk, sh;

n = size[0] = _length[0] = 0;
for (i = 0; i < L; ++i) {
  len = _length[i] + 1; if (len > C / 2) break;
  si = size[i] + 1; if (si + len > C) continue;
  for (j = 0; j <= i; ++j) {
    sj = si + size[j]; if (sj + len > C) continue;
    for (k = 0; k <= j; ++k) {
      sk = sj + size[k]; if (sk + len > C) continue;
      if (++n >= L) { console.log("failed"); }
      size[n] = sk; _length[n] = len;
    }
  }
}
if (len <= C / 2) { console.log("failed"); }
for (i = 0; i <= n; i++) {
  si = size[i];
  for (j = 0; j <= i; j++) {
    if (_length[i] != _length[j]) continue;
    sj = si + size[j]; if (sj > C) continue;
    count[sj]++;
    for (k = 0; k <= j; ++k) {
      sk = sj + size[k] + 1; if (sk > C) continue;
      for (h = 0; h <= k; ++h) {
        sh = sk + size[h];
        if (sh <= C) { count[sh]++; }
      }
    }
  }
}
for (i = 1; i <= C; i++) {
  console.log("炭素原子が", i, "個のものは", count[i], "種類");
}

実行結果

$ tsc isomer.ts && node isomer.js 
炭素原子が 1 個のものは 1 種類
炭素原子が 2 個のものは 1 種類
炭素原子が 3 個のものは 1 種類
炭素原子が 4 個のものは 2 種類
炭素原子が 5 個のものは 3 種類
炭素原子が 6 個のものは 5 種類
炭素原子が 7 個のものは 9 種類
炭素原子が 8 個のものは 18 種類
炭素原子が 9 個のものは 35 種類
炭素原子が 10 個のものは 75 種類
炭素原子が 11 個のものは 159 種類
炭素原子が 12 個のものは 355 種類
炭素原子が 13 個のものは 802 種類
炭素原子が 14 個のものは 1858 種類
炭素原子が 15 個のものは 4347 種類
炭素原子が 16 個のものは 10359 種類
炭素原子が 17 個のものは 24894 種類

所感

ループが3重だったり4重だったりして、計算量が多め。 コードを写経していてクラスが使いたくなった逸品。

別の言語で写すと無理がでるので、そういうアルゴリズムはスキップ。

アルゴリズムの勉強(4)

安定な結婚の問題

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

// 準備
let boy = [0, 0, 0, 0];
let girl = [[0, 0, 0, 0],
            [0, 1, 3, 2],
            [0, 2, 3, 1],
            [0, 3, 1, 2]];
let position = [0, 0, 0, 0];
let rank = [[0, 0, 0, 0],
            [4, 3, 1, 2],
            [4, 2, 1, 3],
            [4, 3, 2, 1]];

// 本題
for (let b = 1; b <= 3; b++) {
  let s = b;
  while (s != 0) {
    let g = girl[s][++position[s]];
    if (rank[g][s] < rank[g][boy[g]]) {
      let t = boy[g];
      boy[g] = s;
      s = t;
    }
  }
}

// 結果表示
for (let g = 1; g <= 3; g++) {
  console.log("女 ", g, " - 男 ", boy[g]);
}

実行結果

$ tsc marriage.ts && node marriage.js 
女  1  - 男  12  - 男  23  - 男  3

所感

アルゴリズムは大したことないけど、コードがわかりにくいなぁという印象。 配列に未使用な要素やターミネータが必要で、データを作りにくかったかな。C言語のコードがベースなので仕方がないといえば仕方がない。 本という制約からくるのだと思うけど、一文字変数名などもわかりにくさの原因かなぁと思った。 仕事してたらあまり書かない(vとかeとか、絶対に意味がわかるでしょ的なのは別だけど)なぁ。

アルゴリズムの勉強(3)

暗号

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

// 線形合同法
//  cryptのコードが線形合同法のrandを使う前提のように見えたので実装
//  TypeScript(というかjavascriptのrandがどうなのかは調べてない)
//  線形合同法を知らない場合はwikipediaなんかで調べればOK
namespace LCG {
  const PARAM_A: number = 1664525;
  const PARAM_C: number = 1013904223;
  const PARAM_M: number = 2147483647;
  let x: number = 1; // default value
  
  export const RAND_MAX: number = 2147483647;

  export function srand(value: number) {
    x = value;
  }
  
  export function rand() {
    x = (x * PARAM_A + PARAM_C) & PARAM_M;
    return x;
  }
};

// 本題はここから

// 文字と文字コードの扱いがC言語と異なるため、暗号化関数と復号関数を別々に用意した
// LCG.srand()の引数が暗号化・復号で共通する「鍵」となっている
// ロジックは暗号化・復号どちらの関数も基本的に同じ
// 文字の扱いと、表示したときのわかりやすさからスペースを挟む・挟まないという違いをつけた

function encrypt(plaintext: string) {
  LCG.srand(12345);

  let cipherletter_array = plaintext.split('').map((c) => {
    let n: number = c.charCodeAt(0);
    let r: number;
    do {
      r = LCG.rand() / ((LCG.RAND_MAX + 1) / 256);
    } while (r >= 256);
    return n ^ r;
  })
  return cipherletter_array.join(' ');
}

function decrypt(ciphertext: string) {
  LCG.srand(12345);

  let plainletter_array = ciphertext.split(' ').map((d) => {
    let n: number = parseInt(d);
    let r: number;
    do {
      r = LCG.rand() / ((LCG.RAND_MAX + 1) / 256);
    } while (r >= 256);
    return String.fromCharCode(n ^ r);
  })
  return plainletter_array.join('');
}

const targettext = "Hello, World!";
console.log("検証テキスト: ", targettext);

const ciphertext = encrypt(targettext);
console.log("暗号化されたテキスト: ", ciphertext);

const plaintext = decrypt(ciphertext);
console.log("復号されたテキスト: ", plaintext);

実行結果

$ tsc crypt.ts && node crypt.js
検証テキスト:  Hello, World!
暗号化されたテキスト:  66 109 122 41 190 21 221 79 94 227 120 24 207
復号されたテキスト:  Hello, World!

所感

線形合同法のコードを久しぶりに書いた。RAND_MAXの値っていくつだっけ?ってちょっと考えてしまったが、式( x = (x * PARAM_A + PARAM_C) & PARAM_M )を見れば一髪でわかるじゃん、ってなった。

本家は encrypt, decryptが一つの関数なのでキレイだけど、文字の扱いの違いをうまく吸収できず二つにわけてしまった。 共通ロジックを抜き出しても良かったが、まぁいいかな。という気持ち。

アルゴリズムの勉強(2)

誤り検出符号

Luhn(ルーン)のアルゴリズム

クレジットカードの番号の誤り検出を行うのに使われているらしい。

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

const card_number: string  = "1234567890123456";
let w: number = 1;
let t: number = 0;
let d: number = 0;

for (let i: number = card_number.length - 1; i >= 0; i--) {
  d = w * parseInt(card_number.charAt(i));
  if (d > 9) {
    d -= 9;
  }
  t += d;
  w = 3 - w;
}

if (t % 10 == 0) {
  console.log("有効");
} else {
  console.log("無効");
}

実行結果

$ tsc luhn.ts && node luhn.js
無効

所感

実際に使われているらしいアルゴリズム。上の実行結果では 無効 と表示されているが、それは実装1行目の card_number がダミーであるため。自分のカード番号を入れたらちゃんと 有効 と表示されたので、「お〜〜」って声が出てしまった。

こういうの楽しい。

アルゴリズムの勉強(1)

値の交換

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

let a: number = 1;
let b: number = 2;

console.log("a = ", a, ", b = ", b);

console.log("swap");
let t = a;
a = b;
b = t;

console.log("a = ", a, ", b = ", b);

実行結果

$ tsc swap.ts && node swap.js
a =  1 , b =  2
swap
a =  2 , b =  1

所感

なんのことはない処理。さらっと実装。