基礎算法藝術( 簡體 字) | |
作者:張新華 | 類別:1. -> 程式設計 -> 演算法 |
出版社:清華大學出版社 | 3dWoo書號: 44009 詢問書籍請說出此書號! 有庫存 NT售價: 445 元 |
出版日:4/1/2016 | |
頁數:714 | |
光碟數:0 | |
站長推薦: | |
印刷:黑白印刷 | 語系: ( 簡體 字 ) |
ISBN:9787302409496 | 加入購物車 │加到我的最愛 (請先登入會員) |
(簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證, 繁體書的下載亦請直接連絡出版社) | |
第一章分治算法
折半查找法 遞歸二分算法★ 非遞歸二分法★ 拓展與練習 魔法石的誘惑 分治算法★ 數學方法★ 拓展與練習 逃亡 分治算法★ 數學方法1★★ 數學方法2★★ 拓展與練習 快速冪運算 基本快速冪算法★ 位優化快速冪算法★ 拓展與練習 運動會 循環比賽★ 殘缺棋盤★ 解一元三次方程 枚舉法★ 二分法★ 拓展與練習 數的查找 第k小數1★ 第k小數2★ 第k小數3★ 拓展與練習 剔除多余括號 二分法★★ 非二分法★ 聰明的質檢員 二分法+前序和★★ 拓展與練習 最接近點對問題 一維算法★★ 二維算法★★ 拓展與練習 第二章遞歸算法 棋子移動 遞歸算法★ 拓展與練習 地盤劃分 樸素遞歸算法★ 優化遞歸算法★ 拆分自然數 遞歸算法★ 回溯算法★ 分形圖 分形圖1★★ 分形圖2★★ 拓展與練習 N皇后問題 遞歸算法1★ 遞歸算法2★ 遞歸算法3★★ 遞歸算法4★ 回溯算法★ 位運算法★★★ 拓展與練習 求子集 遞歸算法★ 位運算法★ 數字三角形 遞歸算法★ 記憶化搜索優化算法★ 深度優先搜索算法★ 位運算法★ 回溯算法★ 動態規劃算法★ 滾動數組優化算法★ 非完美算法★ 拓展與練習 油桶問題 窮舉法★ 遞歸算法★ 動態規劃算法1★ 動態規劃算法2★ 拓展與練習 傳球游戲 遞歸搜索法★ 窮舉法★ 遞推算法★ 第三章排列組合問題 全排列問題 非字典序遞歸算法★ 深搜字典序★ 位運算法★★ STL模板法★ 火星人問題★ 拓展與練習 組合問題 組合公式法★ 遞推法★ 遞歸算法★ 位運算法★★ Jam的計數法★ 拓展與練習 乘法游戲 全排列法★★ 區間動態規劃法★★ 郵票面值問題 排列組合法★★ DFS+動規★★ 第四章高精度算法 被限制的加法★ 簡單高精度加法★ 簡單高精度減法★ 簡單高精度乘法★★ 高精度冪 普通快速冪算法★★ 指針交換地址優化算法★★ 高精度分數 樸素算法★ 優化算法★★ 高精度階乘 非遞歸式算法★★ 樸素高精度算法★ 優化算法1★ 優化算法2★ 優化算法3★★ 高精度數除以低精度數1★ 高精度數除以低精度數2★ 普通高精度數除以高精度數 普通算法★★★ 改進算法★★★ 萬進制高精度加法★ 萬進制高精度減法★ 萬進制高精度乘法★★ 萬進制高精度除法★★★ 組合數的高精度算法 算法1★ 算法2★ 算法3★★ 算法4★★★ 第五章排序算法 一次查找兩元素★ 常用排序法 直接插入排序法★ 選擇排序法★ 樸素快速排序法★ 隨機化快速排序法★ 簡單計數排序法★ 穩定計數排序法★ 基數排序法★ 希爾排序法★ 歸并排序法★ 各種排序算法的比較 緊急集合★ 求逆序對數 歸并排序求逆序對數★ 樹狀數組求逆序對數★★★ 拓展與練習 第六章窮舉算法 火柴棒等式 窮舉法★ 拓展與練習 加急密文★ 翻轉棋盤 枚舉+DFS★ 枚舉+BFS+位運算★★ 拓展與練習 排隊 窮舉法★ 動態規劃法★★ 選擇客棧 樸素算法★ 優化算法1★ 優化算法2★ 時鐘問題 普通枚舉法★ 優化枚舉法★★ 位運算法★★ 拓展與練習 快算24點 回溯算法★★ 全排列+枚舉算法★★ 檢測方法 推理練習 偵探推理★★★ 拓展與練習 第七章貪心算法 刪數問題★ 數列極差問題★ 不相交區間問題 電視節目安排★ 拓展與練習 區間選點問題 監測點★ 雷達問題★★ 廣告問題★★ 區間覆蓋問題 時空定位1★ 時空定位2★ 平均分配問題 均分紙牌★★ 作業調度問題 流水作業調度問題★ 趕作業★ 釣魚★★ 田忌賽馬★★ 普通貪心法 動態規劃法 貪心+動規法 拓展與練習 第八章遞推算法 過河卒★ 數的計數 遞推算法★ 遞歸算法★ 動態規劃算法★ 儲油點★ 挖地雷★ 偶數3的個數★ 布陣 方法一★ 方法二★ 方法三★ 方法四★ 極值問題★★ 區域劃分問題★ 軍事情報★ 密文傳送★★ 漢諾塔問題 標準漢諾塔問題★ 雙塔問題★ 四塔問題★★ M塔問題★★ 妖獸特攻隊★★ 平面分割問題 凸多邊形的三角形剖分★★ 拓展與練習 實數數列 算法1★★★ 算法2★★★ 第九章搜索算法 四色地圖★ 迷宮問題 寬度優先搜索★ 寬度優先搜索STL版★ 深度優先搜索★ 深度優先搜索遞歸法★ 騎士遍歷問題 騎士遍歷初級版★ 騎士遍歷普通版★ 騎士遍歷優化版★★★ 拓展與練習 八數碼問題 康托展開★ 康托展開逆運算★ 哈希函數★ 寬搜算法★ 雙向寬度優先搜索★★ 雙向寬度搜索+康托展開★★ A*算法★★★ IDA*算法★★ 拓展與練習 魔板問題 寬搜算法★★ 蟲食算★★ 數獨游戲★★ 拓展與練習 第十章模擬算法 貓和老鼠★ 奶牛的命運★★ 世紀梭哈★★ 小球鐘★★ 第十一章動態規劃 最長不下降子序列 機器人軍團★ 抄近路★ 魔法石礦★ 攔截導彈★★ 樓蘭寶藏★★ 和諧俱樂部★★ 滑雪★★ 拓展與練習 簡單背包問題 枚舉算法★ 遞歸算法★ 0/1背包問題 動態規劃算法★ 拓展與練習 貨幣問題 貨幣系統問題★ 拓展與練習 數字分組問題 數字分組1★ 數字分組2★ 完全背包問題 完全背包問題★ 完全背包算法的優化★ 0/1背包算法的優化★ 拓展與練習 多重背包問題 多重背包★ 太空梯★ 拓展與練習 混合背包問題 忙碌★★ 拓展與練習 理想收入問題 樸素動態規劃★ 優化算法1★ 優化算法2★ 優化算法3★ 優化算法4★ 優化算法5★ 優化算法6★ 優化算法7★ 優化算法8★ 貪心算法★ 數的劃分 枚舉算法★ 遞歸算法★ 動規算法1★ 動規算法2★ 動規算法3★ 樓梯問題 動規算法1★ 動規算法2★ 動規算法3★ 動規算法4★ 動規算法5★ 動規算法6★ 母函數算法★★ 拓展與練習 合并問題 合并魔法石1★ 合并魔法石2★★ 多邊形魔法陣★★ 能量項鏈★★ 路徑問題 最短路徑★ 最小交通費用問題★ 放置問題 書架問題1★ 書架問題2★ 安排車廂★ 唱片錄制★ 雙色馬★ 拓展與練習 數字游戲 乘積最大★ 添加號問題★ 加減人生★ 模擬人生★ 矩陣連乘★ 拓展與練習 相遇問題 動規算法1★ 遞歸算法★ 寬度搜索算法★ 動規優化1★ 動規優化2★ 動規優化3★ 動規優化4★★ 動規優化5★★ 拓展與練習 最大連續子序列問題 最大連續子序列和★ 最大連續子序列積★★ k個最大連續子序列和★ 子矩陣問題 二維最大子矩陣問題★★ 擴展最大子矩陣問題★★ 子矩陣變形問題★★ 子串問題 最長前綴★ zipper★ 最長公共子串問題★★ 確定基因功能★★ 拓展與練習 最長公共上升子序列 優化算法1★ 優化算法2★ 購物問題 購物問題★ 收購魔法石★ 商店購物★ 資源分配問題 機器分配★ 系統可靠性★ 郵局問題★ 快餐問題★ 切割能量棒★ 調度問題★ 分割問題 凸多邊形三角劃分★★ 凸多邊形分割★★ 拓展與練習 雙重動規 城市交通★★ 復雜的審批★★ 拓展與練習 多進程動規 方格取數★★ 3取方格數★★ 拓展與練習 狀態壓縮動態規劃 猛獸軍團1★★ 猛獸軍團2★★ 炮兵陣地★★ 清掃計劃★★ 拓展與練習 樹型動態規劃 加分二叉樹★★ 寶藏★★ 選課★★★ 鴻門宴★★★ 拓展與練習 附錄AC++語言使用參考 類和對象 類的繼承 函數重載 操作符重載 顯式類型轉換 異常處理 名字空間 友員函數 內聯函數 靜態成員 附錄B標準模板庫使用參考 vector向量容器 deque雙端隊列容器 list雙向鏈表容器 set集合容器 multiset多重集合容器 map映照容器 multimap多重映照容器 stack堆棧容器 queue隊列容器 priority_queue優先隊列容器 adjacent_find查找相鄰元素 find_first_of查找第一個匹配字符 count統計個數 堆排序 sort排序算法 歸并算法merge inplace_merge內部歸并 stable_sort穩定排序 lower_bound下確界 upper_bound上確界 折半搜索binary_search Includes判斷集合包含關系 集合操作 最值 產生組合數 ⅩⅦ 附錄C常用在線評測網站 參考文獻 重點介紹各種基礎算法,如分治算法、貪心算法、枚舉算法、動態規劃算法等。注重培養學生用“多向思考”“一題多解”和“一題多變”的方式解決問題。一書在手、盡在掌握。
為什么編寫這套書?
隨著計算機逐步深入人類生活的各個方面,利用計算機及其程序設計來分析、解決問題的算法在計算機科學乃至于整個科學界的作用日益明顯。相應地,各類以算法為主的程序設計競賽也層出不窮: 在國內,有全國青少年信息學奧林匹克聯賽(National Olympiad in Informatics in Provinces,NOIP),該聯賽與全國中學生生物學聯賽、全國中學生物理競賽、全國高中數學聯賽、全國高中學生化學競賽,并稱為國內影響力最大的“五大奧賽”; 在國際,有中學生的國際信息學奧林匹克競賽(International Olympiad in Informatics,IOI)、面向亞太地區在校中學生的信息學科競賽(即亞洲與太平洋地區信息學奧林匹克,AsiaPacific Informatics Olympiad,APIO)和國際大學生程序設計競賽(ACM International Collegiate Programming Contest,ACM/ICPC)等。 各類算法競賽要求參賽選手不僅必須具有深厚的計算機算法功底、快速、準確的編程能力以及創造性的思維,而且還必須具備團隊合作精神和抗壓工作的能力,因此算法競賽在高校、IT公司和其他社會各界中獲得越來越多的認同和重視。算法競賽的優勝者,更是微軟、Google、百度、Facebook等全球著名IT公司爭相高薪招募的對象。因此,不僅是各類參加算法競賽的選手,即使是不參加此類競賽的很多研究工作者和從事IT行業的人士,都希望能獲得這方面的專業訓練并從中得到一定的收獲。 但是,長期以來,算法競賽的內容以其高難度、高要求而困住了許多有志于參加算法競賽的愛好者的求索腳步。部分已出版的同類書籍或艱深難懂、或教條灌輸,使不少愛好者望而卻步,半途而廢,以至于研究算法成了一種“曲高和寡”的學問,嚴重制約了算法競賽優秀人才的培養。 殊不知,書上多數看似復雜難懂的知識或內容,其實總是可以找到一種深入淺出、化難為易的表述方法,使讀者能看得懂、學得透,并最終達到觸類旁通、舉一反三的學習目標。因此本套叢書的寫作初衷,是試圖將看似晦澀難懂的算法表述得輕松、活潑、易懂。同時也是為了彌補國內算法競賽以及普及讀物方面的不足。 希望本套書的出版,能夠給那些學有余力的中學生、計算機專業的大學生、程序算法愛好者以及IT從業者提供一個學習計算機科學的機會。 為什么要學習算法? 經常有人說: 我不學算法也照樣可以編程寫軟件。那么,為什么還要學習算法呢? 首先,算法(algorithm)一詞源于算術(algorism),具體地說,算術方法是一個由已知推求未知的運算過程。后來,人們把它推廣到一般,即把進行某一工作的方法和步驟稱為算法。一個程序要完成一個任務,其背后肯定要涉及算法的實現,算法的優劣,直接決定了程序的優劣,因此,算法是程序的靈魂。學好了算法,就能夠設計出更加有效的軟件,以最為有效的方式完成復雜的功能。例如設計完成一個具有較強人工智能的人機對弈棋類游戲,程序員沒有深厚的算法功底是根本不可能實現的。 其次,算法是對事物本質的數學抽象,是初等數學、高等數學、線性代數、計算幾何、離散數學、概率論、數理統計和計算方法等知識的具體運用。真正學懂計算機的人(不只是“編程匠”)都對數學有相當的造詣,既能用科學家的嚴謹思維來求證,也能用工程師的務實手段來解決問題——而這種思維和手段的最佳演繹就是“算法”。學習算法,能鍛煉我們的思維,使思維變得更清晰、更有邏輯,變得更有深度和廣度。學習算法更是培養邏輯推理能力的非常好的載體之一。因此,學會算法思想,其意義不僅僅在算法本身,更重要的是,對日后的學習生活和思維方式也會產生深遠的影響。 最后,學習算法本身很有意思、很有趣味。所謂“技術做到極致就是藝術”,當一個人真的沉浸到算法研究里時,他會感受到一個個精妙絕倫的算法的藝術之美,他會為它的驚人的運行速度和巧奪天工的構思而深深震撼,并從中體會到一種不可言喻的美感和愉悅。當然,算法的那份優雅與精巧雖然吸引人,卻也令很多人望而生畏。事實證明,對很多人來說,學習算法是一件很痛苦的事情。 本套書的特色 本套書的第一個特點是具備一定理解能力的讀者可以憑自學看懂書中的多數內容。由于地區的不平衡性等原因,很多算法競賽選手及算法愛好者面對的一個最大難題是沒有合適的教材以及找不到合適的導師給予引導。考慮到這種情況,本書作者盡可能地對書中每一個可能的難點和重點都進行了不厭其煩、深入仔細的講解,此外,書中的絕大多數題目均附有帶注釋的完整源代碼及測試數據供讀者參考和檢測。當然,不管怎樣,你永遠也不要指望閱讀一本算法書能像閱讀一本通俗小說那般輕松愜意。 本套書的第二個特點摒棄了一些算法書過于“學究氣”,片面強調學術性、嚴謹性而忽略了可讀性的“四平八穩”的表述手法,代之以輕松、活潑、搞笑的故事情節和穿插以歷史、文化、科技等要素的情境導入,讀者不僅在學習過程中獲得編程的樂趣,還能夠跟隨書中的眾多人物,一同經歷一場奇妙的冒險之旅。本書作者熱切希望讀者不僅最終能夠在計算機科學的領域大展宏圖,更能夠在故事中獲得感悟,對社會、人生、理想、價值和信念等有更深刻的思考和認識。 本套書的第三個特點是絕大多數題目均采用了“多向思考”“一題多解”和“一題多變”的解決方法,其目的主要有三點: 一是為了充分調動讀者思維的積極性,提高綜合運用已學知識解答問題的技能技巧; 二是為了鍛煉讀者思維的靈活性,促進知識和智慧的增長; 三是訓練思維深度和廣度,引導讀者靈活地掌握知識的縱橫聯系,培養和發揮讀者的創造性。所以,這種訓練,決不能簡單地看作是編程技巧的花哨賣弄,而是通過這種訓練,培養讀者思維的敏捷性,促進讀者智力和思維的發展,提高讀者的變通能力與綜合運用所學知識的能力。讀者若能堅持這種思維訓練方法,必能起到意想不到的良好學習效果。 本套書內容簡介 本套書的第一部——《語言及算法入門》,主要介紹在算法競賽中需要用到的C++語言的語法知識及一些簡單算法的運用。但與一般C++語言入門書不同的是,本部書在介紹C++語言的同時,更加側重于數學思維的培養和簡單算法的應用,因此其學習難度遠高于一般市面上的C++語言入門書。書中很多表面看上去似乎非常簡單的題目,由于采取了“一題多解”及“數學求解”等方法,其程序復雜度直線上升。因此這就要求讀者具備一定的數學功底和思維能力,并且需要花費相當長的時間去思考和練習,才可能深刻理解題目的本質和內涵。此外,為了防止初學者原封不動地照抄源代碼而不理解代碼真實含義的“惡習”,書中凡可寫可不寫源代碼的地方,一律采用偽代碼形式表述,當然,在出版社網站上,讀者可以下載到書中所有的源代碼及測試數據等資源。 本套書的第二部——《基礎算法藝術》,重點介紹了各種基礎算法,如分治算法、貪心算法、枚舉算法、動態規劃算法等。書中的絕大多數題目都采用了“多向思考”、“一題多解”和“一題多變”的方式來解決。讀者不僅可以通過出版社網站下載的簡單測試數據驗證所寫程序的正確性,還可以根據書中標注的題目原始出處,訪問相關的在線評測網站提交所寫代碼進行測試。需要注意的是,與多數教材從頭讀到尾的習慣不同的是,本書的各章節劃分并不是嚴格按從難到易、從簡到繁的順序編排,各章節基本都可以獨立閱讀,互不影響。讀者在閱讀過程中,有時可根據需要翻到其他章節學習完相關內容后再返回本章節繼續學習。此外,每一道題的各種算法按難易程度粗略地以★號表示,★號越多,表示難度越大,讀者若遇到難度過大的題,不必硬“啃”,完全可以在學習完其他章節的相關內容后再來學習。 本套書的第三部——《基礎數據結構》,詳細介紹了鏈表、堆棧、隊列、樹、圖等基礎數據結構的相關知識。為了便于讀者的理解,本書對數據結構眾多知識點進行了詳細的解釋和分析,隨書還配有難易適中的練習題。本書中的多數題目未配置相應測試數據,讀者編寫的代碼正確與否,需要去相關的在線評測網站提交代碼進行測試。這樣做是培養讀者善于應用無限網絡資源的能力,使讀者能逐漸脫離書本的束縛,最終達到獨立、自主學習的目的。 全套書中以調侃化的形式出現的公司和人名等,均為故事情節而服務,與現實無更多關聯。 適合閱讀本書的讀者 本套書可作為全國青少年信息學奧林匹克聯賽(NOIP)系列的復賽教材及ACM國際大學生程序設計競賽(ACM/ICPC)的參考和學習用書,還可作為計算機系學生、IT工程師、科研人員、算法愛好者的參考和學習用書。 致謝 感謝原烏魯木齊高級中學(前身為烏魯木齊市第六中學)的李念、劉悠然、朱生龍、陸智、李智杰、劉毅東、呂亞偉、徐兆鵬、戴文軒、杜同心、胡亞欣、徐菲鵬、戴維、張歡、鄭斐、彭胡杰、肖陽等同學; 感謝浙江省瑞安中學錢瑞源、潘偉達、張元煌、周望威、林展、楊豐、張穎潔、盧眾意、沈小洲、肖煜偉、鄭立言、金澤豪、章奎亮、蔡子豪、陳云帆、方佳豪、陳士俊、李心怡、孫一言、蔡凡、黃海同、王絡、肖瑞宇、潘洲陽、陳可、張夏悅、陳振哲、林江浩、魏書揚等同學,他們在我的指導下,用簡潔易懂的程序代碼實現了本書的部分算法。 感謝全國各省市中學、大學的信息學奧賽指導師們,他們給本套書提了許多真誠而有益的建議,并對本人在寫書過程中遇到的一些困惑和問題給予了熱心的解答。 感謝浙江省瑞安中學為本人搭建的學習、研究、競賽的平臺以及對本人工作的大力支持。 本套書在完成過程中,使用了NOIP的部分原題、在線評測網站的部分題目,并參考和收集了其他創作者發表在互聯網、雜志等媒體上的相關資料,無法一一列舉,在此一并表示衷心感謝。 最后,感謝我的女兒,你是我完成這套書的動力,因為這套書專為你而寫。 最后要說的話 本套書花費了本人巨大的精力和時間,這些年來的多數閑暇時間,都用在了這套書的編寫和反復校驗上。但盡管如此,由于時間和水平所限,書中難免存在不妥和錯誤之處,歡迎同仁或讀者賜正,如果在閱讀中發現任何問題,請發送電子郵件到hiapollo@sohu.com告訴本人,更希望讀者對本書提出建設性意見,以便修訂再版時改進。 張新華 2014年8月于浙江瑞 |