演算法邏輯力：工程師必備的演算法解題、設計、加速技巧 (Algorithmic Thinking: A Problem-Based Introduction)

Daniel Zingaro 著 蔡牧村 譯

演算法邏輯力：工程師必備的演算法解題、設計、加速技巧 (Algorithmic Thinking: A Problem-Based Introduction)

買這商品的人也買了...

商品描述

無師自通最高難度的計算問題！





     
  •  
  •  
  • 本書將教你如何解決艱難的程式設計問題，並設計屬於你自己的演算法。透過教學大神Daniel Zingaro從USACO、IOI等世界級程式競賽中精選來的範例，你將學會如何分類問題、選擇資料結構，並辨認出適合的演算法。同時也將學到，你所選擇的資料結構（無論是雜湊表、堆積、或樹）會如何影響執行時間，以及如何讓你的演算法加速，包括應用遞迴、動態規劃、二元搜尋等強大的策略來解決艱難的問題。

    透過程式碼的逐一講解，你將學到的演算法和資料結構包括：
    ❏ 用圖與廣度優先搜尋演算法來尋找桌遊的最佳策略、或是翻譯一本書的最好方法。
    ❏ 用Dijkstra演算法來判斷有多少老鼠能成功走出迷宮、或是兩個地點之間最短路徑的數量。
    ❏ 用聯集尋找資料結構來回答關於社群網路上的連結或判斷敵友等問題。
    ❏ 用堆積資料結構來決定促銷活動期間所送出的獎金金額。
    ❏ 用雜湊表資料結構來判斷雪花是否獨一無二、或在字典中辨認出複合詞。

    ➤本書中的每一道問題都可在程式解題系統網站上，由系統判定是否正確解題，網站的網址和問題編號都會列在說明之中。

作者簡介

  • Daniel Zingaro任教於多倫多密西沙加大學的數學與資訊科學系，是位獲獎的助理教授。他在大學中以他獨特的互動式教學方法聞名，且其專業在國際間以主動學習的領域著稱。

目錄大綱

  • [導論]
    線上資源
    本書對象
    程式語言
    --為什麼是C語言？
    --靜態關鍵字
    --導入的檔案
    --記憶體釋放
    主題
    解題系統
    題目描述的構成
    題目：取餐排隊
    --解開問題
    筆記

    [第1章_雜湊表]
    題目一：獨特雪花
    --問題
    --簡化問題
    --解決核心問題
    --解答一：逐對比較
    --解答二：減輕工作量
    雜湊表
    --設計雜湊表
    --為什麼要使用雜湊表？
    題目二：複合詞
    --問題
    --辨別複合詞
    --解答
    題目三：拼字檢查─刪除字母
    --問題
    --思索雜湊表
    --一個量身打造的解答
    摘要
    筆記

    [第2章_樹與遞迴]
    題目一：萬聖節糖果收集
    --問題
    --二元樹
    --解決一個較簡單的實例
    --二元樹表示方法
    --收集所有糖果
    --一個完全不一樣的解答
    --走最少街道
    --讀取輸入
    為什麼要使用遞迴？
    題目二：子孫的距離
    --問題
    --讀取輸入
    --一個節點的子孫數目
    --全部節點的子孫數目
    --節點排序
    --輸出資訊
    --main函數
    總結
    筆記

    [第3章_記憶法與動態規劃]
    題目一：漢堡狂熱
    --問題
    --產生一個計畫
    --刻劃最佳解
    --解答一：遞迴
    --解答二：記憶法
    --解答三：動態規劃
    記憶法與動態規劃
    --步驟一：最佳解的結構
    --步驟二：遞迴解
    --步驟三：記憶法
    --步驟四：動態規劃
    題目二：守財奴
    --問題
    --刻劃出最佳解
    --解答一：遞迴
    --解答二：記憶法
    題目三：冰球世仇
    --問題
    --關於世仇
    --刻劃出最佳解
    --解答一：遞迴
    --解答二：記憶法
    --解答三：動態規劃
    --空間最佳化
    題目四：及格方法
    --問題
    --解答：記憶法
    總結
    筆記

    [第4章_圖與廣度優先搜尋]
    題目一：騎士追逐
    --問題
    --最佳化移動
    --騎士的最佳結果
    --騎士反反覆覆
    --時間最佳化
    圖（Gragh）與 BFS
    --什麼是圖？
    --圖vs.樹
    --圖上的BFS
    題目二：攀爬繩子
    --問題
    --解答一：找出動作
    --解答二：重新建模
    題目三：書籍翻譯
    --問題
    --圖的建立
    --BFS
    --總成本
    總結
    筆記

    [第5章_加權圖中的最短路徑]
    題目一：老鼠迷宮
    --問題
    --從BFS繼續邁進
    --加權圖中的最短路徑
    --圖的建立
    --實作Dijkstra演算法
    --兩種最佳化
    Dijkstra演算法
    --Dijkstra演算法的執行時間
    --負權重邊
    題目二：拜訪奶奶規劃
    --問題
    --相鄰矩陣
    圖的建立
    --怪異路徑
    --任務一：最短路徑
    --任務二：最短路徑的數目
    總結
    筆記

    [第6章_二元搜尋]
    題目一：螞蟻餵食
    --問題
    --新風味的樹問題
    --讀取輸入
    --可行性測試
    --搜尋解答
    二元搜尋
    --二元搜尋的執行時間
    --判斷可行性
    --搜尋排序過的陣列
    題目二：跳躍河流
    --問題
    --貪婪演算法的思路
    --測試可行性
    --搜尋解答
    --讀取輸入
    題目三：生活品質
    --問題
    --排序所有的矩形
    --二元搜尋
    --測試可行性
    --更快速測試可行性
    題目四：洞穴門
    --問題
    --解決子任務
    --使用線性搜尋
    --使用二元搜尋
    總結
    筆記

    [第7章_堆積與區段樹]
    題目一：超市促銷
    --問題
    --解答一：陣列中的最大值與最小值
    --最大堆積
    --最小堆積
    --解答二：堆積
    堆積
    --兩個額外的應用
    --選擇一個資料結構
    題目二：建立樹堆
    --問題
    --遞迴輸出樹堆
    --根據標籤排序
    --解答一：遞迴
    --區間最大值查詢
    --區段樹
    --解答二：區段樹
    區段樹
    題目三：二元素和
    --題目
    --填寫區段樹
    --查詢區段樹
    --更新區段樹
    --main函數
    總結
    筆記

    [第8章_聯集尋找]
    問題一：社群網路
    --問題
    --用圖來模擬
    --解答一：BFS
    --聯集尋找
    --解答二：聯集尋找
    --最佳化一：依大小聯集
    --最佳化二：路徑壓縮
    聯集尋找
    --關聯：三個需求
    --選擇聯集尋找
    --最佳化
    題目二：朋友與敵人
    --問題
    --擴充：敵人
    --main函數
    --尋找和聯集
    --SetFriends與SetEnemies
    --AreFriends與AreEnemies
    題目三：抽屜雜務
    --問題
    --等價抽屜
    --main函數
    --尋找和聯集
    總結
    筆記

    後記

    [附錄A_演算法執行時間]
    計時與其他東西之事件簿
    大O符號
    --線性時間
    --常數時間
    --另一個例子
    --平方時間
    --本書中的大O

    [附錄B_因為我忍不住]
    獨特雪花：隱式鏈結串列
    漢堡狂熱：重建解答
    騎士追逐：編碼移動
    Dijkstra演算法：使用堆積
    --老鼠迷宮：用堆積來追蹤
    --老鼠迷宮：用堆積來實作
    路徑壓縮的壓縮
    --步驟一：不使用三元運算子
    --步驟二：較簡潔的指派運算子
    --步驟三：理解遞迴

    [附錄C_題目貢獻者]

類似商品