培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版][Pei Yang Yu Duan Lian Cheng Shi She Ji De Luo Ji Nao ： Shi Jie...]～推薦！

作者：秋葉拓哉,岩田陽一,北川宜稔
出版社：博碩
出版日期：2013/11/21
語言：繁體中文

ISBN：9789862017777
叢書系列：單行本
規格：平裝/432頁/17x23cm/普通級/單色印刷/二版
出版地：台灣
本書分類：電腦資訊>程式設計>資料結構/演算法

【Author】作者/繪者/著者/譯者

作者簡介

秋葉拓哉

　　1988年出生。2007年進入東京大學就讀。以iwi的身份活躍於程式編譯大賽中。主要的戰績為TopCoder Open 2010第9名、ACM-ICPC World Finals 2012第11名、TopCoder Open 2012 Algorithm第4名等。

岩田陽一

　　1988年出生。2007年進入東京大學就讀。以wata的身份活躍於程式編譯大賽中。主要的戰績為Google Code Jam 2009第3名、TopCoder Open 2010 Marathon冠軍、IPSC 2010個人組冠軍等。

北川宜稔

　　1988年出生。2007年進入東京大學就讀。以kita_masa的身份活躍於程式編譯大賽中。主要的戰績為ICPC World Finals 2010第16名等。

【Introduction】簡介/書評/特色/摘要

CPE！ CPE！ CPE！

　　就要考CPE了，仍毫無頭緒？那麼多的題目，要怎麼準備啊？

　　雖然已經有資料結構和基礎演算法的底子，嘗試解考古題時，仍然腦袋中一片空白！完全發揮不出原本的實力！

　　您有以上的困擾嗎？那就快來看看這本書。

　　CPE的考題大多來自於各大程式設計競賽，題目眾多，若不先經過專家的整理與歸類，確實難以準備！

　　本書分析了各大程式設計競賽的題目，將之區分類別與難易度，按照循序漸進的方式，引導您逐步解題，提示您看到哪類題目時，應該如何思考，可以套用那些資料結構與演算法，讓您在CPE考試中無往不利！

　　延續第一版暢銷的寫法，在[第二版]中，作者新增了約1/4的內容，這些內容大多集中於中級篇及高級篇，並且納入了簡單的人工智慧搜尋解法，引入heuristic function h(n)的觀念，以剪枝、A*與IDA*來解出時間要求更嚴格的考題。對於沒有學習過類似解法的考生而言，幫助著實不小。

　　您還在煩惱如何在CPE考試中取得高分嗎？或者您想要參加國際型的程式競賽以取得升學的加分優勢呢？本書將協助您、完成您的夢想！

本書特色

　　■ 內容淺顯易懂，在有趣愉快的學習下重新釐清重要概念
　　■ 依困難度和關聯性的方式編排，讓讀者分階段進行學習
　　■ 透過考古題與原創題目的試作，挑戰自我程式設計能力
　　■ 只需具備基礎的程式設計概念，本書就能輕鬆閱讀上手
　　■ 匯集了作者參加程式設計比賽所取得的解題技巧和經驗

【Table of Contents】目錄/大綱/內容概要

01 開始挑戰吧！但在這之前?準備篇
1-1 程式設計比賽是什麼？
1-2 有哪些比賽呢？
1-3 本書的學習方式
1-4 該如何提交解答呢？
1-5 以有效率的演算法為目標
1-6 輕鬆的暖身運動

02 從基礎開始吧！初級篇
2-1 一切的基礎「完全搜尋法」
2-2 突飛猛進！「貪心法」
2-3 記錄值並重新利用的「動態規劃法」
2-4 加工資料並記憶的「資料結構」
2-5 這個與那個其實都是「圖」
2-6 解決數學問題的要訣
2-7 挑戰看看GCJ的問題吧(1)

03 大幅提升程度！中級篇
3-1 不是只能搜尋值而已喔！「二分搜尋法」
3-2 嚴選！常用技巧(1)
3-3 操縱各式各樣的資料結構
3-4 掌握動態規劃法！
3-5 藉由流水解決問題的「網路流量」
3-6 處理平面．空間的「計算幾何」
3-7 挑戰看看 GCJ 的問題吧(2)

04 超越巔峰！高級篇
4-1 更加複雜的數學問題
4-2 找出遊戲的必勝法！
4-3 圖論大師的修鍊之道
4-4 嚴選！常用技巧(2)
4-5 別出心裁的智慧探索
4-6 分開求解再合併！「分治法」
4-7 華麗地操作字串
4-8 挑戰看看 GCJ 的問題吧(3)

ISBN：9789862017777
叢書系列：單行本
規格：平裝/432頁/17x23cm/普通級/單色印刷/二版
出版地：台灣
本書分類：電腦資訊>程式設計>資料結構/演算法

【Preview】內容預覽/連載/試閱PDF下載

Page1

首先讓我們從簡單的Ants問題開始

問題

n隻螞蟻在長度為L公分的竿子上以每秒1公分的速度行走。螞蟻走到竿子底端便會摔到竿子底下。另外，竿子很窄，不能讓兩隻螞蟻同時走過，所以當兩隻螞蟻相遇時，就必須各自往反方向走回去。關於每一隻螞蟻，只知道牠們位於從竿子左邊算起距離xi的地方，但卻不清楚牠們是朝哪個方向前進。請分別求出所有螞蟻摔到竿子底下的最短時間和最長時間。

輸入

L = 10

n = 3

x = {2,6,7}

輸出

min = 4(左、右、右)

max = 8(右、右、右)

Page2

我們首先會想到的解決方式，就是嘗試所有螞蟻的所有前進方向之演算法。想要進行這種完全搜尋法時，就要利用遞迴函數（詳細的說明請參閱2-1節）。每隻螞蟻的前進方向各有兩種，有n隻螞蟻就有2×2×2⋯×2種走法。雖然n有時候並不會太大，但指數函數會隨著n的增加而急速增加。

完全搜尋法程式的執行時間也會隨著n的增加急速膨脹。這種量級的執行時間通常叫做「指數時間」。指數時間的演算法無法處理過大的輸入規模。

那麼，就來想想有沒有比完全搜尋法更有效率的解決方法吧。首先，最短時間的情況應該是所有螞蟻都朝同方向前進。實際上，在這樣的情況下，任何螞蟻將不會遇到其他螞蟻，所以不會有其他情況能夠更快結束程式。

Page3