1. ホーム >
  2. 書籍 >
  3. プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問


形式:
書籍
発売日:
ISBN:
9784798142456
価格:
本体2,580円+税
仕様:
A5・312ページ
分類:
開発技法

本書籍の他の形式を確認する

  • このエントリーをはてなブックマークに追加

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

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

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

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

【使用言語について】
本書の解説では、主にRubyとJavaScriptを使用していますが、解説内容は「考え方」が中心であるため、どんな言語にも応用できます。また、問題を解くために特定の言語が必要になることもありません。

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


はじめに
謝辞
本書の概要
登場人物紹介
ダウンロードファイルについて

第1章 入門編★ プログラムを作って問題を解いてみよう

2進数と10進数
Q01:10進数で回文
Q02:数列の四則演算
Q03:カードを裏返せ
Q04:棒の切り分け
Q05:いまだに現金払い?
Q06:(改造版)コラッツの予想
Q07:日付の2進数変換
Q08:優秀な掃除ロボット
Q09:つりあわない男女
Q10:ルーレットの最大値
Q11:フィボナッチ数列
Q12:平方根の数字
Q13:覆面算を満たすのは何通り?
Q14:W杯出場国しりとり
Q15:階段で立ち話

第2章 初級編★★ 簡単な問題を解いてアルゴリズムの効果を実感しよう

費用対効果を意識する
Q16:3本のひもで作る四角形
Q17:30人31脚に挑戦!
Q18:ショートケーキの日
Q19:友達の友達は友達?
Q20:受難のファサードの魔方陣
Q21:排他的論理和で作る三角形
Q22:絡まない糸電話
Q23:ブラックジャックで大儲け!?
Q24:完璧に撃ち抜くストラックアウト
Q25:オシャレな靴ひもの結び方
Q26:効率のよい立体駐車場
Q27:右折を禁止されても大丈夫?
Q28:クラブ活動への最適な配分
Q29:合成抵抗で作る黄金比
Q30:テーブルタップで作るタコ足配線

第3章 中級編★★★ アルゴリズムを工夫して高速な処理を実現しよう

オーダー記法と計算量
Q31:最短経路の計算
Q32:畳を敷きつめろ
Q33:百人一首の達人
Q34:飛車と角の利き
Q35:運命の出会いは何通り?
Q36:「0」と「7」の回文数
Q37:サイコロの反転
Q38:7セグメントコードの反転
Q39:「白」で埋めつくせ!
Q40:並べ替えの繰り返し
Q41:美しい?IPアドレス
Q42:1つの数字で作る1234
Q43:シャッフルで逆順
Q44:グラスの水を半分に
Q45:素数のマトリックス
Q46:ソートの交換回数の最少化
Q47:オンリーワンな○×
Q48:グレイコードのループ
Q49:反転で作る互い違い
Q50:急がば回れ
Q51:パーフェクトシャッフル
Q52:同時に終わる砂時計
Q53:いたずらされたお菓子
Q54:同じ数字で挟み撃ち
Q55:横着なそろばん
Q56:公平に分けられたケーキ

第4章 上級編★★★★ 視点を変えて高速化を目指してみよう!

ソースコードの個性
Q57:あみだくじの横線
Q58:最速の連絡網
Q59:ハンカチ落としの総走行距離
Q60:セルの結合パターン
Q61:同じ大きさに分割
Q62:交差せずに一筆書き
Q63:カレンダーの最大長方形
Q64:迷路で待ち合わせ
Q65:面倒なキャッチボール
Q66:図形の一筆書き
Q67:クロスワードパズルを作成せよ!
Q68:隣り合わないのがマナー?
Q69:男女平等な席替え
Q70:青白歌合戦

索引
ダウンロードファイルは、まだ公開されておりません。今しばらくお待ちくださいますようお願い申し上げます。

書籍への問い合わせ

正誤表、追加情報をご確認の上、こちらよりお問い合わせください

書影の利用許諾について

本書籍に関する利用許諾申請はこちらになります

追加情報はありません。

本書に誤りまたは不十分な記述がありました。下記のとおり訂正し、お詫び申し上げます。
なお、こちらは紙の書籍の正誤となります。

ご購入刷数  紙:  電子書籍 最終更新日:2016年11月16日
発生刷 ページ数 書籍改訂刷 電子書籍訂正 内容 登録日
1刷 041
Q09 問題文
3刷
2つのグループのいずれかで男女の数が異なってしまう
2つのグループのいずれも男女の数が異なってしまう
2015.12.16
1刷 088
Q19 解答の補記
3刷
これを満たす組み合わせは以下のようになります。
これを満たす組み合わせの例は以下のようになります。
2015.12.10
1刷 100
Q23 ソースコード(q23_01.rb)の5行目と6行目
3刷
return 1 if depth == 0 return 0 if coin == 0
return 0 if coin == 0 return 1 if depth == 0

第3刷発行にあわせ、ダウンロードファイルを修正しました(2016.3.3)
2015.11.11
1刷 100
Q23 解答
3刷
16195220通り
16051010通り
2015.11.11
1刷 124
Q30 ソースコード(q30_01.rb)
3刷
N = 20

def set_tap(remain)
return 1 if remain == 1
cnt = 0
# 2口
(1..(remain / 2)).each{|i|
cnt += set_tap(remain - i) * set_tap(i)
}
# 3口
(1..(remain / 3)).each{|i|
(1..((remain - i) / 2)).each{|j|
cnt += set_tap(remain - (i + j)) * set_tap(j) * set_tap(i)
}
}
cnt
end
puts set_tap(N)
N = 20

def set_tap(remain)
return 1 if remain == 1
cnt = 0
# 2口
(1..(remain / 2)).each{|i|
if remain - i == i then
cnt += set_tap(i) * (set_tap(i) + 1) / 2
else
cnt += set_tap(remain - i) * set_tap(i)
end
}
# 3口
(1..(remain / 3)).each{|i|
(i..((remain - i) / 2)).each{|j|
if (remain - (i + j) == i) && (i == j) then
cnt += set_tap(i) * (set_tap(i) + 1) * (set_tap(i) + 2) / 6
elsif remain - (i + j) == i then
cnt += set_tap(i) * (set_tap(i) + 1) * set_tap(j) / 2
elsif i == j then
cnt += set_tap(remain - (i+j)) * set_tap(i) * (set_tap(i)+1) / 2
elsif remain - (i + j) == j then
cnt += set_tap(j) * (set_tap(j) + 1) * set_tap(i) / 2
else
cnt += set_tap(remain - (i + j)) * set_tap(j) * set_tap(i)
end
}
}
cnt
end
puts set_tap(N)

第3刷発行にあわせ、ダウンロードファイルを修正しました(2016.3.3)
2015.11.25
1刷 125
Q30 ソースコード(q30_02.rb)
3刷
N = 20
@memo = {1 => 1}

def set_tap(remain)
return @memo[remain] if @memo.has_key?(remain)
cnt = 0
# 2口
(1..(remain / 2)).each{|i|
cnt += set_tap(remain - i) * set_tap(i)
}
# 3口
(1..(remain / 3)).each{|i|
(1..((remain - i) / 2)).each{|j|
cnt += set_tap(remain - (i + j)) * set_tap(j) * set_tap(i)
}
}
@memo[remain] = cnt
end

puts set_tap(N)
N = 20

@memo = {1 => 1}
def set_tap(remain)
return @memo[remain] if @memo.has_key?(remain)
cnt = 0
# 2口
(1..(remain / 2)).each{|i|
if remain - i == i then
cnt += set_tap(i) * (set_tap(i) + 1) / 2
else
cnt += set_tap(remain - i) * set_tap(i)
end
}
# 3口
(1..(remain / 3)).each{|i|
(i..((remain - i) / 2)).each{|j|
if (remain - (i + j) == i) && (i == j) then
cnt += set_tap(i) * (set_tap(i) + 1) * (set_tap(i) + 2) / 6
elsif remain - (i + j) == i then
cnt += set_tap(i) * (set_tap(i) + 1) * set_tap(j) / 2
elsif i == j then
cnt += set_tap(remain - (i+j)) * set_tap(i) * (set_tap(i)+1) / 2
elsif remain - (i + j) == j then
cnt += set_tap(j) * (set_tap(j) + 1) * set_tap(i) / 2
else
cnt += set_tap(remain - (i + j)) * set_tap(j) * set_tap(i)
end
}
}
@memo[remain] = cnt
end

puts set_tap(N)

第3刷発行にあわせ、ダウンロードファイルを修正しました(2016.3.3)
2015.11.25
1刷 126
Q30 ソースコード(q30_03.js)
3刷
const N = 20;
var memo = [];
memo[1] = 1;

function set_tap(remain){
if (memo[remain]){
return memo[remain];
}
var cnt = 0;
/* 2口 */
for (var i = 1; i <= remain / 2; i++){
cnt += set_tap(remain - i) * set_tap(i);
}
/* 3口 */
for (var i = 1; i <= remain / 3; i++){
for (var j = 1; j <= (remain - i) / 2; j++){
cnt += set_tap(remain - (i + j)) * set_tap(j) * set_tap(i);
}
}
memo[remain] = cnt;
return cnt;
}

console.log(set_tap(N));
const N = 20;
var memo = [];
memo[1] = 1;

function set_tap(remain){
if (memo[remain]){
return memo[remain];
}
var cnt = 0;
/* 2口 */
for (var i = 1; i <= remain / 2; i++){
if (remain - i == i)
cnt += set_tap(i) * (set_tap(i) + 1) / 2;
else
cnt += set_tap(remain - i) * set_tap(i);
}
/* 3口 */
for (var i = 1; i <= remain / 3; i++){
for (var j = i; j <= (remain - i) / 2; j++){
if ((remain - (i + j) == i) && (i == j))
cnt += set_tap(i) * (set_tap(i) + 1) * (set_tap(i) + 2) / 6;
else if (remain - (i + j) == i)
cnt += set_tap(i) * (set_tap(i) + 1) * set_tap(j) / 2;
else if (i == j)
cnt += set_tap(remain - (i+j)) * set_tap(i) * (set_tap(i)+1) / 2;
else if (remain - (i + j) == j)
cnt += set_tap(j) * (set_tap(j) + 1) * set_tap(i) / 2;
else
cnt += set_tap(remain - (i + j)) * set_tap(j) * set_tap(i);
}
}
memo[remain] = cnt;
return cnt;
}

console.log(set_tap(N));

第3刷発行にあわせ、ダウンロードファイルを修正しました(2016.3.3)
2015.11.25
1刷 126
Q30 解答
3刷
136916765通り
63877262通り
2015.11.25
1刷 212
Q51 解答
3刷
①2(n-1)回で「初めて」元に戻ったとき、46個 ②何度も元に戻るが、2(n-1)回のときも元に戻ったとき、22個
①2(n-1)回で「初めて」元に戻ったとき、22個 ②何度も元に戻るが、2(n-1)回のときも元に戻ったとき、46個
2015.12.10
1刷 212
Q51のPoint内、下から3つ目の式
(i×2)^2(n-1)mod(2×n-1)=i
i×2^2(n-1)mod(2×n-1)= i
2016.11.16

関連書籍

関連記事