高職學生參與ACM程序設計競賽的特點和培訓研究

【摘 要】ACM程序設計競賽旨在展示大學生創(chuàng)新能力、團隊精神和在壓力下編寫程序分析問題、解決問題的能力。本文以往年幾屆浙江省大學生程序設計競賽的數(shù)據(jù)分析了高職生參與ACM程序設計競賽的特點，并探索組織高職生進行ACM程序設計競賽培訓的方法，也為拓展軟件技術專業(yè)學生素質(zhì)提供新的途徑。

【關鍵詞】ACM；大學生程序設計競賽；高職；培訓

一、前言

高等學校是知識創(chuàng)新的基地、人才培養(yǎng)的搖籃，高職院校承擔著培養(yǎng)高端技能型專門人才的重任，高職學生必須在實踐技能上有非常突出的能力。

高職軟件技術專業(yè)在對學生的技能型專門人才方面的培養(yǎng)，就需要加強實踐教學的比例，提高學生的實際編程能力和動手能力。

軟件技術專業(yè)學生參加各類大學生程序設計競賽是提高編程能力的重要手段，特別是ACM程序設計競賽在國內(nèi)外都有非常大的影響力，國內(nèi)的各類本、?？圃盒６挤e極組織學生參與，成為最為重要的程序設計競賽。

二、ACM國際大學生程序設計競賽和浙江省大學生程序設計競賽介紹

ACM國際大學生程序設計競賽（ACM Inter-

national Collegiate Programming Contest，簡稱ACM/ICPC）是由美國計算機協(xié)會（Association of Computing Machinery，簡稱ACM）主辦的，世界上公認的規(guī)模最大、水平最高的國際大學生程序設計競賽，競賽旨在展示大學生創(chuàng)新能力、團隊精神和在壓力下編寫程序、分析和解決問題的能力。

ACM程序設計競賽以團隊的形式代表學校參賽，每隊至多三名本校學生組成，比賽期間，每隊只使用1臺電腦在4-5個小時內(nèi)編寫程序解決10個左右的試題，試題描述全部為英文，程序設計語言可選用C、C++、Java以及其它允許的語言，編寫的程序由在線系統(tǒng)進行自動評判。

由浙江省大學生科技競賽委員會主辦、浙江大學承辦的浙江省大學生程序設計競賽也稱為ACM/ICPC浙江省賽，是ACM/ICPC在亞洲組織的省賽、國賽的一部分，從2004年開始至2013年已連續(xù)舉辦了十屆比賽。浙江省本、?？聘咝６挤e極組織隊伍參加比賽，如今已經(jīng)基本穩(wěn)定在本科隊伍200個左右、專科隊伍100個左右的參賽規(guī)模。

所有參賽隊伍同臺競技，成績有統(tǒng)一的排名，但本、?？圃盒５膮①悓W生在知識水平和競賽準備上有較大的差距，所以本、?？脐犖闀謩e評比獎項，各設一個特等獎以及一定比例的金、銀、銅獎。

三、往年幾屆浙江省大學生程序設計競賽的數(shù)據(jù)分析

由于浙江省賽在賽后不提供比賽時的數(shù)據(jù)，所以選擇省賽競賽平臺（acm.zju.edu.cn）的校外同步競賽（非參賽的ACM愛好者在競賽時間段內(nèi)進行的解題）產(chǎn)生的數(shù)據(jù)作為部分分析的依據(jù)。

1.每題成功解題人數(shù)的統(tǒng)計數(shù)據(jù)

如圖1、圖2所示，以2012年和2013年的成功解題數(shù)據(jù)分析，因為題目難度隨機分布在題目序號中，所以不按照題目順序、而是每題成功解題人數(shù)從大到小構造柱狀圖。

圖1 2012年浙江省大學生程序設計競賽成功解題情況圖

圖2 2013年浙江省大學生程序設計競賽成功解題情況圖

從圖中可以看出一些特性：

（1）題目難度控制較好，區(qū)分度清晰

一個題目成功解題的人數(shù)越多，說明這個題目的難度較低，反之，解題人數(shù)越少，題目難度越大。

圖1中，前6個題目成功解題人數(shù)幾乎成線性的遞減，很好的控制了競賽的節(jié)奏，易于區(qū)分出參賽隊伍的水平，后5個題目I、E、G、B、C難度極大，是強隊真正競爭的地方。同理，在圖2中，前7個題目成功解題的人數(shù)也是幾乎成線性的遞減，后4個題目E、G、C、K顯然也是難度極大。

（2）年度間的題目難度比較

從圖1、圖2及數(shù)據(jù)體現(xiàn)看，2012年的競賽難度比2013年大。這兩年的題目數(shù)量相等，當從難度極大的題目數(shù)量看2012年偏多，同時，前幾題的的線性遞減的傾斜度顯然是2012年的大，說明2012年的題目難度遞增趨勢快。

對于普通參賽隊伍來說，前幾題是可以奮斗的題目，而同一年這些題目間解題成功人數(shù)遞減的數(shù)據(jù)比較：

2012年前6題的平均遞減人數(shù)是：

2013年前7題的平均遞減人數(shù)是：

從以上運算數(shù)據(jù)中看出2012年遞減較快，反映了2012年的題目難度增長趨勢比2013年大。

2.每個參賽隊成功解題的數(shù)量分布

從另一個角度考慮，在比賽期間，每個參賽隊能夠成功解答的題目數(shù)量分布情況如圖3、圖4所示。

從這兩個圖中的差異，再參考對圖1、圖2的分析，可以看到2012年由于題目難度偏大，每個參賽隊的解題數(shù)量偏低，近一半集中在2題以下，而2013年解題有比較好的分布，容易使普通參賽隊有發(fā)揮的機會。

圖3 2012年每個參賽隊解題數(shù)量的分布比例圖

圖4 2013年每個參賽隊解題數(shù)量的分布比例圖

3.競賽題目特點

從圖1、圖2的分析可以看到，題目是一個由易到難的過程，具體到每一個題目的題型時，有一半多一些偏易的題目主要考核的是參賽隊使用特定的編程語言編寫代碼的熟練度、基本數(shù)據(jù)結構的算法和側(cè)重于考驗思維能力的題目，而較難的那部分題目，往往有高級的數(shù)據(jù)結構或者有特定的算法支持，需要復雜的思維處理能力。

再從圖3、圖4中可以看到，絕大部分參賽隊伍也只能完成較易的那部分題目、只有少數(shù)隊伍有過特定知識的準備，并經(jīng)過一定的訓練，才能夠在比賽期間沖擊并完成更難的題目。

4.比賽期間的選題策略

根據(jù)排名規(guī)則，參賽隊在解題時需要考慮一個選題的策略，不然，即使有相同的解題數(shù)量，也可能排名時偏弱于其他參賽隊。

假設一個題目的解題時間是固定的、且不產(chǎn)生罰時，并假設題目X的解題時間是s分鐘，題目Y的解題時間是t分鐘，且s

（1）當題目X、Y在相鄰的時間段內(nèi)解答完成

同時假設在X、Y之前解答的題目已經(jīng)耗費的時間是m，那么當X在Y之前完成解答，X和Y的總計時是：

T1=（m+s）+（m+s+t）=2m+2s+t

如圖5所示：

m分鐘X（s分鐘）Y（t分鐘）

圖5 相鄰時先完成題目X后完成題目Y

當X在Y之后完成解答，X和Y的總計時是：

T2=（m+t）+（m+t+s）=2m+2t+s

如圖6所示：

m分鐘Y（t分鐘）X（s分鐘）

圖6 相鄰時先完成題目Y后完成題目X

因為假定s

總的競賽耗費時間在其它都不變的情況下，差距的時間是：T2-T1=t-s。

（2）當題目X、Y不在相鄰的時間段內(nèi)解答完成

若在X和Y之間相隔了k個有序的題目，它們的總耗時為n分鐘，那么當X在Y之前完成解答，X和Y的總計時是：

T3=（m+s）+（m+s+n+t）=2m+2s+t+n

如圖7所示：

m分鐘X（s分鐘）n分鐘Y（t分鐘）

圖7 間隔k個有序題目時先完成題目X后完成題目Y

當X在Y之后完成解答，X和Y的總計時是：

T4=（m+t）+（m+t+n+s）=2m+2t+s+n

如圖8所示：

m分鐘Y（t分鐘）n分鐘X（s分鐘）

圖8 間隔k個有序題目時先完成題目Y后完成題目X

在s：T3

但同時注意，夾在中間耗時n分鐘的k道題目，在圖7到圖8的解題方案轉(zhuǎn)變時，每個題目都往后移動了，所以總的競賽耗費時間在其它都不變的情況下，差距的時間是：T4-T3+k（t-s）=（k+1）（t-s）。

綜合上述的分析，選題策略應該按照每個題目解題時耗費時間的長短從小到大排序，并按這個順序依次解題。而解題耗費時間的長短，可以假定為題目的難易程度。從結果看，也就是如圖1、圖2所示柱狀圖從左到右依次選題是一個比較優(yōu)化的選題策略。

四、高職生參與ACM程序設計競賽的特點

1.高職生相比于本科生差距巨大

浙江省大學生程序設計競賽的參賽隊伍是本科組約200個、?？平M約100個，共同構成統(tǒng)計數(shù)據(jù)。在第二部分對競賽數(shù)據(jù)的分析中，顯然本科組的優(yōu)勢參賽隊有機會向完成8、9、10題甚至是11題進行沖擊。

那么，專科組的解題情況又是如何呢？我們從最近4屆專科組獲得特點獎、一等獎的解題數(shù)據(jù)進行比較。如表1所示：

表1 近4屆浙江省大學生程序設計競賽?？平M解題情況

年份特等獎一等獎（金獎）

2013年完成7題1個參賽隊完成6題、6個參賽隊完成5題

2012年完成5題8個參賽隊完成3題

2011年完成5題6個參賽隊完成5題

2010年完成6題5個參賽隊完成5題

參考圖3、圖4，可以注意到，?？平M的一等獎的解題數(shù)量處于所有參賽隊的中等位置，也可以認為是在150名左右，這樣的成績很難進入到本科組的三等獎，只有偶爾1、2個?？平M的參賽隊解題突出一些，會進入到排名100以內(nèi)。

2.高職院校間差距小競爭激烈

從表1的分析看，絕大部分的高職院校的參賽隊只能壓縮在5題左右的可解題目，而且這還是表現(xiàn)優(yōu)秀的隊伍，這使得相互之間多解出一題的排名差距更加大，競爭激烈。

那么，各高職院校間的競賽水平是否差距巨大呢？考慮到特等獎有一定的特殊性，可能是個別參賽隊員本身實力突出所帶來的表現(xiàn)，通過分析特定獎和一等獎在各院校的分布，以近四屆的數(shù)據(jù)為例，如圖9所示：

圖5 高職院校近四屆浙江省賽獲一等獎及以上參賽隊個數(shù)

從圖5中可以看到，共有16所高職院校在近四屆中至少獲得過一次一等獎。

考慮到解題數(shù)量有限，其實專科組獲得二等獎的參賽隊也其實有機會獲得一等獎，只是他們在沖擊下一題的解題中未能成功而已。所以圖10統(tǒng)計了近4屆獲得二等獎及以上的參賽隊數(shù)量分布情況（共計26所高職院校進入統(tǒng)計，圖6中部分省略）：

圖6 高職院校近四屆浙江省賽獲二等獎及以上參賽隊個數(shù)

3.高職生的特點

高職生和本科生之間的差距巨大最根本的原因在于生源造成的知識能力的巨大差異。本科院校特別是重點本科院校能夠優(yōu)先獲得優(yōu)秀的學生，也獲得優(yōu)秀學生的青睞。高職生的來源有兩塊，一部分來源于普通高考的錄取，是那些無法進入本科院校學習而只能選取高職院校就讀，另一部分來源于中職院校，他們只能被錄取到高職院校。

（1）競賽的主力是中職錄取的學生

由于普通高考上來的學生在高中階段幾乎沒有接觸過程序設計，進入高校學習后他們有一個逐步編程語言的過程，也就是沒法快速的進入到競賽培訓的角色，而中職學生必須是相關專業(yè)才能錄取到高職的計算機類專業(yè)就讀，它們已經(jīng)學過較多的編程，甚至有部分同學在中職階段就對程序設計有非常高的興趣，有非常良好的基礎，有非常強的動手能力。

（2）高職生的英語薄弱

我們能夠找到非常優(yōu)秀的學生，他們在實際編寫代碼的能力突出，但是一個普遍的問題是在英語上都欠缺，一個對本科生來說沒有閱讀困難的題目，到了他們眼里就非常困難，甚至為此耗費大量的時間，一個即使簡單的題目，由于沒有讀懂題目或者偏離題目含義也是很正常的事情。

（3）沒有系統(tǒng)的數(shù)學、算法上的知識積累

從實際的訓練表現(xiàn)來看，高職生的思維能力也并不一定差，但競賽中若有數(shù)學類的題目則需要特定的數(shù)學知識、若有算法類的題目則需要用到特定的算法，這些特定的知識不是靠靈活的思維就能解決，而是需要專門花精力去學習才能掌握，如果沒有這個知識背景，那么就會無從下手。

（4）積極性高、但訓練時間短

部分本科生在高中階段就因為參加信息技術大賽而進行過系統(tǒng)的培訓，在大學期間又會有較多志同道合的來源于不同專業(yè)的理工科同學進行交流，在知識積累和ACM的訓練上有較多的時間，并且他們的理解力也快很多。

而高職生在入學之前，即使有編程的基礎，基本沒有ACM程序設計以及相關知識的系統(tǒng)性積累，只能入校后進行練習，他們的積極性是很高的，但也沒有時間也沒有環(huán)境進行系統(tǒng)性的算法學習，只能在普通的算法以及考驗思維的題目上可以加強訓練。

五、組織高職生進行ACM程序設計競賽培訓

1.早宣傳、早鼓勵、早訓練

正因為訓練時間短，所以必須入校不久就加強ACM程序設計競賽的宣傳，介紹往年的獲獎情況、比賽的特點，同時宣傳學校對競賽的支持政策，加強新老學生的交流，鼓勵學生早投入到對ACM的認識中，使得有基礎的學生能督促自己盡早訓練。

總之，目的是激發(fā)學生參與ACM程序設計的積極性，盡早開始進行基礎性題目的訓練，特別是在同期加強英語閱讀的能力。

2.集中培訓，突破難點

如果能讓學生自發(fā)的早訓練，那么在賽前的兩、三個月，就可以進行集中的提高的培訓，專門安排一個機房，通過對歷屆賽題特別是適合于高職生難度的那些題目的分類分析，并選取其它同等難度的各類題目進行培訓和訓練。

應該在這段培訓期間盡快的選定組隊的隊員，并按照團隊進行有有一定難度的團隊解題訓練，使團隊內(nèi)成員對各自的分工和合作有較好的磨合。

同學也反映，平時在練習中相互的交流總是比較簡單的、隨意的，沒有壓力感，而這種在機房的集中訓練，能使得大家更齊心協(xié)力的專注于題目，感受到在有限的時間內(nèi)能否完成解題的壓力。

3.正式競賽期間的注意事項

（1）選題策略

因為本科院校的參賽隊伍在英語閱讀以及其他發(fā)面的優(yōu)勢，能夠在比賽期間較快的完成部分簡單題目，他們的選題策略也是盡量選取從易到難的題目，也許少數(shù)幾個隊伍有偶然性，但較多隊伍解題情況就能反映出題目難度來。

而高職院校的參賽隊，由于英語閱讀的薄弱，使得一下子在最簡單的題目上就會落后于本科隊，這樣，當我們需要選取下一個難度的題目時，完全可以在競賽頁面查詢即時的統(tǒng)計數(shù)據(jù)，判斷可以做的題目。

依據(jù)判斷的待解題目難度，?？脐爲撨x擇1、2題作為主攻的方向。

（2）團隊分工協(xié)調(diào)

本科院校的比較優(yōu)秀的參賽隊伍，組成的3個成員往往是分方向負責不同類型的題目，這是因為ACM題目的題型復雜，涉及的算法多，一個人無法覆蓋到方方面面，在比賽時3個隊員可以各自獨立的準備一道題目。

但是，對于高職院校的參賽隊伍，由于沒有足夠時間進行系統(tǒng)的算法學習，同時又有英語、數(shù)學等知識上的欠缺，使得他們隊員之間沒有太多可區(qū)分的題型方向，而且最終即使優(yōu)秀的高職隊伍基本解題量也在5題左右，所以3個隊員各自獨立的解答一道題目，會很快存在困難。

在判斷出題目難易程度之后，更需要參賽隊克服困難，協(xié)調(diào)解題的策略，發(fā)揮團隊的思維，透徹的理解題目，共同的來完成一道題目的解答，盡量少出現(xiàn)做了一半做不下去了，換個題目嘗試的行為。

六、結語

組成高職學生參加ACM程序設計競賽，能夠為學校為專業(yè)獲得榮譽，同時，參賽同學也在程序設計能力、團隊協(xié)作能力、甚至閱讀能力上得到提高。獲得的良好成績也激勵著參賽的和未參賽的同學對程序設計的熱愛，提高了軟件技術專業(yè)學生學習程序設計的積極性。

參考文獻：

[1]何莉輝，梁滄.基于ACM國際大學生程序設計競賽的學習模式[J].邊疆經(jīng)濟與文化，2008（06）.

[2]李玲芝，徐俊，易險峰.依托大學生計算機程序設計競賽，探索信息學科創(chuàng)新型人才培養(yǎng)新模式[J].實踐教學改革與創(chuàng)新，2009（12）.

[3]石晶瑜，白喜文，包常喜.ACM ICPC競賽中團隊精神的培養(yǎng)[J].內(nèi)蒙古師范大學學報（教育科學版），2011（3）.

作者簡介：林新輝（1979—），碩士研究生，講師，主要研究方向：計算機輔助幾何設計。