算法之禪 : 遞推與遞歸

劉鐵猛

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

商品描述

算法是個有趣的東西——針對某個問題設計算法的時候,
不會的人感覺像“大海撈針”,而會的人則感覺像“一葦渡江”。
高手的頭腦裡都有一張“算法地圖”,算法之間不是孤立的,而是彼此連通的。
算法之間的內在聯繫有很多,但挖掘到根源上,就是遞推與遞歸兩種思想。
本書從深度解析遞推和遞歸這兩個基本算法思想開始,
用它們貫穿起了《算法導論》中的幾十個經典算法,
包括排序、查找、回溯、貪心、分治、動態規劃、圖算法等。
本書成稿自作者的教案,秉承了作者一貫的風趣幽默又不失嚴謹的寫作風格,
同時融入了學習心理學和認知科學的實踐原理。
作者的諸多學生在參加完以本書內容為藍本的集訓後進入了微軟、
臉書、亞馬遜、領英、甲骨文等公司,所以本書是經過千錘百煉的一線教學成果。
本書適合於所有想通過學習算法來精進自己編程能力的讀者。
為了傾聽讀者們的心聲、不斷完善這本書,作者熱切地期待大家與他在領英上建立聯繫。
在那裡,作者還將源源不斷地與讀者們分享種類教學資源和工作機會。
作者的領英首頁是https://www.linkedin.com/in/hexagons/。

作者簡介

劉鐵猛

高級軟件工程師,技術作者、譯者、教育者,現就職於亞馬遜(美國)。
曾就職於微軟(美國),著有《深入淺出WPF》一書,銷量數万冊。
精心製作的《C#語言入門詳解》視頻課程點擊量超500萬次,是目前全球排名第一的中文C#教程。
他的多套教學視頻已被微軟收錄為官方認證課程。
他的所有作品風格一致:內容詳實準確、語言風趣幽默、說理深入淺出,被學習者們奉為佳作。

目錄大綱

目錄
致謝
一夜春風,萬樹梨花
第OO章開篇緒言
緣起
預備知識
第01章思想與實現
思想
實現
準備一棵樹
用遞推代碼實現遞推思想
用遞歸代碼實現遞推思想
用遞歸代碼實現遞歸思想
“好”的遞歸與“壞”的遞歸
用遞推代碼實現遞歸思想
思考題
第02章回溯:上古神話中的算法
回溯式遞歸的基本原理
示例1
示例2
神話故事中的算法
迷宮設計入門
探尋迷宮中的路徑
用遞推(循環)代碼實現回溯
思考題
第03章動態規劃:動機決定性質
什麼是動態規劃
透徹理解動態規劃
遞推版動態規劃
遞歸版動態規劃
陷阱:這不是動態規劃
貪心也要動腦子
更上層樓:讓規劃“動態”起來
切年糕
接訂單
聽講座
思考題
動態規劃哲思
第04章排序:算法皇冠上的明珠
遊樂園:O(n2)的簡單排序們
選擇排序
冒泡排序
插入排序
以空間換時間:歸併排序
看運氣的快速排序
兩全其美:堆排序
什麼是“堆”
構建大/小根堆
利用“大根堆”進行原地排序
利用“小根堆”生成升序數組
思考題
第05章查找:來而不往非禮也
二分查找
在己排序的數組上
在平衡二叉搜索樹上
線段樹:化繁為簡
構建線段樹
查詢子段和
字典樹:字母大接龍
遞推版實現
遞歸版實現
並查集:朋友的朋友是朋友
第06章圖:包羅萬象
圖的表達
鄰接列表
鄰接矩陣
應對向、權、環的變化
思考題
圖的遍歷
廣度優先遍歷
深度優先遍歷
遞推版深度優先遍歷
向、權、環對遍歷的影響
頂點的連通性
有無權重對連通性的影響
有無向對連通性的影響
環對連通性的影響
強連通性組件
Kosaraju-Sharir算法
圖上的路徑
BFS式路徑搜尋
DFS式路徑搜尋
自底向上式路徑搜尋
回溯式路徑搜尋
獲取環路
思考題
最短路徑
Dijkstra最短路徑算法
Bellman-Ford最短路徑算法
Floyd-Warshall最短路徑算法
最小生成樹
構建有權無向圖
Prim算法
Kruskal算法
最大流:超時空移花接木
餘量邊,反向邊,餘量網絡,增益路徑
容量返還
Ford-Fulkerson算法實現
最小割:流量的瓶頸
拓撲排序
生成入度圖與出度圖
理解頂點的入度
遞推實現
遞歸實現
思考題
後記