信息學(xué)競賽輔導(dǎo)中“擠”的藝術(shù)
2009-11-12 22:11:49網(wǎng)絡(luò)
在信息學(xué)競賽輔導(dǎo)中,培養(yǎng)學(xué)生抓住題目本質(zhì)、把題目做完全(得滿分)的能力是非常重要的。在高層次的競賽中,大部分已經(jīng)達(dá)到一定層次的學(xué)生的水平實(shí)際上非常接近。比如在廣東省信息學(xué)奧賽總決賽中,對(duì)于每天的四個(gè)題目,高層次的學(xué)生(這類學(xué)生全省有30人左右)一般都能做其中三題。請(qǐng)注意,我這里用的是“能做”二字,一些題目很多學(xué)生能做,但卻不能得到該題的滿分,這里就是涉及到能否把能做的題目做完全的問題。而一旦誰能把能做的這幾題做完全,有兩題或兩題以上都得到滿分(或高分),誰就將脫穎而出,進(jìn)入省前五名是順理成章的事。
例如有這樣一題競賽題:求N個(gè)字母的字符串組合:
如:用A、B、C三個(gè)字母組成長度為3的字符串,但每個(gè)字母都不允許重復(fù)使用,并且每個(gè)字母都不能擺在自己序號(hào)的位置上,則符合條件的只有兩個(gè)字符串:BCA、CAB。對(duì)于鍵盤輸入的n(n<=17),則意味著給出了A1、A2、……、An個(gè)不同的字母,用它們組成長度為N的字符串,但每個(gè)字母不允許重復(fù)使用,并且每個(gè)字母都不能擺在自己序號(hào)的位置上。問有多少個(gè)符合條件的字符串S。
幾乎所有學(xué)生一拿到就立刻用遞歸算法下手,對(duì)于輸入的n,把滿足條件的n個(gè)字符的字符串全部找出來,最后輸出總數(shù),不用多少時(shí)間就得到程序,一運(yùn)行,結(jié)果也對(duì),于是絕大部分學(xué)生都認(rèn)為大功告成了。熟不知測試數(shù)據(jù)中有n=17的情況,而限時(shí)竟然只有短短的5秒!絕大部分同學(xué)都因大數(shù)據(jù)超時(shí)而只得到該題的很少的幾分。顯然,對(duì)于這樣一題人人會(huì)做的題目,最終卻只有少數(shù)幾人能做得完全,能得滿分。事實(shí)上,此題有一公式,對(duì)于n=17的情況也不用1秒就能得出結(jié)果,找到這一公式才能把這題做得完全,雖然使用的仍是遞歸算法,但速度卻要快出無數(shù)倍,因?yàn)閷?duì)于輸入的n,直接計(jì)算字符串的總數(shù)而無需得到每一個(gè)字符串,耗時(shí)自然大大減少了。給出公式如下:
0 (x=1)
f(x)= x*f(x-1)+1 (x>2,x mod 2=0)
x*f(x-1)-1 (x>2,x mod 2=1)
程序自然不必多說了。
所以,一個(gè)題目會(huì)做卻并不等于你能把這題做全,能把這題的分得全,這就是真高手與半高手的區(qū)別。那么,怎樣才能在平常的訓(xùn)練中培養(yǎng)學(xué)生的這種把題目做全的能力呢?下面筆者想以第四屆全國青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽復(fù)賽高中組第二題為例,談?wù)劰P者在奧賽訓(xùn)練中采用的“擠”的訓(xùn)練方法。
題目如下:
設(shè)有N個(gè)正整數(shù)(N<=20),將它們聯(lián)成一排,組成一個(gè)最大的多位整數(shù)。
例如:N=3時(shí),3個(gè)整數(shù)13、312、343聯(lián)成的最大整數(shù)為:34331213;
又如:N=4時(shí),4個(gè)整數(shù)7,13,4,246聯(lián)成的最大整數(shù)為:7424613;
輸入: N
N個(gè)數(shù)
……
輸出:聯(lián)成的多位數(shù)。
測試數(shù)據(jù)如下:
序號(hào)
輸入
輸出
分值
1
3
121 21 3
321121
5
2
4
13 24 75 42
75422413
10