ACM/ICPC程序設(shè)計(jì)與分析

前言

　　國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM Intcrnational Collegiate Programming Contest，ACM／ICPC）是由頗具權(quán)威性的美國(guó)計(jì)算機(jī)協(xié)會(huì)（Association for Computing Machinery，ACM）主辦的、世界上公認(rèn)的規(guī)模最大、水平最高的國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽，旨在使大學(xué)生通過(guò)編程充分展示自己分析問(wèn)題和解決問(wèn)題的能力。該項(xiàng)競(jìng)賽從1970年舉辦至今已有30多屆，分區(qū)域預(yù)賽和國(guó)際決賽兩個(gè)階段進(jìn)行。ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽已成為在世界各國(guó)大學(xué)生中最具影響力的國(guó)際級(jí)計(jì)算機(jī)類的賽事，是廣大愛(ài)好計(jì)算機(jī)編程的大學(xué)生展示才華的舞臺(tái)，是著名大學(xué)計(jì)算機(jī)教育成果的直接體現(xiàn)，是信息企業(yè)與世界頂尖計(jì)算機(jī)人才對(duì)話的最好機(jī)會(huì)。　　1996年上海大學(xué)將ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽首次引入中國(guó)大陸，舉辦了首屆亞洲區(qū)預(yù)選賽中國(guó)大陸賽區(qū)比賽。1996-2001年間，共6屆比賽賽區(qū)設(shè)在上海，均由上海大學(xué)主辦。2002年起每年分別由國(guó)內(nèi)的2-5所高校輪流主辦亞洲區(qū)預(yù)選賽。　　隨著ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽在中國(guó)大陸的蓬勃開(kāi)展，一些高校在程序設(shè)計(jì)類課程（高級(jí)語(yǔ)言程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)與分析等）方面進(jìn)行了一系列的教學(xué)改革，將程序設(shè)計(jì)類課程進(jìn)行整合，并紛紛推出了網(wǎng)上在線判題系統(tǒng)，注重學(xué)生平時(shí)的實(shí)踐，強(qiáng)調(diào)學(xué)生的自主學(xué)習(xí)和上機(jī)實(shí)踐，并按ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽的模式進(jìn)行課程考核。同時(shí)，學(xué)生在學(xué)過(guò)程序設(shè)計(jì)語(yǔ)言課程后有進(jìn)一步提高程序設(shè)計(jì)能力的要求，在學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)與分析后進(jìn)行在線判題系統(tǒng)實(shí)時(shí)解題的計(jì)劃，甚至有參加各種程序設(shè)計(jì)競(jìng)賽以更快地提高編程能力的愿望.另外，全國(guó)每年僅參加國(guó)內(nèi)主辦的亞洲區(qū)域預(yù)賽的參賽隊(duì)就達(dá)幾千支，而參加各校舉辦的各類程序設(shè)計(jì)競(jìng)賽的學(xué)生更是眾多。

內(nèi)容概要

　　《ACM/ICPC程序設(shè)計(jì)與分析(C++實(shí)現(xiàn))》介紹ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽概況及程序設(shè)計(jì)基礎(chǔ)，系統(tǒng)介紹數(shù)論、組合數(shù)學(xué)、動(dòng)態(tài)規(guī)劃、計(jì)算幾何、搜索、圖論和網(wǎng)絡(luò)流等專題的典型算法，挑選歷年競(jìng)賽中許多有代表性的競(jìng)賽題作為例題進(jìn)行分析，便于學(xué)生編程時(shí)模仿學(xué)習(xí)。每章的例題和習(xí)題都配有輸入輸出樣例，方便學(xué)生在編程時(shí)測(cè)試與調(diào)試程序?！禔CM/ICPC程序設(shè)計(jì)與分析(C++實(shí)現(xiàn))》以C++為程序設(shè)計(jì)語(yǔ)言，以提高編程能力為目標(biāo)，按照由淺人深、循序漸進(jìn)的原則編寫。　　《ACM/ICPC程序設(shè)計(jì)與分析(C++實(shí)現(xiàn))》不僅適合于計(jì)算機(jī)專業(yè)的學(xué)生，也適合于非計(jì)算機(jī)專業(yè)的學(xué)生。《ACM/ICPC程序設(shè)計(jì)與分析(C++實(shí)現(xiàn))》是問(wèn)題求解性自主式學(xué)習(xí)的程序設(shè)計(jì)教材，也是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)與分析的參考教材，還可以作為ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽的參考書。

書籍目錄

第1章 ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽簡(jiǎn)介1.1 ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽概況1.2 ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽組織形式簡(jiǎn)介1.2.1 組隊(duì)方式和比賽形式1.2.2 競(jìng)賽環(huán)境1.2.3 判題結(jié)果1.2.4 遞交與評(píng)判1.3 程序設(shè)計(jì)對(duì)學(xué)生的要求1.4 程序設(shè)計(jì)語(yǔ)言選擇1.5 ACM程序設(shè)計(jì)競(jìng)賽題形式習(xí)題1第2章 程序設(shè)計(jì)基礎(chǔ)2.1 程序設(shè)計(jì)概述2.2 算法基礎(chǔ)2.2.1 算法概述2.2.2 算法復(fù)雜性2.2.3 演繹方法的使用2.2.4 演繹法算法設(shè)計(jì)舉例2.3 程序設(shè)計(jì)的輸入輸出形式2.4 C++文件操作2.5 輸入輸出格式控制2.5.1 流基類ios層次圖2.5.2 非格式化抽取2.5.3 操縱算子2.6 排序2.6.1 冒泡排序2.6.2 快速排序2.7 簡(jiǎn)單應(yīng)用2.7.1 轉(zhuǎn)換十六進(jìn)制數(shù)2.7.2 顛倒原文2.7.3 指定個(gè)數(shù)的整數(shù)求和2.7.4 不指定個(gè)數(shù)的整數(shù)求和習(xí)題2第3章 程序設(shè)計(jì)簡(jiǎn)單問(wèn)題3.1 ACM／ICPC程序設(shè)計(jì)競(jìng)賽的題型3.2 簡(jiǎn)單例子3.2.1 空格字符與非空格字符統(tǒng)計(jì)3.2.2 荷蘭國(guó)旗問(wèn)題3.2.3 城市間的球面距離3.2.4 合并電話簿3.2.5 圖書排序問(wèn)題習(xí)題3第4章 高精度計(jì)算與代數(shù)計(jì)算4.1 高精度計(jì)算4.1.1 基本知識(shí)4.1.2 高精度數(shù)據(jù)的處理方法4.1.3 高精度四則運(yùn)算的基本處理方法4.2 高精度四則運(yùn)算應(yīng)用4.2.1 A+B問(wèn)題4.2.2 公牛和母牛4.2.3 A一月問(wèn)題4.2.4 計(jì)算余數(shù)問(wèn)題4.3 代數(shù)計(jì)算4.4 實(shí)例研究4.4.1 指數(shù)函數(shù)值4.4.2 是金還是銀4.4.3 p倍和子集問(wèn)題4.4.4 楊輝三角形4.4.5 黑白棋游戲習(xí)題4第5章 數(shù)論中的程序設(shè)計(jì)5.1 從跳獸問(wèn)題談起5.2 最大公因數(shù)與最小公倍數(shù)5.2.1 公因數(shù)和最大公因數(shù)的概念5.2.2 最小公倍數(shù)5.2.3 歐幾里得算法5.3 利用歐幾里得算法求整系數(shù)一次不定方程5.4 求解模線性方程5.4.1 模和同余5.4.2 模線性方程5.5 求modm的逆元素算法5.6 模線性方程組與中國(guó)剩余定理5.7 模冪運(yùn)算與素?cái)?shù)測(cè)試5.7.1 模冪運(yùn)算5.7.2 素?cái)?shù)測(cè)試5.8 二次剩余與Pell方程5.8.1 二次剩余5.8.2 Pell方程5.9 實(shí)例研究5.9.1 MagicHorse5.9.2 階乘問(wèn)題5.9.3 郵票問(wèn)題5.9.4 Josephus問(wèn)題5.9.5 負(fù)數(shù)進(jìn)制轉(zhuǎn)換5.9.6 數(shù)塔問(wèn)題5.9.7 幸運(yùn)數(shù)5.9.8 哥德巴赫猜想習(xí)題5第6章 組合數(shù)學(xué)中的程序設(shè)計(jì)6.1 組合數(shù)學(xué)中有關(guān)概念與公式6.1.1 排列與組合及有關(guān)的生成算法6.1.2 母函數(shù)6.1.3 容斥原理與錯(cuò)排6.1.4 P6lya定理6.2 實(shí)例研究6.2.1 蛋糕6.2.2 楊輝三角形中的奇偶問(wèn)題6.2.3 足球賽票6.2.4 棋盤格數(shù)6.2.5 保險(xiǎn)柜上鎖6.2.6 彈球游戲6.2.7 最少砝碼6.2.8 環(huán)6.2.9 珍珠項(xiàng)鏈6.2.1 0統(tǒng)計(jì)棋局?jǐn)?shù)習(xí)題6第7章 動(dòng)態(tài)規(guī)劃7.1 動(dòng)態(tài)規(guī)劃原理7.2 實(shí)例研究7.2.1 游船費(fèi)問(wèn)題7.2.2 航線設(shè)置7.2.3 復(fù)制書稿7.2.4 括號(hào)序列7.2.5 整數(shù)匹配問(wèn)題7.2.6 生日蛋糕7.2.7 乘積最大7.2.8 多邊形計(jì)算習(xí)題7第8章 計(jì)算幾何學(xué)8.1 幾何基本知識(shí)8.1.1 矢量的概念8.1.2 矢量加減法8.1.3 矢量叉積8.1.4 折線段的拐向判斷8.1.5 判斷點(diǎn)是否在線段上8.1.6 跨立試驗(yàn)與判斷兩線段是否相交8.1.7 整數(shù)點(diǎn)與Pick定理8.2 基本算法8.3 凸包8.3.1 凸包的概念與實(shí)例8.3.2 Graham掃描法8.3.3 Jarvis步進(jìn)法8.3.4 Graham掃描法與Jarvis步進(jìn)法的程序?qū)崿F(xiàn)8.4 實(shí)例研究8.4.1 有缺陷的衛(wèi)星8.4.2 籬笆8.4.3 處于危險(xiǎn)之中的飛行員8.4.4 穿街走巷8.4.5 三角形習(xí)題8……第9章 搜索算法第10章 一般圖論中的程序設(shè)計(jì)第11章 網(wǎng)絡(luò)流與二分圖第12章 雜例

章節(jié)摘錄

　　ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM Intcrnational Collegiate Programming Contest，ACM／ICPC）是由頗具權(quán)威性的美國(guó)計(jì)算機(jī)協(xié)會(huì)（Association for Computing Machinery，ACM）主辦的，是世界上公認(rèn)的規(guī)模最大、水平最高的國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽，是計(jì)算機(jī)界的奧林匹克比賽。該項(xiàng)競(jìng)賽從1970年起至2009年已舉辦30多屆。歷年來(lái)這樣的競(jìng)賽都薈萃了世界各大洲的精英，云集了計(jì)算機(jī)界的“希望之星”，因而該賽事受到國(guó)際各知名大學(xué)的重視，并受到全世界各著名計(jì)算機(jī)公司的高度關(guān)注。　　此項(xiàng)賽事的目的是大學(xué)生運(yùn)用計(jì)算機(jī)編程平臺(tái)，充分展示自己分析問(wèn)題和解決問(wèn)題的能力，團(tuán)隊(duì)合作精神以及他們?cè)诔绦蛟O(shè)計(jì)過(guò)程中的創(chuàng)新意識(shí)，同時(shí)也是檢測(cè)學(xué)生們?cè)趬毫ο逻M(jìn)行開(kāi)發(fā)活動(dòng)的能力?？梢哉f(shuō)，ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽是參賽學(xué)生展示計(jì)算機(jī)才華的廣闊舞臺(tái)，是大學(xué)計(jì)算機(jī)教育成果的直接體現(xiàn)，是IT企業(yè)與世界頂尖計(jì)算機(jī)人才對(duì)話的最好機(jī)會(huì)。該項(xiàng)競(jìng)賽分區(qū)域預(yù)賽和世界總決賽兩個(gè)階段進(jìn)行，世界總決賽安排在每年的3-4月舉行，而區(qū)域預(yù)賽安排在上一年的9－12月在各大洲舉行。另外，為配合世界總決賽和洲區(qū)域預(yù)賽，也有稱為地區(qū)二級(jí)預(yù)賽的國(guó)家賽、省級(jí)賽、學(xué)校選拔賽以及邀請(qǐng)賽。IBM公司已連續(xù)多年贊助該項(xiàng)賽事的世界總決賽和區(qū)域預(yù)賽，而一些企業(yè)也爭(zhēng)相贊助，使ACM賽事在各大洲蓬勃開(kāi)展。

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    ACM/ICPC程序設(shè)計(jì)與分析 PDF格式下載

---