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

要約

副題は「シンプルで高速なコードが書けるようになる 70 問」

感想

コードのほとんどが Ruby で書かれている。Ruby を知らない人は、 これを機会に Ruby の文法に慣れるのがいいと思う。inject の使い方を覚えれば、 Ruby 通になれると思う。

Q01 の 10 進数で回文

Q01 は、10 進数で 11 以上の数で、2 進数でも、8 進数でも、10進数でも、回文になる数のなかで、 一番小さなものを求めよ、という問題である。せっかくなので、Haskell の処理も付け加えてみた。

その準備として、Haskell で使える処理を調べることにした。 本書の p.016 では、表２に各言語の進数変換の処理がまとめられている。 本書では、ある整数 n を２進数、８進数、１６進数の文字列表記に変換する処理を進数変換と呼んでいるが、 r 進数というときの r は、ふつう進数とは呼ばず基数(base)と呼ぶ。 この表に １０進数の場合と Haskell の処理を付け加えてみた。

注１：showIntAtBase 2 ("01"!!) n "" の形なら使える。 あるいはimport Data.Char (intToDigit) も合わせて読みこんで、 showIntAtBase 2 intToDigit n "" の形なら使える。

ghci で試行錯誤の上、醜いプログラムができた。\は次の行に続くことを表す：

> [x | x <- [11, 13 ..], (show x) == (reverse (show x)), \
	(showOct x "" ) == (reverse( showOct x	"")), \
	(showIntAtBase 2 intToDigit x "") == (reverse (showIntAtBase 2 intToDigit x "")) ]
[585Interrupted.

ここで Interrupted. は Ctrl-c キーボード入力をした結果出た表示である。 585 という数字が得られたところはいいが、あまりにも醜い。少し反省して次のプログラムを書いた。

> let oct x = showOct x ""
> let bin x = showIntAtBase 2 inToDigit x ""
> let dec x = show x
> let palindrome x = (x == reverse x)
> head [x|x <- [11, 13 ..], palindrome (dec x), palindrome (oct x), palindrome (bin x)]
585

私の力ではこれが精一杯である。

Q02 の数列の四則演算

Q 02 では文字列としての数式を計算するために、JavaScript でのコードが載っている。 これは eval を使っている。eval はセキュリティ上危険であるということは本書の p.020 でも書かれている。 ではどうすればいいのか。本書にその回答はない。そこまで求めるのは酷だろうか。

mozilla のページでは、JavaScript で eval を使わない方法として window.Function を使う方法が推奨されている。

Q12 の「平方根の数字」

このパズルの末尾に次の対話がある。

sub や split、uniq など、Ruby には便利なメソッドが多いですね。

こういう便利な言語を使うのもいいですが、できれば C 言語のような言語でも実装してみてほしいですね。

第１の発言には賛同する。便利なメソッドを多く用意することで、プログラミングを楽しめるようにする、 というのが Ruby という言語の長所だと思う。 これに対して、第２の発言はどういうことだろう。そのこころは C 言語のような不便な言語でも、 頭を絞って考えろ、ということだろうか。プログラミングは難行苦行ではあってはならないはずだ。 それでも、C 言語で考えることも無駄ではないだろう。私の解答を示す。 なお、問題を解くための実装に疑義がある（後述）ので、その疑義をただしたプログラムとなる。

/*  q12_02.c */

#include <math.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
    int i;
    int len;
    char str[4096];
    char *str10;
    char *str11;
    char fullset10[]="0123456789";
    char fullset11[]="0123456789.";
    
    i = 1;
    /* 整数部分も含む */
    while (i++) {
        /* 文字列表現。小数点以下は11桁（切捨て対応のため） */
       sprintf(str, "%11.11f", sqrt((double)i));
       /* 小数点を残して左から 11 文字を取得*/
       str[11] = '\0';
       str11 = str;
        /* str11 を構成する文字がすべて fullset11 の文字に含まれていれば終了 */
        len = strspn(fullset11, str11);
        if (len == 11) {
            break;
        }
    }
    printf("%d, %11.11f\n", i, sqrt((double)i));
    /* 整数部分を含まない */
    i = 1;
    while (i++) {
        /* 文字列表現。小数点以下は11桁（切捨て対応のため） */
       sprintf(str, "%11.11f", sqrt((double)i));
       /* 小数点で分割して小数部分のみを取得 */
       str10 = strchr(str, '.') + 1;
       /* 小数点以下 11 桁めは切捨て */
        str10[10] = '\0';
        /* str10 を構成する文字がすべて fullset10 の文字に含まれていれば終了 */
       len = strspn(fullset10, str10);
        if (len == 10) {
            break;
        }
    }
    printf("%d, %11.11f\n", i, sqrt((double)i));
        
    return 0;
}    

まず実装の疑義について述べる。本書の解法は、 浮動小数点数を小数点以下 10 桁までを求める書式を使って小数点以下 10 桁の文字に変換して、 その 10 桁の文字を使っている点である。これは、小数点以下の 10 桁目が、 11 桁めを四捨五入した数字に変換されているため、問題の意図を汲んだ解答でないと思う。 問題は p.055 によれば次の通りである。

平方根を小数で表したときに、0 ～ 9 までの数字が最も早くすべて現れる最小の整数を求めてください。 ただし、ここでは正の平方根のみを対象とします。 整数部分を含む場合と、小数部分のみの場合のそれぞれについて求めてください。

これを見ると、無限に続いている小数点を小数点第１位、小数点第２位、……の順に見ていく、 という解釈なので、小数点第 n 位に現われている数字はそのまま見るのが正しく、 その次の位を四捨五入して見る、というのではないはずだ。だから、小数点は切捨てで考えるのが正しい。

なおもう一つ考慮しないといけないのは、浮動小数点数を有限の桁数で表示するときに、 割り切れない値は四捨五入で表示されるのか、それとも切捨てで表示されるのか、 ということが言語の、あるいはライブラリの仕様を確認しなければならない。 私は C 言語の浮動小数点数の表示を確かめてはいないが、少なくとも私の使っている処理系では、 四捨五入した数字で表される。次は 2 の平方根の値を、有効数字を１つずつ増やしながら表示した結果である。 この結果の通り、小数点以下 6 桁と小数点以下 10 桁は、それぞれ下の位を切り上げた結果となっている。 他の桁の場合も併せて、この処理系の場合は四捨五入で表示すると考えられる。

 1: 1.4
 2: 1.41
 3: 1.414
 4: 1.4142
 5: 1.41421
 6: 1.414214
 7: 1.4142136
 8: 1.41421356
 9: 1.414213562
10: 1.4142135624
11: 1.41421356237

得られた結果は本書と変わりはなかったが、これは偶然だろう。アルゴリズムの訓練も大事だが、 仕様の確認もまた大事だというのが私のいいたいことである。

なお、C 言語での実装については次の通りである。 まず、整数部分を含む場合である。小数点を除去し、 左から10 文字を取得というのは C 言語の仕様上ムダが多いので、 小数点を残したまま左から　11 文字を取得した。 そしてこれらの11文字に 0 から 9 までとピリオドがすべて含まれていることの確認に、
strspn(const char *s1, const char *s2)
という C 言語の標準ライブラリを使っている。 この関数は、*s1 が指す文字列の中で、 *s2 が指す文字列中の指定文字群だけを含む先頭部分の最大の長さを計算する。 たとえば、s1="aaaououkkk", s2="aeiou" であれば、s1 に出てくる文字を先頭から見ていき、 母音でない文字が初めて出てくる箇所を調べる。s1[0]の文字は s2 に出てくる文字に含まれる、 s1[1]の文字は s2 に出てくる文字に含まれる、と調べて、s[8] が初めて母音でない文字が出てくるから、 この strspn は 8 を返す。

ここで普通、s2 に入れる文字は集合を文字列にするものだから重複はさせないだろうが、 別に重複してもかまわない。ここに目をつけて、調べるべき文字列を s2 に入れる。 一方で、すべてがそろった文字列　"0123456789." を s1 とすることで、 s2 になく s1 の文字列に存在する文字があれば、その文字が最初に出現する場所がわかる。 言い換えれば、すべての文字が s2 にあれば strspn の返す値は文字列の長さである 11 となる。 これを判断基準にすればよい。 これが、ruby の sub も split も uniq も使わないで済ませる一つの方法である。

なお、11 がマジックナンバーでわかりにくいという人がいるかもしれない。 その場合は、strspn の代わりに strcspn という関数を使う手がある。 この関数は、*s1 が指す文字列の中で、 *s2 が指す文字列中の指定文字群を含まない先頭部分の最大の長さを計算する。 これを使うと、*s2 に含まれる文字がすべて *s1 に出てくるとき、またそのときに限って、 この関数は 0 を返す。これを使ってもいいだろう。

整数部分を含まず、小数部分だけで判断する場合も考え方は全く同じである。 この場合は小数点を含まない箇所で切り出すので、比較すべき文字列も小数点を含まない、 というところだけが違う。

なお、厳密なことをいえば、整数を１から順にインクリメントさせてループをさせ、 所定の条件に合致したときにループから抜けるようにしているが、このループが停止するかどうかは、 小数点だけの場合はわからない （整数部分も含む場合は、i = 1023456789^2 であれば確実に停止する）。 だから、頑強なプログラムを作るには、ループの上限をある程度大きな数までで押さえることが必要となるだろう。

JavaScript の reduce について

Q50 では JavaScript のコード例で、reduce を使った例を示している。

function sum(a) {
    return a.reduce(function(x, y) {return x + y;});
}

本書では、３人の登場人物がいる。そのうちの「センセイ」が吹き出しで、 無名関数を使うと、モダン JavaScript のようでいいですね。 といっている。

ここで、x と y とある引数の名称が無造作で、わかりにくい。mozilla の例を参考に、 本書の例と変えたところがいくつかある。x と y の名称を mozilla の例に変えたほか、 初期値を 0 と明示したこと、そしてアロー関数の表記に変えたことである。

function sum(array) {
    return array.reduce((accumulator, currentValue )=> accumulator + currentValue); 
}

振り返って、モダン JavaScript とは何か、と問われると答に窮する。 ではモダン JavaScript の特徴は何か、一つはアロー関数であろう。 これが map や reduce と等と合わせてうまく使えるようになるのが一つの目標である。

実行速度の計測の前提と計測の方法

本書のいたるところで、処理時間の長さについて言及されている。相対的な時間はよいのだが、 本書で具体的に秒数を明示している箇所もある。たとえば、q07_72.c というプログラムの処理時間について、 p.306 で、 同じ処理ですが、C 言語に書き換えるだけで、1.5 秒まで短縮できました。 という具合だ。このとき、著者の環境がどのようなものであったかを知りたい。

念のため、私の環境ではどうだったか。NEC LaVie LS150/N 、Windows 10 Home 64bit、 Intel Celeron 1005M 1.90GHz 、メモリ 8GB である。 コンパイラには Windows 用の GCC （rubenvb-4.6.3 ）を用い、処理時間は次のように計測した；
> gcc -pg -o q70_02 -q70_02.c
> .\q70_02.exe > gprof .\q07_02.exe

この結果を５回測ったところ、1.24 秒、1.21 秒、1.25 秒、1.26 秒、1.32 秒だった。 本書の 1.5 秒とほぼ変わらないといっていいだろう。

Column について

関数型言語

p.032 で、「関数型言語で再帰を学ぼう」とある。わたしもこれには同意するが、 関数型言語を列挙するなかで最後に、Python を使う方法もあります、という文には違和感がある。 やはり、本文で順にあげた、LISP、Scheme、Haskell、Scala が順当だと思う。

プログラミング言語の選び方

本書では主に Ruby での解答が述べられている。 実際、問題のすべてに Ruby のコードによる解答が与えられている。 次に多いのが JavaScript のコードである。そしてわずかに C 言語でのコードもある。 おそらくこれら３種類であろう。というのも、p.006 でソースコードを動作確認したのが、 Ruby 2.2.3、JavaScript 1.8、C 言語 C99 (GCC) とあるからだ。 著者はこの Column で、Ruby と JavaScript を選んだ理由を述べている。 Ruby は便利なライブラリが揃っていて解説がしやすいという理由から、 そして JavaScript は読者の皆さんが環境を準備しやすいという理由から、だという。 一方、著者は、最低でも 2 つの言語で実装してみて、それぞれの言語の特徴をつかんでみてください、 と勧めて、このとき、タイプが異なる言語を選ぶことが重要ですと、付け加えている。 その伝でいけば、Haskell あたりで実装例を示すというのもありではないかと思う。

続編にもっとプログラマ脳を鍛える数学パズルがある。

書誌情報

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