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

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

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

1ACM/ICPC

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

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

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

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

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

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

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

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

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

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

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

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

3程序設計的常用思維方式

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

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

(1) 整體實現(xiàn)的關鍵是準確地應用必要條件。

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

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

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

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

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

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

4本書的體例結構

本書介紹的內容豐富而深入，所采用的敘述結構大致如下:

思維方法1 (1～6)

知識點1

經典例題1

思路點撥

解題思路分析

算法1

算法分析

程序實例

算法2

……

經典例題2

……

小結

知識點2

……

思維方法2

……

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

本書各個知識點的“小結”內容是很值得推薦閱讀的部分，作者以精準的語言扼要地概括了本部分的知識內容，仔細閱讀和認真思考，將起到事半功倍的效果。

5圖書相關信息

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

作者:吳文虎王建德編著

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

頁數(shù):278

定價:42.0元

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

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

郵編:100054

責編:秦緒好

裝幀:精裝

出版年:2009-7

6主要內容(目錄)

第1章正確認識和處理整體與部分的關系

1.1整體實現(xiàn)的關鍵是準確地應用必要條件

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

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

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

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

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

1.2.2根據問題的本質構造守恒量

1.2.3在交互問題中構造變化中的不變量

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

1.3.1計算過程中充分利用有效信息

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

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ù)據關系

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章逆向思維

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

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

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

5.2由反及正型逆向思維

5.2.1割補法

5.2.2在統(tǒng)計問題中應用補集轉化

第6章猜想與試驗

6.1相似聯(lián)想

6.1.1與熟悉的問題類比

6.1.2與特殊的問題類比

6.2歸納聯(lián)想

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

6.2.2歸納聯(lián)想的實際應用

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

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

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

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

7推薦指數(shù)

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

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

8作者簡介

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

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

參考文獻:

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