アルゴリズム

情報トレーニング -パズルで学ぶ,なっとくの60題-

丸岡章
朝倉書店

ステップ1 導入

  • 問題1 ハンバーグを焼く
  • 問題2 ニセコインの袋を当てる
  • 問題3 板チョコを最後まで割る
  • 問題4 次にくる形
  • 問題5 横切る曲線
  • 問題6 一筆書きを描く
  • 問題7 タワーのアンケート
  • 問題8 トーナメントの試合数
  • 問題9 関係式の推測
  • 問題10 2次元配列の誤り訂正
  • 問題11 キューブの切り出し
  • 問題12 マージソート回路を組み立てる
  • 問題13 アンケート対象の条件
  • 問題14 コイン置きゲーム
  • 問題15 ハミルトンサイクルを描く
  • 問題16 サイコロ転がし
  • 問題17 信号が伝搬するパスを指定する
  • 問題18 格子面カバー
  • 問題19 2分探索
  • まとめ
    • トピック1 ブール代数

ステップ2 展開

  • 問題20 缶ビールの自動販売機
  • 問題21 2番目に大きい数を求める
  • 問題22 釣り人を運ぶ
  • 問題23 秘密の鍵を当てる
  • 問題24 決定木をつくる
  • 問題25 2つの論理回路の出力の関係
  • 問題26 カバー可能な格子面のサイズ
  • 問題27 キューブによる最小カバー
  • 問題28 隣接が禁止される数の配置
  • 問題29 同数列を生成する書き換え
  • 問題30 コインの整列
  • 問題31 マルチプレクサを構成する
  • 問題32 オオカミ,ヤギ,キャベツの運搬
  • 問題33 魔方陣
  • 問題34 論理式を充足する割り当て
  • 問題35 ナイトの旅
  • 問題36 コップの向きの反転の手順
  • 問題37 3つの円周上への数の配置
  • 問題38 石とり遊びの最後の局面
  • 問題39 ピックアップのお迎え
  • 問題40 系列a^m b^{m n} a^n の生成
  • 問題41 正しいラベルの決定
  • 問題42 コインの面あわせ
  • 問題43 グレーコードの構成
  • 問題44 ニセコイン探し
  • 問題45 デ・ブルーイン系列をつくる
  • 問題46 最後のボールの色を当てる
  • 問題47 L形タイルによる格子面カバー
  • まとめ
    • トピック2 再帰的定義と書き換えルール
    • トピック3 背理法
    • トピック4 グラフ
    • トピック5 有限オートマトン

ステップ3 発展

  • 問題48 チェス盤の彩色
  • 問題49 正直者とウソつきの島
  • 問題50 ヒルベルトカーブを描く
  • 問題51 2方向ソート
  • 問題52 ライフゲームのグライダーの展開
  • 問題53 ハノイの塔
  • 問題54 2SATを解く
  • 問題55 コイン最大獲得パス
  • 問題56 クイーンを配置する
  • 問題57 反転カードゲーム
  • 問題58 最長共通部分系列を求める
  • 問題59 囚人の推論
  • 問題60 ソート回路を構成する
  • まとめ
    • トピック6 セル構造オートマトンと自己増殖機械
    • トピック7 効率のよいアルゴリズムの設計法
    • トピック8 P vs NP問題

ヒント
解答
問題の分類
文献案内
索引