全國

熱門城市 | 全國 北京 上海 廣東

華北地區(qū) | 北京 天津 河北 山西 內(nèi)蒙古

東北地區(qū) | 遼寧 吉林 黑龍江

華東地區(qū) | 上海 江蘇 浙江 安徽 福建 江西 山東

華中地區(qū) | 河南 湖北 湖南

西南地區(qū) | 重慶 四川 貴州 云南 西藏

西北地區(qū) | 陜西 甘肅 青海 寧夏 新疆

華南地區(qū) | 廣東 廣西 海南

  • 微 信
    高考

    關(guān)注高考網(wǎng)公眾號(hào)

    (www_gaokao_com)
    了解更多高考資訊

首頁 > 高中頻道 > 信息學(xué)聯(lián)賽輔導(dǎo) > 信息學(xué)競賽輔導(dǎo)中“擠”的藝術(shù)

信息學(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

 

[標(biāo)簽:藝術(shù) 學(xué)習(xí)方法 競賽 競賽聯(lián)賽]

分享:

高考院校庫(挑大學(xué)·選專業(yè),一步到位。

高考院校庫(挑大學(xué)·選專業(yè),一步到位!)

高校分?jǐn)?shù)線

專業(yè)分?jǐn)?shù)線

日期查詢
  • 歡迎掃描二維碼
    關(guān)注高考網(wǎng)微信
    ID:gaokao_com

  • 👇掃描免費(fèi)領(lǐng)
    近十年高考真題匯總
    備考、選科和專業(yè)解讀
    關(guān)注高考網(wǎng)官方服務(wù)號(hào)