培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版][Pei Yang Yu Duan Lian Cheng Shi She Ji De Luo Ji Nao ： Shi Jie...]＊電腦資訊類＊～新書推薦！
|
作者：秋葉拓哉,岩田陽一,北川宜稔 ISBN：9789862017777
|
|
【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
接著，再來想想哪種情況會讓程式時間拉得最長，而螞蟻的相遇情況又會是如何吧。
其實即使把螞蟻看成是「直接交錯而過」也不會有問題。只要這樣一想，就可以把所有螞蟻都當成是獨立活動，只要求取各螞蟻到達竿子邊緣的最大距離，就能求出時間的最大值了。
如果要這樣演算的話，不管是求最大值還是最小值，都只需要調查所有螞蟻一次就行了，而演算法複雜度會是O(n)。從「n≦1000000」這個限制可知，這個演算法一定來得及在限制時間內完成，這樣就解決這個問題了。
這個題目可說是考驗參賽者發想力的最佳問題。有些問題就像這樣，乍看之下很難，但想一下就會發現它意外地簡單。
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_bc_01.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_01.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_02.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_03.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_04.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_05.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_06.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_07.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_08.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_09.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_10.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_b_11.jpg)
![►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]](http://www.books.com.tw/img/001/061/69/0010616945_bf_01.jpg)
ISBN：9789862017777
叢書系列：單行本
規格：平裝/432頁/17x23cm/普通級/單色印刷/二版
出版地：台灣
本書分類：電腦資訊>程式設計>資料結構/演算法
►博客來►特價►》培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版]
【Customers Who Bought This Item Also Bought】相關書籍，推薦書單... |
培養與鍛鍊程式設計的邏輯腦：世界級程式設計大賽的知識、心得與解題分享 [第二版][Pei Yang Yu Duan Lian Cheng Shi She Ji De Luo Ji Nao ： Shi Jie...]＊電腦資訊類＊
資料來源:[博客來BOOKS網路書店] http://www.books.com.tw/exep/assp.php/ap/products/0010616945?utm_source=ap&utm_medium=ap-books&utm_content=recommend
圖文屬原創所有。相關資訊僅供參考，歡迎前往選購。
文章標籤
全站熱搜
留言列表
{{ article.title }}
