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

《感受數(shù)學(xué)思維與算法藝術(shù)之美》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、感受數(shù)學(xué)思維與算法藝術(shù)之美ACM/ICPC是國際計(jì)算機(jī)協(xié)會(huì)(AssociationforComputingMachinery)組織的國際大學(xué)生程序設(shè)計(jì)競賽(InternationalCollegiateProgrammingContest),這項(xiàng)每年一屆的計(jì)算機(jī)學(xué)科競賽始于1976年,是大學(xué)生智力與計(jì)算機(jī)解題能力的競賽,是世界公認(rèn)的、目前全球高校之間規(guī)模最大且最具影響力的國際頂級(jí)賽事。
　　由清華大學(xué)吳文虎、王建德編著的《世界大學(xué)生程序設(shè)計(jì)競賽(ACM/ICPC)高級(jí)教程第一冊程序設(shè)計(jì)中常用的計(jì)算思維方式》(以下簡稱《計(jì)算思

2、維方式》)就是針對(duì)世界大學(xué)生程序設(shè)計(jì)競賽(ACM/ICPC)而編寫的參考書,該書面向參加ACM/ICPC的高等院校學(xué)生,也可作為程序設(shè)計(jì)愛好者的參考用書。同時(shí),也向講授程序設(shè)計(jì)及相關(guān)課程的教師推薦此書,建議認(rèn)真一讀。
　　1ACM/ICPC
　　ACM/ICPC是高等院校計(jì)算機(jī)教育成果的直接體現(xiàn),是大學(xué)生展示水平與才華的大舞臺(tái),也是IT企業(yè)與世界頂尖計(jì)算機(jī)人才對(duì)話的最佳機(jī)會(huì)。因而,ACM/ICPC吸引了越來越多的高校參賽,使得參賽隊(duì)伍的水平上升很快,賽題的難度也在不斷提高。
　　每年度的ACM/ICPC賽事從當(dāng)年

3、9月份開始,先進(jìn)行各大洲各地區(qū)的預(yù)選賽,從上千所高校的幾千支隊(duì)伍中挑選出幾十支優(yōu)勝隊(duì)伍。讓這些百里挑一的隊(duì)伍在下一年春天參加總決賽,爭奪金銀銅獎(jiǎng)和世界冠軍的獎(jiǎng)杯。參賽選手由三人組成,一隊(duì)共用一臺(tái)計(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

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

5、節(jié)是看題、審題和選題。一開始就選對(duì)題,一下子就切入主題是十分重要的。有時(shí)第一個(gè)環(huán)節(jié)遇到陷阱,“馬失前蹄”,就會(huì)導(dǎo)致一籌莫展而步步落后。能否在第一環(huán)節(jié)占上優(yōu)勢取決于實(shí)踐能力和洞察力,而實(shí)踐能力與洞察力的提升需要實(shí)戰(zhàn),需要經(jīng)驗(yàn),需要學(xué)懂計(jì)算思維方式和解題策略。
　　參加ACM/ICPC活動(dòng),在與編程高手過招的過程中,可以把知識(shí)運(yùn)用的綜合性、靈活性和探索性發(fā)揮到極致,體驗(yàn)和感受數(shù)學(xué)思維與算法藝術(shù)之美,提升科學(xué)思維能力。
　　2“觀察—聯(lián)想—變換”思維方式
　　計(jì)算機(jī)解題的核心是算法設(shè)計(jì),而算法設(shè)計(jì)需要具備良好的數(shù)學(xué)素養(yǎng)

6、。數(shù)學(xué)具有運(yùn)用抽象思維去把握實(shí)際的能力,應(yīng)用數(shù)學(xué)知識(shí)去解決實(shí)際問題時(shí)的建模過程是一個(gè)突出主要因素的科學(xué)抽象過程。進(jìn)行抽象和形式化需要學(xué)習(xí)和掌握常用的計(jì)算思維方式。
　　科學(xué)思維能力的提高是成就事業(yè)最重要的因素之一,本書作者希望能在這方面對(duì)讀者起到幫助作用。
　　編程解題的一般思維方法或過程,可以概述為“觀察—聯(lián)想—變換”,即通過對(duì)問題的觀察,認(rèn)識(shí)和理解該問題;然后通過聯(lián)想,尋找該問題同已有知識(shí)和經(jīng)驗(yàn)之間的聯(lián)系;最后通過變換,把該問題轉(zhuǎn)化為另一個(gè)或幾個(gè)易于解決的新問題,最終達(dá)到解決原問題的目的。
　　“觀察”是人類

7、認(rèn)識(shí)客觀事物的基本途徑,就編程解題而言,“觀察”是“聯(lián)想”和“變換”的基礎(chǔ)。一般地說,通過觀察應(yīng)當(dāng)明確:求解的對(duì)象是什么;是枚舉方案還是回答哪個(gè)存在性問題;已知的條件(包括隱含條件)是什么;能否用遞推公式、遞歸公式、約束規(guī)則或狀態(tài)轉(zhuǎn)移方程把問題的條件、結(jié)論和求解途徑表示出來;問題所涉及的這些計(jì)算式子各有什么特點(diǎn)等。
　　“聯(lián)想”是由某種對(duì)象而引出其他相關(guān)對(duì)象的思維形式。就編程解題而言,“聯(lián)想”的目的在于為“變換”提供可能的方向或線索。一般地說,在“觀察”的基礎(chǔ)上,通過聯(lián)想應(yīng)當(dāng)明確:以前是否解過這類試題;是否解答過與其類似而又

8、稍有不同的試題;是否解答過與其有關(guān)的問題;能否利用解答這些問題時(shí)所使用的解題方法或所得到的結(jié)果;能否回憶出某個(gè)可能用得上的定理、公式或解題思路;為了能利用它,是否應(yīng)當(dāng)改變條件或結(jié)論的表現(xiàn)形式等。
　　“變換”是編程解題的基本手段。在“觀察”和