プログラマ脳を鍛える数学パズル

パズルを解くコードを、あなたは書けるか?
アルゴリズムがみるみるわかる! プログラミングってやっぱり面白い!

急速な技術の進歩、システム開発競争の激化…。プログラマを取り巻く環境はやさしいものではありません。でも、思い出してみてください。自分の書いたソースコードでプログラムが動くのを初めて見たとき。思い描いた通りのプログラムができたとき。プログラミングの楽しさを感じたことでしょう。何もないところからソースコードだけで新たな価値を生むプログラマは、非常に魅力的な職業です。

本書で登場する数学パズルは、そのようなワクワクにあふれています。「両替したときの硬貨の組み合わせはいくつ?」のような問題から、「国名でしりとりしたときに、一番長く続く順番は?」「運命の出会いは何通り?」というものまで、70 の問題を解くコードを、3 人のキャラクターたちと一緒に考えていきます。

パズルを解くうちにアルゴリズムが身につき、シンプルで高速なコードが書けるようになります。楽しみながらスキルアップもできて一石二鳥。さっそく挑戦してみましょう!

【本書に収録されている問題 (抜粋)】
Q01 10 進数で回文
Q03 カードを裏返せ
Q08 優秀な掃除ロボット
Q19 つりあわない男女
Q21 排他的論理和で作る三角形
Q33 百人一首の達人
Q45 素数のマトリックス
Q48 グレイコードのループ
Q53 いたずらされたお菓子
Q64 迷路で待ち合わせ

【本書に収録されている問題 (抜粋)】
Q01 10 進数で回文
Q02 数列の四則演算
Q03 カードを裏返せ
Q08 優秀な掃除ロボット
Q09 つりあわない男女
Q11 フィボナッチ数列
Q14 W 杯出場国しりとり
Q19 友達の友達は友達?
Q20 受難のファサードの魔方陣
Q21 排他的論理和で作る三角形
Q33 百人一首の達人
Q35 運命の出会いは何通り?
Q37 サイコロの反転
Q45 素数のマトリックス
Q48 グレイコードのループ
Q51 パーフェクトシャッフル
Q53 いたずらされたお菓子
Q55 横着なそろばん
Q58 最速の連絡網
Q64 迷路で待ち合わせ

『プログラマ脳を鍛える数学パズル』 (増井 敏克 著、翔泳社、2015 年 10 月刊) は、パズル 70 問を解くコードを考えながら、アルゴリズムの考え方と、シンプルで速いコードの書き方を身につける問題集です。副題は「シンプルで高速なコードが書けるようになる 70 問」です。版元の紹介によると、両替したときの硬貨の組み合わせの数や、国名でしりとりをした時に一番長く続く順番といった問題を、3 人のキャラクターと一緒に考えていく形をとります。解説には主に Ruby と JavaScript が使われていますが、版元は解説の中心が考え方であり、どの言語にも応用できると案内しています。

入門編から上級編まで、全 4 章 70 問の構成

本文は 4 章に分かれ、章題には入門編、初級編、中級編、上級編の名前と、難しさを示す星の印が添えられています。第 1 章は「10 進数で回文」「フィボナッチ数列」「W 杯出場国しりとり」など 15 問、第 2 章は「友達の友達は友達?」「受難のファサードの魔方陣」など 15 問、第 3 章は「最短経路の計算」「グレイコードのループ」「パーフェクトシャッフル」など 26 問、第 4 章は「あみだくじの横線」「迷路で待ち合わせ」「クロスワードパズルを作成せよ!」など 14 問です。どの章も問題の前に 1 つの項目が置かれており、第 1 章は 2 進数と 10 進数、第 2 章は費用対効果、第 3 章はオーダー記法と計算量、第 4 章はソースコードの個性を扱います。章題の言葉を追うと、プログラムで解く体験から始めて、アルゴリズムの効果を実感し、処理を速くする工夫へ、さらに視点を変えた高速化へと進む並びと読めます。

答えが出るコードと、速く答えが出るコード

パズルの多くは、すべての場合を順に試せば答えにたどり着けます。問題は、条件が少し大きくなるだけで試す数が爆発的に増えることです。並べ方や組み合わせを数える問題では、要素が 1 つ増えるたびに場合の数が何倍にもなり、素朴な書き方では待っても終わらないプログラムになります。そこで、同じ計算を繰り返していないか、対称性を使って探す範囲を半分にできないか、途中の結果を覚えておけないかを考えることになります。この見積もりの道具が 計算量 で、一度求めた結果を保存して使い回す メモ化 は、こうした工夫の代表的な形の 1 つです。本書が第 3 章の冒頭にオーダー記法の項目を置き、その章に最も多くの問題を集めているのは、この見積もりと工夫の往復を数多く繰り返させる構成と読めます。

パズルで手を動かしたいプログラマに向く理由

向いているのは、業務で書くコードとは別に、問題を分解して解き方を組み立てる練習をしたいプログラマです。題材は 1 問ごとに変わり、硬貨の組み合わせやしりとりのような身近な問題のほか、2 進数や排他的論理和、グレイコードのようなビット表現にまつわる問題も含まれます。ただし解説の言語は Ruby と JavaScript が中心なので、ほかの言語で書く人は読み替えながら進めることになります。時間制限の中で解く 競技プログラミング の対策を主目的にするなら、本書は問題に慣れる入口として位置づけ、定番の解法を体系的に並べた本と組み合わせるほうが効率的です。目的別の選び方は アルゴリズム本の選び方 で整理しています。

動くコードを書くだけで止まらず、同じ答えをもっと短く、もっと速く出す方法を考える習慣を付けたい人にとって、70 問を段階的に解き進められる本書は手元に置いて元が取れる 1 冊です。第 1 章の入門編から、まずは 1 問ずつコードを書いてみてください。