信息學(xué)競賽輔導(dǎo)中“擠”的藝術(shù)

　　在信息學(xué)競賽輔導(dǎo)中，培養(yǎng)學(xué)生抓住題目本質(zhì)、把題目做完全（得滿分）的能力是非常重要的。在高層次的競賽中，大部分已經(jīng)達(dá)到一定層次的學(xué)生的水平實(shí)際上非常接近。比如在廣東省信息學(xué)奧賽總決賽中，對于每天的四個(gè)題目，高層次的學(xué)生（這類學(xué)生全省有30人左右）一般都能做其中三題。請注意，我這里用的是“能做”二字，一些題目很多學(xué)生能做，但卻不能得到該題的滿分，這里就是涉及到能否把能做的題目做完全的問題。而一旦誰能把能做的這幾題做完全，有兩題或兩題以上都得到滿分（或高分），誰就將脫穎而出，進(jìn)入省前五名是順理成章的事。

　　例如有這樣一題競賽題：求N個(gè)字母的字符串組合：

　　如：用A、B、C三個(gè)字母組成長度為3的字符串，但每個(gè)字母都不允許重復(fù)使用，并且每個(gè)字母都不能擺在自己序號的位置上，則符合條件的只有兩個(gè)字符串：BCA、CAB。對于鍵盤輸入的n（n<=17），則意味著給出了A1、A2、……、An個(gè)不同的字母，用它們組成長度為N的字符串，但每個(gè)字母不允許重復(fù)使用，并且每個(gè)字母都不能擺在自己序號的位置上。問有多少個(gè)符合條件的字符串S。

　　幾乎所有學(xué)生一拿到就立刻用遞歸算法下手，對于輸入的n，把滿足條件的n個(gè)字符的字符串全部找出來，最后輸出總數(shù)，不用多少時(shí)間就得到程序，一運(yùn)行，結(jié)果也對，于是絕大部分學(xué)生都認(rèn)為大功告成了。熟不知測試數(shù)據(jù)中有n=17的情況，而限時(shí)竟然只有短短的5秒！絕大部分同學(xué)都因大數(shù)據(jù)超時(shí)而只得到該題的很少的幾分。顯然，對于這樣一題人人會做的題目，最終卻只有少數(shù)幾人能做得完全，能得滿分。事實(shí)上，此題有一公式，對于n=17的情況也不用1秒就能得出結(jié)果，找到這一公式才能把這題做得完全，雖然使用的仍是遞歸算法，但速度卻要快出無數(shù)倍，因?yà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è)題目會做卻并不等于你能把這題做全，能把這題的分得全，這就是真高手與半高手的區(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ù)如下：

　　序號

　　輸入

　　輸出

　　分值

　　1

　　3

　　121 21 3

　　321121

　　5

　　2

　　4

　　13 24 75 42

　　75422413

　　10