アルゴリズム

アルゴリズムパズル - プログラマのための数学パズル入門

Anany Levitin
Maria Levitin
オライリージャパン

質問形式の序文
謝辞
パズル一覧

  • チュートリアルのパズル
  • 本編のパズル
  • 墓碑銘パズル

第1章 チュートリアル

  • 一般的なアルゴリズム設計戦略
    • 魔方陣(Magic Square)
    • nクイーン問題(The n-Queens Problem)
    • 有名人の問題(Celebrity Problem)
    • 数当てゲーム(Number Guessing)(別名20の扉(Twenty Questions))
    • トロミノ・パズル(Tromino Puzzle)
    • アナグラム発見(Anagram Detection)
    • 封筒に入った現金(Cash Envelopes)
    • 2人の嫉妬深い夫(Two Jealous Husbands)
    • グァリーニのパズル(Guarini’s Puzzle)
    • 最適なパイの切り分け(Optimal Pie Cutting)
    • 互いに攻撃しないキング(Non-Attacking Kings)
    • 真夜中の橋渡り(Bridge Crossing at Night)
    • レモネード売り場の設置場所(Lemonade Stand Placement)
    • 正への変化(Positive Changes)
    • 最短経路の数え上げ(Shortest Path Counting)
  • 分析テクニック
    • チェスの発明(Chess Invention)
    • 正方形の増大(Square Build-Up)
    • ハノイの塔(Tower of Hanoi)
    • 不完全なチェス盤のドミノ敷き詰め(Domino Tiling of Deficient Chessboards)
    • ケーニヒスベルクの橋の問題(The Königsberg Bridges Problem)
    • 板チョコレートの分割(Breaking a Chocolate Bar)
    • トウモロコシ畑の鶏(Chickens in the Corn)

第2章 パズル

  • 初級パズル
    • 1. 狼と山羊とキャベツ(A Wolf, a Goat, and a Cabbage)
    • 2. 手袋選び(Glove Selection)
    • 3. 長方形の分割(Rectangle Dissection)
    • 4. 兵士の輸送(Ferrying Soldiers)
    • 5. 行と列の入れ替え(Row and Column Exchanges)
    • 6. 指数え(Predicting a Finger Count)
    • 7. 真夜中の橋渡り(Bridge Crossing at Night)
    • 8. ジグソーパズルの組み立て(Jigsaw Puzzle Assembly)
    • 9. 暗算(Mental Arithmetic)
    • 10. 8枚の硬貨に含まれる1枚の偽造硬貨(A Fake Among Eight Coins)
    • 11. 偽造硬貨の山(A Stack of Fake Coins)
    • 12. 注文付きのタイルの敷き詰め(Questionable Tiling)
    • 13. 通行止めの経路(Blocked Paths)
    • 14. チェス盤の再構成(Chessboard Reassembly)
    • 15. トロミノによる敷き詰め(Tromino Tilings)
    • 16. パンケーキの作り方(Making Pancakes)
    • 17. キングの到達範囲(A King’s Reach)
    • 18. 角から角への旅(A Corner-to-Corner Journey)
    • 19. ページの番号付け(Page Numbering)
    • 20. 山下りの最大和(Maximum Sum Descent)
    • 21. 正方形の分割(Square Dissection)
    • 22. チームの並べ方(Team Ordering)
    • 23. ポーランド国旗の問題(Polish National Flag Problem)
    • 24. チェス盤の塗り分け(Chessboard Colorings)
    • 25. 最高の時代(The Best Time to Be Alive)
    • 26. 何番目かを求めよ(Find the Rank)
    • 27. 世界周遊ゲーム(The Icosian Game)
    • 28. 一筆書き(Figure Tracing)
    • 29. 魔方陣再び(Magic Square Revisited)
    • 30. 棒の切断(Cutting a Stick)
    • 31. 3つの山のトリック(The Three Pile Trick)
    • 32. シングル・エリミネーション方式のトーナメント(Single-Elimination Tournament)
    • 33. 魔方陣と疑似魔方陣(Magic and Pseudo-Magic)
    • 34. 星の上の硬貨(Coins on a Star)
    • 35. 3つの水入れ(Three Jugs)
    • 36. 限られた多様性(Limited Diversity)
    • 37. 2n枚の硬貨の問題(2n-Counters Problem)
    • 38. テトロミノによる敷き詰め(Tetromino Tiling)
    • 39. 盤面上の一筆書き(Board Walks)
    • 40. 交互に並ぶ4つのナイト(Four Alternating Knights)
    • 41. 電灯の輪(The Circle of Lights)
    • 42. もう1つの狼と山羊とキャベツのパズル(The Other Wolf-Goat-Cabbage Puzzle)
    • 43. 数の配置(Number Placement)
    • 44. より軽いか?より重いか?(Lighter or Heavier?)
    • 45. ナイトの最短経路(A Knight’s Shortest Path)
    • 46. 3色配置(Tricolor Arrangement)
    • 47. 展示計画(Exhibition Planning)
    • 48. マックナゲット数(McNugget Numbers)
    • 49. 宣教師と人食い人種(Missionaries and Cannibals)
    • 50. 最後の球(Last Ball)
  • 中級パズル
    • 51. 存在しない数字(Missing Number)
    • 52. 三角形の数え上げ(Counting Triangles)
    • 53. バネ秤を使った偽造硬貨の検出(Fake-Coin Detection with a Spring Scale)
    • 54. 長方形の切断(Cutting a Rectangular Board)
    • 55. 走行距離計パズル(Odometer Puzzle)
    • 56. 新兵の整列(Lining Up Recruits)
    • 57. フィボナッチのウサギ問題(Fibonacci’s Rabbits Problem)
    • 58. ソートして、もう1回ソート(Sorting Once, Sorting Twice)
    • 59. 2色の帽子(Hats of Two Colors)
    • 60. 硬貨の三角形から正方形を作る(Squaring a Coin Triangle)
    • 61. 対角線上のチェッカー(Checkers on a Diagonal)
    • 62. 硬貨拾い(Picking Up Coins)
    • 63. プラスとマイナス(Pluses and Minuses)
    • 64. 八角形の作成(Creating Octagons)
    • 65. ビット列の推測(Code Guessing)
    • 66. 残る数字(Remaining Number)
    • 67. ならし平均(Averaging Down)
    • 68. 各桁の数字の和(Digit Sum)
    • 69. 扇の上のチップ(Chips on Sectors)
    • 70. ジャンプにより2枚組を作れI(Jumping into Pairs I)
    • 71. マスの印付けI(Marking Cells I)
    • 72. マスの印付けII(Marking Cells II)
    • 73. 農夫とニワトリ(Rooster Chase)
    • 74. 用地選定(Site Selection)
    • 75. ガソリンスタンドの調査(Gas Station Inspections)
    • 76. 効率良く動くルーク(Efficient Rook)
    • 77. パターンを探せ(Searching for a Pattern)
    • 78. 直線トロミノによる敷き詰め(Straight Tromino Tiling)
    • 79. ロッカーのドア(Locker Doors)
    • 80. プリンスの巡回(The Prince’s Tour)
    • 81. 有名人の問題再び(Celebrity Problem Revisited)
    • 82. 表向きにせよ(Heads Up)
    • 83. 制約付きハノイの塔(Restricted Tower of Hanoi)
    • 84. パンケーキのソート(Pancake Sorting)
    • 85. 噂の拡散I(Rumor Spreading I)
    • 86. 噂の拡散II(Rumor Spreading II)
    • 87. 伏せてあるコップ(Upside-Down Glasses)
    • 88. ヒキガエルとカエル(Toads and Frogs)
    • 89. 駒の交換(Counter Exchange)
    • 90. 座席の再配置(Seating Rearrangements)
    • 91. 水平および垂直なドミノ(Horizontal and Vertical Dominoes)
    • 92. 台形による敷き詰め(Trapezoid Tiling)
    • 93. 戦艦への命中(Hitting a Battleship)
    • 94. ソート済み表における探索(Searching a Sorted Table)
    • 95. 最大と最小の重さ(Max-Min Weights)
    • 96. 階段形領域の敷き詰め(Tiling a Staircase Region)
    • 97. 上部交換ゲーム(The Game of Topswops)
    • 98. 回文数え上げ(Palindrome Counting)
    • 99. ソートされた列の反転(Reversal of Sort)
    • 100. ナイトの到達範囲(A Knight’s Reach)
    • 101. 床のペンキ塗り(Room Painting)
    • 102. 猿とココナツ(The Monkey and the Coconuts)
    • 103. 向こう側への跳躍(Jumping to the Other Side)
    • 104. 山の分割(Pile Splitting)
    • 105. MU パズル(The MU Puzzle)
    • 106. 電球の点灯(Turning on a Light Bulb)
    • 107. キツネとウサギ(The Fox and the Hare)
    • 108. 最長経路(The Longest Route)
    • 109. ダブルnドミノ(Double-n Dominoes)
    • 110. カメレオン(The Chameleons)
  • 上級パズル
    • 111. 硬貨の三角形の倒立(Inverting a Coin Triangle)
    • 112. ドミノの敷き詰め再び(Domino Tiling Revisited)
    • 113. 硬貨の除去(Coin Removal)
    • 114. 格子点の通過(Crossing Dots)
    • 115. バシェのおもり(Bachet’s Weights)
    • 116. 不戦勝の数え上げ(Bye Counting)
    • 117. 1次元ペグソリティア(One-Dimensional Solitaire)
    • 118. 6つのナイト(Six Knights)
    • 119. 着色トロミノによる敷き詰め(Colored Tromino Tiling)
    • 120. 硬貨の再分配機械(Penny Distribution Machine)
    • 121. 超強力卵の試験(Super-Egg Testing)
    • 122. 議会和平工作(Parliament Pacification)
    • 123. オランダ国旗の問題(Dutch National Flag Problem)
    • 124. 鎖の切断(Chain Cutting)
    • 125. 7回で5つの物体をソートする(Sorting 5 in 7)
    • 126. ケーキの公平な分割(Dividing a Cake Fairly)
    • 127. ナイトの巡回(The Knight’s Tour)
    • 128. セキュリティスイッチ(Security Switches)
    • 129. 家扶のパズル(Reve’s Puzzle)
    • 130. 毒入りのワイン(Poisoned Wine)
    • 131. テイトによる硬貨パズル(Tait’s Counter Puzzle)
    • 132. ペグソリティアの軍隊(The Solitaire Army)
    • 133. ライフゲーム(The Game of Life)
    • 134. 点の塗り分け(Point Coloring)
    • 135. 異なる組合せ(Different Pairings)
    • 136. スパイの捕獲(Catching a Spy)
    • 137. ジャンプにより2枚組を作れII(Jumping into Pairs II)
    • 138. キャンディの共有(Candy Sharing)
    • 139. アーサー王の円卓(King Arthur’s Round Table)
    • 140. nクイーン問題再び(The n-Queens Problem Revisited)
    • 141. ヨセフス問題(The Josephus Problem)
    • 142. 12枚の硬貨(Twelve Coins)
    • 143. 感染したチェス盤(Infected Chessboard)
    • 144. 正方形の破壊(Killing Squares)
    • 145. 15パズル(The Fifteen Puzzle)
    • 146. 動く獲物を撃て(Hitting a Moving Target)
    • 147. 数の書かれた帽子(Hats with Numbers)
    • 148. 自由への1硬貨(One Coin for Freedom)
    • 149. 広がる小石(Pebble Spreading)
    • 150. ブルガリアン・ソリティア(Bulgarian Solitaire)

第3章 ヒント

第4章 解

参考文献
索引(設計戦略と分析テクニック)
索引(人名と用語)