出版時間:2009-7 出版社:中國鐵道出版社 作者:吳文虎,王建德 頁數(shù):278
Tag標簽:無
前言
ACM/ICPC是國際計算機協(xié)會組織的國際大學生程序設計競賽的英文簡稱。這項每年一屆的計算機學科競賽始于1976年,是目前規(guī)模最大且最具影響力的全球性高校之間的賽事。每年度的ACM/ICPC賽事從當年的9月份開始,先進行各大洲各地區(qū)的預選賽,從上千所高校的幾千支隊伍中挑選出幾十支優(yōu)勝隊伍。讓這些百里挑一的隊伍在下一年春天參加總決賽,爭奪金銀銅獎和世界冠軍的獎杯。參賽選手由三人組成一隊共用一臺計算機,所以這項賽事與中學生的信息學奧林匹克競賽既有聯(lián)系又有較大區(qū)別,被稱為大學生的信息學奧林匹克。2008—2009年度的ACM/ICPC是第33屆賽事,有1838所大學的7109支隊伍參加分區(qū)賽。經(jīng)過第一階段的預選賽,共有100支隊伍取得決賽資格,于2009年4月18—22日在瑞典斯德哥爾摩舉行全球總決賽。ACM/ICPC這項國際頂級賽事是大學生智力與計算機解題能力的競賽,是大學生展示水平與才華的大舞臺,是著名的高等學府計算機教育成果的直接體現(xiàn),也是IT企業(yè)與世界頂尖計算機人才對話的最佳機會。因而,ACM/ICPC吸引了越來越多的高校參賽,使得參賽隊伍的水平上升很快,賽題的難度也在不斷提高。
內(nèi)容概要
本書是針對世界大學生程序設計競賽(ACM/ICPC)而編寫的參考書?! CM/ICPC是大學生的智力與計算機解題能力的競賽,是世界公認的最具影響力的、規(guī)模最大的國際頂級賽事,被稱為大學生的信息學奧林匹克?! ∮嬎銠C解題的核心是算法設計,而算法設計需要具備良好的數(shù)學素養(yǎng)。數(shù)學具有運用抽象思維去把握實際的能力,應用數(shù)學知識去解決實際問題時的建模過程是一個突出主要因素的科學抽象過程。進行抽象和形式化需要學習和掌握常用的計算思維方式。本書主要介紹了大賽程序設計中的常用思維方式,主要包括正確認識和處理整體與部分的關系、構造性思維、目標轉化的思想、分類與分治思想、逆向思維、猜想與試驗六個章節(jié),旨在引導參賽學生學習并掌握編程解題的一般思維方法和過程,提高解題能力。 本書面向參加世界大學生程序設計競賽(ACM/ICPC)的高等院校學生,也可作為程序設計愛好者的參考用書。
作者簡介
吳文虎,教授1955年—1961年分別就讀于清華大學電機工程系及自動控制系,現(xiàn)為計算機系教授、博士生導師,主要研究方向包括語音識別及語言理解、語音合成、語音信號數(shù)字處理等。吳教授學術水平精湛、教學水平高超、教學經(jīng)驗豐富。多年來用對學生無私的愛詮釋了最好的師恩師德
書籍目錄
第1章 正確認識和處理整體與部分的關系 1.1 整體實現(xiàn)的關鍵是準確地應用必要條件 1.1.1 選擇有助于簡化問題、變難為易的必要條件 1.1.2 合成必要條件,從整體結構上優(yōu)化 1.1.3 必要條件與原有模型比較,更新算法 小結 1.2 整體思考的一個重要角度是“守恒” 1.2.1 從具體問題中抽象出守恒量 1.2.2 根據(jù)問題的本質(zhì)構造守恒量 1.2.3 在交互問題中構造變化中的不變量 小結 1.3 提高整體實現(xiàn)效率的基本途徑是“充分利用有效信息”和“壓縮冗余信息” 1.3.1 計算過程中充分利用有效信息 1.3.2 通過“壓縮法”消除冗余的圖形和數(shù)據(jù)信息 小結 1.4 改善整體性能狀態(tài)的基礎是處理好細節(jié)問題 1.4.1 必須解決導致錯誤結果的細節(jié)問題 1.4.2 爭取降低算法時間復雜度的階 1.4.3 注意降低算法時間復雜度的系數(shù) 小結第2章 構造性思維 2.1 模型的基本概念 2.1.1 模型的一般特點與功能 2.1.2 模型的一般分類 2.1.3 模型與信息原型間的關系 小結 2.2 建模的一般方法 2.2.1 建模的機理分析方法 2.2.2 建模的統(tǒng)計分析法 小結 2.3 建模的一般思維方式 2.3.1 直接構造法 2.3.2 分類構造法 2.3.3 歸納構造法 小結 2.4 在建模過程中注意應用序關系 2.4.1 在交互式問題中應用序 2.4.2 利用典型的“序”關系簡化問題 2.4.3 尋找蘊涵在題意中的序關系 小結 2.5 模型選擇 小結第3章 目標轉化的思想 3.1 “降維”——縮小目標 3.1.1 引入“降維思想” 3.1.2 高維降為低維 3.1.3 一般降為特殊 3.1.4 抽象降為具體 3.1.5 整體降為局部 3.1.6 簡化數(shù)據(jù)關系 小結 3.2 “升維”——放大目標 3.2.1 讓步假設 3.2.2 倍增思想 小結第4章 分類與分治思想 4.1 應用于一般有序序列的二分法 4.1.1 在給定的序列中“二分查找” 4.1.2 在交互式問題中應用“二分插入” 小結 4.2 應用于退化了的有序序列的“二分枚舉” 4.2.1 用二分枚舉求可行方案 4.2.2 用二分枚舉求最優(yōu)性問題 小結 4.3 應用于無序序列的“二分搜索” 4.3.1 在“二分搜索”的基礎上構造可行解 4.3.2 在“二分搜索”的基礎上構造最優(yōu)解 小結 4.4 應用于多維情況的“多重二分” 小結第5章 逆向思維第6章 猜想與試驗
章節(jié)摘錄
插圖:總共有n級臺階,一些臺階上有你的若干士兵。把所有的士兵分成兩組,然后敵人會告訴你哪一組士兵留下,哪一組士兵被消滅。接著,那些留下的士兵上一個臺階。然后你把剩下的士兵重新分組,敵人再次選擇一組留下;留下的士兵又上一個臺階。如此反復,如果最后有一個士兵登頂,也就是踏上了第n級臺階,你就贏了;如果士兵全部被消滅完,你就輸了?,F(xiàn)在輸入臺階數(shù)療、每一層臺階上的士兵數(shù)和留下的組別標志(1或2)。你的任務是通過適當?shù)姆纸M,爭取獲勝。如果能夠獲勝,則輸出登頂?shù)氖勘鴶?shù);否則輸出失敗信息。
編輯推薦
《世界大學生程序設計競賽(ACM/ICPC)高級教程(第1冊):程序設計中常用的計算思維方式》是針對世界大學生程序設計競賽(ACM/ICPC)而編寫的參考書?!妒澜绱髮W生程序設計競賽(ACM/ICPC)高級教程(第1冊):程序設計中常用的計算思維方式》面向參加世界大學生程序設計競賽(ACM/ICPC)的高等院校學生,也可作為程序設計愛好者的參考用書。
圖書封面
圖書標簽Tags
無
評論、評分、閱讀與下載