感受數(shù)學(xué)思維與算法藝術(shù)之美

ACM/ICPC是國際計(jì)算機(jī)協(xié)會(Association for Computing Machinery)組織的國際大學(xué)生程序設(shè)計(jì)競賽(International Collegiate Programming Contest)，這項(xiàng)每年一屆的計(jì)算機(jī)學(xué)科競賽始于1976年，是大學(xué)生智力與計(jì)算機(jī)解題能力的競賽，是世界公認(rèn)的、目前全球高校之間規(guī)模最大且最具影響力的國際頂級賽事。

由清華大學(xué)吳文虎、王建德編著的《世界大學(xué)生程序設(shè)計(jì)競賽(ACM/ICPC)高級教程 第一冊 程序設(shè)計(jì)中常用的計(jì)算思維方式》(以下簡稱《計(jì)算思維方式》)就是針對世界大學(xué)生程序設(shè)計(jì)競賽(ACM/ICPC)而編寫的參考書，該書面向參加ACM/ICPC的高等院校學(xué)生，也可作為程序設(shè)計(jì)愛好者的參考用書。同時，也向講授程序設(shè)計(jì)及相關(guān)課程的教師推薦此書，建議認(rèn)真一讀。

1ACM/ICPC

ACM/ICPC是高等院校計(jì)算機(jī)教育成果的直接體現(xiàn)，是大學(xué)生展示水平與才華的大舞臺，也是IT企業(yè)與世界頂尖計(jì)算機(jī)人才對話的最佳機(jī)會。因而，ACM/ICPC吸引了越來越多的高校參賽，使得參賽隊(duì)伍的水平上升很快，賽題的難度也在不斷提高。

每年度的ACM/ICPC賽事從當(dāng)年9月份開始，先進(jìn)行各大洲各地區(qū)的預(yù)選賽，從上千所高校的幾千支隊(duì)伍中挑選出幾十支優(yōu)勝隊(duì)伍。讓這些百里挑一的隊(duì)伍在下一年春天參加總決賽，爭奪金銀銅獎和世界冠軍的獎杯。參賽選手由三人組成，一隊(duì)共用一臺計(jì)算機(jī)。這項(xiàng)賽事與中學(xué)生的信息學(xué)奧林匹克競賽既有聯(lián)系又有較大區(qū)別，被稱為大學(xué)生的信息學(xué)奧林匹克。以2008～2009年度的ACM/ICPC為例，這是第33屆賽事，有1838所大學(xué)的7109支隊(duì)伍參加分區(qū)賽。經(jīng)過第一階段的預(yù)選賽，共有100支隊(duì)伍取得決賽資格，于2009年4月18日—22日在瑞典斯德哥爾摩舉行全球總決賽。

參加ACM/ICPC的選手需要具備很強(qiáng)的數(shù)學(xué)建模功底、廣博的算法知識、超強(qiáng)的編程能力以及團(tuán)隊(duì)的合作與協(xié)同能力。ACM/ICPC的勝負(fù)規(guī)則是:答對題目數(shù)量多者占優(yōu);在兩個隊(duì)解題數(shù)量相同的情況下，總用時最少者占優(yōu)，因此解題速度非常關(guān)鍵。如果比賽一開始就能迅速找出競賽中相對簡單的題目并盡快加以解決，隊(duì)伍的成績排名就會占有優(yōu)勢，心理上的壓力也會小些。相反，一開始就沒有選好題，或者所寫的程序總有這樣或那樣的錯誤，要花很多時間去調(diào)試排錯，就會浪費(fèi)寶貴的時間，處于下風(fēng)。

在這種你追我趕的激烈賽場上，比的是誰做得又快又好。競賽過程中第一個重要的環(huán)節(jié)是看題、審題和選題。一開始就選對題，一下子就切入主題是十分重要的。有時第一個環(huán)節(jié)遇到陷阱，“馬失前蹄”，就會導(dǎo)致一籌莫展而步步落后。能否在第一環(huán)節(jié)占上優(yōu)勢取決于實(shí)踐能力和洞察力，而實(shí)踐能力與洞察力的提升需要實(shí)戰(zhàn)，需要經(jīng)驗(yàn)，需要學(xué)懂計(jì)算思維方式和解題策略。

參加ACM/ICPC活動，在與編程高手過招的過程中，可以把知識運(yùn)用的綜合性、靈活性和探索性發(fā)揮到極致，體驗(yàn)和感受數(shù)學(xué)思維與算法藝術(shù)之美，提升科學(xué)思維能力。

2“觀察—聯(lián)想—變換”思維方式

計(jì)算機(jī)解題的核心是算法設(shè)計(jì)，而算法設(shè)計(jì)需要具備良好的數(shù)學(xué)素養(yǎng)。數(shù)學(xué)具有運(yùn)用抽象思維去把握實(shí)際的能力，應(yīng)用數(shù)學(xué)知識去解決實(shí)際問題時的建模過程是一個突出主要因素的科學(xué)抽象過程。進(jìn)行抽象和形式化需要學(xué)習(xí)和掌握常用的計(jì)算思維方式。

科學(xué)思維能力的提高是成就事業(yè)最重要的因素之一，本書作者希望能在這方面對讀者起到幫助作用。

編程解題的一般思維方法或過程，可以概述為“觀察—聯(lián)想—變換”，即通過對問題的觀察，認(rèn)識和理解該問題;然后通過聯(lián)想，尋找該問題同已有知識和經(jīng)驗(yàn)之間的聯(lián)系;最后通過變換，把該問題轉(zhuǎn)化為另一個或幾個易于解決的新問題，最終達(dá)到解決原問題的目的。

“觀察”是人類認(rèn)識客觀事物的基本途徑，就編程解題而言，“觀察”是“聯(lián)想”和“變換”的基礎(chǔ)。一般地說，通過觀察應(yīng)當(dāng)明確:求解的對象是什么;是枚舉方案還是回答哪個存在性問題;已知的條件(包括隱含條件) 是什么;能否用遞推公式、遞歸公式、約束規(guī)則或狀態(tài)轉(zhuǎn)移方程把問題的條件、結(jié)論和求解途徑表示出來;問題所涉及的這些計(jì)算式子各有什么特點(diǎn)等。

“聯(lián)想”是由某種對象而引出其他相關(guān)對象的思維形式。就編程解題而言，“聯(lián)想”的目的在于為“變換”提供可能的方向或線索。一般地說，在“觀察”的基礎(chǔ)上，通過聯(lián)想應(yīng)當(dāng)明確:以前是否解過這類試題;是否解答過與其類似而又稍有不同的試題;是否解答過與其有關(guān)的問題;能否利用解答這些問題時所使用的解題方法或所得到的結(jié)果;能否回憶出某個可能用得上的定理、公式或解題思路;為了能利用它，是否應(yīng)當(dāng)改變條件或結(jié)論的表現(xiàn)形式等。

“變換”是編程解題的基本手段。在“觀察”和“聯(lián)想”的基礎(chǔ)上，有目的地對問題實(shí)施“變換”，把原問題轉(zhuǎn)化為另一個或幾個易于解決的新問題，這是編程解題成功的關(guān)鍵。為此，變換時，應(yīng)當(dāng)遵循如下三條基本的思考原則:熟悉化原則、簡單化原則以及和諧化原則。

3程序設(shè)計(jì)的常用思維方式

為了使讀者對“觀察—聯(lián)想—變換”的思維方法和過程有一個比較全面深入的了解，本書歸納了大賽程序設(shè)計(jì)中六種常用的思維方式，主要包括正確認(rèn)識和處理整體與部分的關(guān)系、構(gòu)造性思維、目標(biāo)轉(zhuǎn)化的思想、分類與分治思想、逆向思維、猜想與試驗(yàn)六個章節(jié)，旨在引導(dǎo)參賽學(xué)生學(xué)習(xí)并掌握編程解題的一般思維方法和過程，提高解題能力。

在“觀察”上，提出了整體與部分的思想，包括:

(1) 整體實(shí)現(xiàn)的關(guān)鍵是準(zhǔn)確地應(yīng)用必要條件。

(2) 整體思考的一個重要角度是“守恒”，即尋找變化中的不變量。

(3) 提高整體實(shí)現(xiàn)效率的途徑是“充分利用有效信息”和“壓縮冗余信息”。

(4) 改善整體的性能狀態(tài)的基礎(chǔ)是處理好細(xì)節(jié)問題。

在“聯(lián)想”上，提出了逆向思維和猜想與試驗(yàn)，分析了“執(zhí)果索因型”的逆向思維和“由反及正型”的逆向思維;探討了四種聯(lián)想方式:相似聯(lián)想、歸納聯(lián)想、從數(shù)與形的結(jié)合上聯(lián)想和“回到起點(diǎn)”重新聯(lián)想。指出猜想是在深入分析問題的基礎(chǔ)上，不懈探索、反復(fù)修正的過程。

在“變換”上，提出了構(gòu)造性思維、目標(biāo)轉(zhuǎn)化思想、分類與分治思想。構(gòu)造性思維包括建立模型的機(jī)理分析法和統(tǒng)計(jì)分析法;建模過程注意應(yīng)用序關(guān)系;選擇模型時必須權(quán)衡四個因素:“時間復(fù)雜度、空間復(fù)雜度、編程復(fù)雜度和思維復(fù)雜度”。目標(biāo)轉(zhuǎn)化思想包括縮小目標(biāo)的“降維”思想和放大目標(biāo)的“升維”思想;分類與分治思想包括應(yīng)用于一般有序序列的“二分查找”;應(yīng)用于退化了的有序序列的“二分枚舉”;應(yīng)用于無序序列的“二分搜索”;應(yīng)用于多維情況的“多重二分”。

在實(shí)際編程解題時，“觀察”、“聯(lián)想”、“變換”等思想活動總是互相聯(lián)系、互相影響、互相交織地進(jìn)行著，形成了一個有機(jī)的整體。本書列舉的六種思維方式是互相滲透的，章節(jié)劃分主要是依據(jù)各種思維方式的主要特征進(jìn)行分類，同時也是為了敘述的方便。當(dāng)然這六種思維方式并沒有、也不可能窮盡編程解題過程中的所有思維活動，它只不過是列舉了常用的一些思維方式，為“觀察—聯(lián)想—變換”的思維活動勾勒出一個基本輪廓，為讀者留下學(xué)習(xí)、探索和再創(chuàng)造的空間。

4本書的體例結(jié)構(gòu)

本書介紹的內(nèi)容豐富而深入，所采用的敘述結(jié)構(gòu)大致如下:

思維方法1 (1～6)

知識點(diǎn)1

經(jīng)典例題1

思路點(diǎn)撥

解題思路分析

算法1

算法分析

程序?qū)嵗?/p>

算法2

……

經(jīng)典例題2

……

小結(jié)

知識點(diǎn)2

……

思維方法2

……

書中選擇了大量的經(jīng)典例題，這些題目對于豐富程序設(shè)計(jì)課程教師的教學(xué)案例也很有幫助。所選取案例大都具有一定的趣味性，有助于提高讀者的閱讀和實(shí)踐練習(xí)的興趣，提高實(shí)踐效果。因此，可以說，雖然本書的編寫主要針對ACM/ICPC，但對于高等院校程序設(shè)計(jì)教學(xué)水平的提高，促進(jìn)程序設(shè)計(jì)教學(xué)質(zhì)量和教學(xué)改革發(fā)展具有積極的意義。

本書各個知識點(diǎn)的“小結(jié)”內(nèi)容是很值得推薦閱讀的部分，作者以精準(zhǔn)的語言扼要地概括了本部分的知識內(nèi)容，仔細(xì)閱讀和認(rèn)真思考，將起到事半功倍的效果。

5圖書相關(guān)信息

書名:《世界大學(xué)生程序設(shè)計(jì)競賽(ACM/ICPC) 高級教程(第一冊) 程序設(shè)計(jì)中常用的計(jì)算思維方式》

作者:吳文虎王建德編著

ISBN:978-7-113-10134-3/ TP#61590;3344

頁數(shù):278

定價:42.0元

出版社:中國鐵道出版社(計(jì)算機(jī)圖書批銷部)

北京市宣武區(qū)右安門西街8號

郵編:100054

責(zé)編:秦緒好

裝幀:精裝

出版年:2009-7

6主要內(nèi)容(目錄)

第1章正確認(rèn)識和處理整體與部分的關(guān)系

1.1整體實(shí)現(xiàn)的關(guān)鍵是準(zhǔn)確地應(yīng)用必要條件

1.1.1選擇有助于簡化問題、變難為易的必要條件

1.1.2合成必要條件，從整體結(jié)構(gòu)上優(yōu)化

1.1.3必要條件與原有模型比較，更新算法

1.2整體思考的一個重要角度是“守恒”

1.2.1從具體問題中抽象出守恒量

1.2.2根據(jù)問題的本質(zhì)構(gòu)造守恒量

1.2.3在交互問題中構(gòu)造變化中的不變量

1.3提高整體實(shí)現(xiàn)效率的基本途徑是“充分利用有效信息”和“壓縮冗余信息”

1.3.1計(jì)算過程中充分利用有效信息

1.3.2通過“壓縮法”消除冗余的圖形和數(shù)據(jù)信息

1.4改善整體性能狀態(tài)的基礎(chǔ)是處理好細(xì)節(jié)問題

1.4.1必須解決導(dǎo)致錯誤結(jié)果的細(xì)節(jié)問題

1.4.2爭取降低算法時間復(fù)雜度的階

1.4.3注意降低算法時間復(fù)雜度的系數(shù)

第2章構(gòu)造性思維

2.1模型的基本概念

2.1.1模型的一般特點(diǎn)與功能

2.1.2模型的一般分類

2.1.3模型與信息原型間的關(guān)系

2.2建模的一般方法

2.2.1建模的機(jī)理分析方法

2.2.2建模的統(tǒng)計(jì)分析法

2.3建模的一般思維方式

2.3.1直接構(gòu)造法

2.3.2分類構(gòu)造法

2.3.3歸納構(gòu)造法

2.4在建模過程中注意應(yīng)用序關(guān)系

2.4.1在交互式問題中應(yīng)用序

2.4.2利用典型的“序”關(guān)系簡化問題

2.4.3尋找蘊(yùn)涵在題意中的序關(guān)系

2.5模型選擇

第3章目標(biāo)轉(zhuǎn)化的思想

3.1“降維”——縮小目標(biāo)

3.1.1引入“降維思想”

3.1.2高維降為低維

3.1.3一般降為特殊

3.1.4抽象降為具體

3.1.5整體降為局部

3.1.6簡化數(shù)據(jù)關(guān)系

3.2“升維”——放大目標(biāo)

3.2.1讓步假設(shè)

3.2.2倍增思想

第4章分類與分治思想

4.1應(yīng)用于一般有序序列的二分法

4.1.1在給定的序列中“二分查找”

4.1.2在交互式問題中應(yīng)用“二分插入”

4.2應(yīng)用于退化了的有序序列的“二分枚舉”

4.2.1用二分枚舉求可行方案

4.2.2用二分枚舉求最優(yōu)性問題

4.3應(yīng)用于無序序列的“二分搜索”

4.3.1在“二分搜索”的基礎(chǔ)上構(gòu)造可行解

4.3.2在“二分搜索”的基礎(chǔ)上構(gòu)造最優(yōu)解

4.4應(yīng)用于多維情況的“多重二分”

第5章逆向思維

5.1執(zhí)果索因型逆向思維

5.1.1設(shè)置結(jié)果參數(shù)，逆向搜索

5.1.2從目標(biāo)狀態(tài)出發(fā)逆向規(guī)劃

5.2由反及正型逆向思維

5.2.1割補(bǔ)法

5.2.2在統(tǒng)計(jì)問題中應(yīng)用補(bǔ)集轉(zhuǎn)化

第6章猜想與試驗(yàn)

6.1相似聯(lián)想

6.1.1與熟悉的問題類比

6.1.2與特殊的問題類比

6.2歸納聯(lián)想

6.2.1歸納聯(lián)想的理論基礎(chǔ)

6.2.2歸納聯(lián)想的實(shí)際應(yīng)用

6.3從數(shù)與形的結(jié)合上聯(lián)想

6.3.1在數(shù)值計(jì)算中聯(lián)想“以形助數(shù)”

6.3.2在幾何計(jì)算中聯(lián)想“以數(shù)助形”

6.4 “回到起點(diǎn)”重新聯(lián)想

7推薦指數(shù)

推薦同行閱讀指數(shù):★★★★★ (注:以★★★★★為最高。)

這是ACM/ICPC高級教程的第一冊，我們期待著后續(xù)教程的盡早面世。

8作者簡介

吳文虎，1955-1961年分別就讀于清華大學(xué)電機(jī)工程系及自動控制系。清華大學(xué)計(jì)算機(jī)系教授、博士生導(dǎo)師，原國際信息學(xué)奧林匹克中國隊(duì)總教練。主要研究方向包括語音識別及語言理解、語音合成、語音信號數(shù)字處理等。

吳教授學(xué)術(shù)水平精湛、教學(xué)水平高超、教學(xué)經(jīng)驗(yàn)豐富。從1989年至今，吳教授作為總教練和領(lǐng)隊(duì)，曾15次帶領(lǐng)中國隊(duì)參加國際信息學(xué)奧林匹克競賽，中國隊(duì)累計(jì)獲金牌51塊，屆屆名列前茅，2002年獲信息學(xué)奧林匹克國際委員會頒發(fā)的“特別貢獻(xiàn)獎”。1997年～2008年，吳教授連續(xù)13年指導(dǎo)清華大學(xué)的學(xué)生進(jìn)入ACM世界大學(xué)生程序設(shè)計(jì)大賽總決賽，多次獲金、銀牌，并于2009年被大賽組委會授予“杰出教練獎”。

參考文獻(xiàn):

[1] 吳文虎，王建德. 世界大學(xué)生程序設(shè)計(jì)競賽(ACM/ICPC)高級教程(第一冊)程序設(shè)計(jì)中常用的計(jì)算思維方式[M]. 北京:中國鐵道出版社，2009-7.