増井　敏克：もっとプログラマ脳を鍛える数学パズル

作成日 : 2018-05-12
最終更新日 :

要約

副題は「アルゴリズムが脳にしみこむ７０問」。プログラマ脳を鍛える数学パズルの続編にあたる。 前著はプログラムのほとんどが Ruby で書かれていたが、 本書は Ruby のプログラムのほか JavaScript のプログラムも掲載されている。

感想

自分で問題を作る

自分で問題を作ってみるのがこの先いいのだろう。 たとえば、Q.12 「円周率に近似できる分数」では、小数第 n 位まで円周率と一致する分数のうち、 分母が最小のものを `π(n)` とするときの `π(n)` を求めている。すなわち、`π(1) = 19/6 = 3.166 cdots, π(2) = 22/7 = 3.1428cdots, π(3) = 245/78 = 3.14102cdots`である。 では `π(n)` の定義を「真の`π`の値との差が `1/10^n` 以内で円周率と一致する分数のうち分母が最小のもの」とするとどうなるだろうか。

オーダーを改善する

Q01 は、「一発で決まる多数決」である。`N` 人でじゃんけんをするとき、グーチョキパーの数を比べ、それらを比較するだけで、（すなわち、グーチョキパーの順序関係を使わずに） 比較多数となった場合に決定が完了すると定義する。このとき、じゃんけんをただ一度だけして決定するときのパターンが何通りあるかを求める、という問題である。 本書で紹介されている解法は `O(N^2)` であるが、amazon でのあるレビュアは `O(N)` の解法を見つけたという。 気になって探すと（私が独力で考えたのではないのが悔しいが）、 ange1のブログ「今週のお題：一発で決まる多数決」問題解答 ( CodeIQ ) (ange1.hateblo.jp) があり、 `O(1)` の解法が載せられていた。

グローバル変数をローカル変数に変更する

本書ではパズルを解くためにメモ化を多用している。たとえば、p.013 の問題に対してメモ化を取り入れ JavaScript でプログラムしたコード pre1_2.js を多少書き直して掲げる。 ただし、私のほうで、定数には const を明示し、かつ var は let に直し、また比較の == を === にするなど変更している。 

// pre1_2.js 
const M = 10;
const N = 100;
let memo = {};
function check(remain, pre) {
  // 一度計算したものがあれば、それを返す
  if (memo[[remain, pre]]) return memo[[remain, pre]];

  // 配置する人がいなくなると終了
  if (remain < 0) return 0; 
  if (remain === 0) return 1; 
  let cnt = 0; 
  for (let i=pre; i <= M; i++) { 
    cnt +=check(remain - i, i);
  } 
  // 計算結果をメモする 
  return memo[[remain, pre]]=cnt; 
} 
console.log(check(N, 2));

このメモ化の手法は強力だが、このコードのような memo をグローバル変数とするファイルが複数あり（たとえば js1.js, js2.js, js3.js）、 1 つの HTML ファイルがこれらの JavaScript ファイルを同時に読み込むと、 相互の memo 変数が衝突してしまい、目的とするプログラムが得られない。


<!DOCTYPE html>
<html>
  <head>...</head>
  <body>
    ...
    <script src="js1.js"></script>
    <script src="js2.js"></script>
    <script src="js3.js"></script>
  </body>
</html>

そこで、このグローバルスコープをブロックスコープに閉じ込めるために、クロージャを使う。クロージャを使うと次のように書き直せる。

function check(n, pre) {
  const M = 10;
  let memo = {};

  function _check(remain, pre) {
  // 一度計算したものがあれば、それを返す
    if (memo[[remain, pre]]) return memo[[remain, pre]];

  // 配置する人がいなくなると終了
    if (remain < 0) return 0; 
    if (remain===0) return 1; 
    let cnt=0; 
    for (let i=pre; i <= M; i++) {
      cnt += check(remain - i, i);
    } 
    // 計算結果をメモする 
    return memo[[remain, pre]]=cnt; 
  } 
  return _check(n, pre) 
} 
console.log(check(100, 2));

下請関数用の名前をもう一つ用意しないといけないのが難点だが、こうしておけばグローバル変数 memo が衝突する危険はない。 なお、他のグローバル変数のうち M はブロックスコープに閉じ込めている。 N は引数で渡したので表向きは消えている。

誤植

サポートページ(www.shoeisha.co.jp)からたどれる正誤表のほかは、次のとおりである。

p.113 上から 7 行目、（誤）移行すると、→（正）移項すると、

それから誤植ではないのだろうが、pp.143-144 にある q29_2.rb や q29_2.js にある階乗を求めるプログラムの名前が facorial となっている。 正しいスペリングは factorial だろう。他のページで階乗を求めるプログラムでは factorial が用いられている。

書誌情報

書名もっとプログラマ脳を鍛える数学パズル
著者増井敏克
発行日2018 年 2 月 19 日 (初版)
発行元翔泳社
定価2,580 円（本体）
サイズＡ５判 343 ページ
ISBN978-4-7981-5361-2
その他越谷市立図書館で借りて読む

まりんきょ学問所 ＞ コンピュータの部屋 ＞ クイズ・パズル ＞ 増井　敏克：もっとプログラマ脳を鍛える数学パズル

MARUYAMA Satosi