問題解決のPythonプログラミング

―数学パズルで鍛えるアルゴリズム的思考

[cover photo]
TOPICS
Programming , Math , Python
発行年月日
PRINT LENGTH
288
ISBN
978-4-87311-851-2
原書
Programming for the Puzzled
FORMAT
Print PDF
Ebook
3,080円
Ebookを購入する
Print
3,080円

MITで20年にわたり教鞭を執る著者が、1、2年生を対象としたプログラミングの授業で実際に使っている教材をもとに執筆したものです。「楽しみながらアルゴリズム的思考とプログラミングスキルを鍛える」という意図に基づき、著者が選んだ21の数学パズルを解くことを通じて、論理的な思考と柔軟な発想力を身に付けることができます。掲載されているコードはすべてダウンロード可能。また、章末の練習問題で習熟度を確認できます。「閃きの瞬間」が訪れたときの喜びを体感し、プログラミング本来の楽しみを知ることができる一冊です。

目次

日本語版まえがき
謝辞

1章 帽子を全員で揃える
    同じ考えの人のシーケンスを求める
    文字列、リスト、タプル
    アルゴリズムからコードへ
    コードの最適化
    リストの作成と変更
    スコープ制御
    アルゴリズムの最適化
    1パスアルゴリズム
    応用分野
    練習問題

2章 パーティーに行くタイミング
    時間をもう一度チェックする
    時間チェックをスマートにこなす
    ソートの表現
    練習問題

3章 心を読む(準備をしてから)
    助手の作業のコーディング
    マジシャンの作業のコーディング
    トリックを一人遊びでマスターする
    情報の暗号化
    4枚カードによるマジックのトリック
    練習問題

4章 女王たちを一緒にするな
    系統的探索
    2次元リスト/配列の盤面
    1次元リスト/配列の盤面
    反復数え上げ
    練習問題

5章 水晶をどうぞ壊してください
    2個の玉での効率的な探索
    d個の玉で効率的な探索
    2個の玉で落とす回数を減らす
    練習問題

6章 偽造硬貨を探す
    分割統治法
    再帰分割統治法
    3進数表現
    計量パズルの変形
    練習問題

7章 平方根もカッコイイ
    反復法
    二分法で探索
    二分探索
    三分探索
    練習問題

8章 招かれざる客
    最初の試み
    最大選択を常に与える
    すべての組合せを生成する
    嫌い関係の組合せを取り除く
    最大の組合せを選ぶ
    メモリ使用を最適化する
    応用
    練習問題

9章 アメリカズ・ゴット・タレント
    組合せを1つずつ生成してはテストする
    才能の欠ける組合せを決定する
    応用
    練習問題

10章 おびただしい女王
    再帰最大公約数
    再帰フィボナッチ
    再帰Nクイーン
    再帰の応用
    練習問題

11章 中庭にタイルを敷く
    マージソート
    マージソートの実行と分析
    2×2の中庭の基底部
    再帰ステップ
    リスト内包表記の基本
    プリティプリント
    別のタイル問題
    練習問題
    
12章 ひねりを加えたバラモンの塔
    TOHの再帰解
    ATOH再帰解
    グレイコードとの関係
    練習問題

13章 整理が苦手な修理屋
    分割統治のピボット決め
    ソーティングとの関係
    インプレース分割
    ソートマニア
    練習問題

14章 数独は二度とごめんだ
    数独の再帰的解法
    再帰探索における推論
    数独パズルの難しさ
    練習問題

15章 両替する方法を数える
    紙幣の再帰選択
    重複の削除
    最少枚数で両替
    練習問題

16章 貪欲は良いことだ
    貪欲方式
    最短期間ルール
    開始時刻順ルール
    最少重複ルール
    終了時間順ルール
    貪欲法が有効な場合
    練習問題

17章 アナグラム狂
    アナグラムグループを1つずつ探し出す
    ソートによるアナグラムのグループ分け
    ハッシングによるアナグラムのグループ分け
    辞書
    アナグラムのグループ分けに辞書を使う
    ハッシュ表
    練習問題

18章 メモリは役に立つ
    再帰解
    硬貨選択のトレースバック
    メモ化
    例外をなくす
    動的プログラミング
    練習問題

19章 忘れられない週末
    分割を見つける
    グラフが2部グラフかどうかチェックする
    グラフ表現
    グラフ彩色
    練習問題

20章 6次の隔たり
    幅優先探索
    集合
    幅優先探索に集合を使う
    歴史的なこと
    練習問題

21章 質問するにもお金がかかる
    辞書を用いた二分探索木
    辞書表現を使ったBST演算
    OOPスタイルの二分探索木
    パズルに戻る:アルゴリズム
    パズルを解くコード
    データ構造の比較
    練習問題

訳者あとがき
索引