信息學競賽指導教師的知識結構與技能

信息學競賽指導教師的知識結構與技能福建師大附中信息技術組周成QQ：33345707Email：fjfzczhou@163.com主要內(nèi)容什么信息學競賽？信息學競賽指導的意義指導教師的知識結構指導教師的教學技能IOITheInternationalOlympiadinInformatics(IOI)IOI是全世界范圍內(nèi)高中生信息學（計算機）的競賽，學生要編寫程序解決有挑戰(zhàn)的問題。IOI是由聯(lián)合國教科文組織主辦的世界中學生五項奧林匹克競賽之一。第一屆

IOI于1989年在保加利亞舉行。

2000年9月23-30日，第12屆國際信息學奧林匹克競賽(簡稱IOI2000)在我國北京舉行。它的宗旨是在青少年中普及計算機科學，給來自世界各地的年輕人提供一個交流機會，并通過比賽和訪問加深對主辦國的了解。

同大學的ACM競賽與數(shù)學建模競賽有一定的相似與聯(lián)系數(shù)學、物理、信息、生物、化學NOI全國青少年信息學奧林匹克競賽（簡稱NOI）自1984年至，在國內(nèi)包括香港、澳門，已組織了24次全國性競賽活動。每年由中國計算機學會組織全國各省市、自治區(qū)33個代表隊，每隊5名選手，歷時7天。NOIP(NationalOlympiadinInformaticsinProvinces)全國青少年信息學奧林匹克聯(lián)賽自1995年至今已舉辦13屆。每年由中國計算機學會統(tǒng)一組織。NOIP是在同一時間、不同地點以各省市為單位由特派員組織。每年的9月10—20日報名，初賽定于每年10月的最后一個星期六下午，復賽定于每年11月的最后一個星期六舉行。全國統(tǒng)一大綱、統(tǒng)一試卷。初、高中或其他中等專業(yè)學校的學生可報名參加聯(lián)賽。聯(lián)賽分初賽和復賽兩個階段。初賽以通用和實用的計算機知識為考試內(nèi)容，重在考察基礎與實用的知識，以筆試為主。復賽為程序設計。參加初賽者須達到一定分數(shù)線后才有資格參加復賽。各省市、自治區(qū)都應參加聯(lián)賽，參加聯(lián)賽是參加NOI的必要條件。NOIP2009（提高組）情況全省共有4632人報名初賽全省共有664人進入復賽全省共有72人獲一等獎(新增46人)福州一中計數(shù)11南安一中計數(shù)10福建師大附中計數(shù)9福州三中計數(shù)7廈門一中計數(shù)6泉州七中計數(shù)6廈門雙十中學計數(shù)5長樂一中計數(shù)5福州八中計數(shù)3漳平一中計數(shù)2莆田一中計數(shù)2廈門英才學校計數(shù)1龍巖一中計數(shù)1晉江養(yǎng)正中學計數(shù)1惠安一中計數(shù)1長汀一中計數(shù)1長泰一中計數(shù)1OI的“現(xiàn)實”意義NOIP提高組一等獎具有保送大學的資格NOIP提高組二等獎可參加大學自主招生NOI二、三等獎可直接獲得一些重點大學免試保送NOI一等獎可獲得北大、清華免試保送高考可加10分……OI只為了得獎？編程解決有挑戰(zhàn)性的問題，是益智性考查智力、解決問題能力構建數(shù)學模型設計算法寫出程序調(diào)試通過陳宏：IOI99金牌、IOI00金牌朱瓏：無任何省賽一等獎以上的獲獎，洛杉磯理工大學博士，美國微軟工作不僅使部分學生們在國際、全國、省、市等各級競賽中獲得各種獎項更重要是培養(yǎng)了一批有計算機特長的學生，使他們在中學階段就打下了很好的算法與程序設計基礎同時也鍛煉了他們分析問題、解決問題、語言表達、團結協(xié)作等能力。OI只為了得獎？OI有很大的意義培養(yǎng)一批特長的學生擴大學校辦學成果為學生進入重點大學開辟新的渠道OI已經(jīng)成為我們信息技術教師，在做好信息技術教學工作后的一項極具挑戰(zhàn)的有很大意義的工作。ILIKEIT!OI給我?guī)淼臉s譽1994、1995、1996年獲“福建師大優(yōu)秀團員”；1994年獲“福建省計算機競賽優(yōu)秀指導教師”；1995、1996、1999、2002年獲“福建師大教學先進工作者”；1997年獲“市教育系統(tǒng)新長征突擊手”；1997年獲“福建師大先進教育工作者”；2000年獲“福州市先進教育工作者”；2002年獲“福州市學科培優(yōu)工作先進個人”；2003年獲“第四屆‘福建省青少年科技教育突出貢獻獎’科技輔導員”等榮譽稱號。2005年被評為第二十市福州市勞動模范。指導教師的知識結構本體性知識教師所教科目的學科專業(yè)知識條件性知識教育學、心理學知識包括對教學過程規(guī)律性的認識，對教育對象的了解等等背景性知識（教師應有的綜合性的文化涵養(yǎng)）實踐性知識（教師在教學過程中積累的經(jīng)驗）指導教師的知識結構-本體性知識學科專業(yè)知識 較為熟練掌握C/C++或Pascal語言計算機的基本常識操作系統(tǒng)、數(shù)據(jù)庫計算機網(wǎng)絡計算機信息安全基礎知識算法與數(shù)據(jù)結構、圖論、組合數(shù)學……指導教師的知識結構-本體性知識相關通識知識相關通識知識是信息技術教師應當掌握的擴展性知識，與學生的學科背景有一定的關聯(lián)。老師應當具有與學生學科專業(yè)相結合的，更寬廣的背景性知識，需要強調(diào)知識的相關性、實用性、擴展性和指向性，充分體現(xiàn)信息技術課程作為文化和工具的實踐價值。指導教師的知識結構-條件性知識條件性知識是指在教育教學活動中運用教育學和心理學理論規(guī)律來思考、重組和表征本體性知識的知識，包括：學生認知發(fā)展的知識、教與學的知識以及學生成績評價的知識。如杜威所指出：教師的學科知識與科學家知識是不一樣的，教師必須把學科知識”心理化“，以便學生能夠理解。例如：我們在講授”堆“這種數(shù)據(jù)結構時，要考慮學生的興趣點可能有哪些？“堆是怎么產(chǎn)生的？”、”為什么堆的復雜度為O（lgN）？“等等。我們在傳授給學生這種知識時應采用什么態(tài)度、方式和教學策略？應該如何評估學生掌握情況？除此，我們還要學習一些諸如：“建構主義理論”等現(xiàn)代教育理論信息學競賽指導教師的技能與領導、老師溝通，取得支持的能力科學管理競賽梯隊的能力從小抓起，及時發(fā)現(xiàn)人才處理教材，切勿生搬硬套難點分散、用到再學要寫程序、先想算法聯(lián)系實際、激發(fā)興趣注重結構、培養(yǎng)習慣引導變通，提高能力合理安排好學習內(nèi)容控制好學習的難度培養(yǎng)學生的自學能力積極營造討論氣氛鼓勵學生撰寫解題報告與小論文運用網(wǎng)絡進行學習建立網(wǎng)絡在線評測系統(tǒng)利用網(wǎng)絡在線系統(tǒng)，自主學習注重培養(yǎng)學生的解題方法信息學競賽指導教師的技能刻苦鉆研，終身學習的能力資料的收集與整理能力與校內(nèi)外同事交流協(xié)作的能力架構主題網(wǎng)站、編寫測評系統(tǒng)、開發(fā)形象生動的課件等能力難點分散、用到再學第一節(jié)課“我的第一個程序“Programex1;Varr,c,s:real;BeginWrite(‘Pleaseinputr:’);readln(r);C:=2*pi*r;s:=pi*r*r;Writeln(‘C=‘,c:0:2);Writeln(‘S=‘,s:0:2);End.了解程序結構、學會輸入程序、保存程序、運行程序。要寫程序、先想算法闡明解題過程中人與程序的關系，即解題實際上是人解題過程，而程序是人解題過程的一種描述，它可以使得計算機能解決該問題。簡單的算法設計訓練例1輸入三個數(shù)，然后輸出其中最大的數(shù)。要寫程序、先想算法算法的自然語言表示：步驟1：接受鍵盤輸入三個數(shù)A、B、C步驟2：A與B中大的一個放入MAX中步驟3：把C與MAX中大的一個放入MAX中步驟4：輸出MAX，MAX即為最大數(shù)。要寫程序、先想算法算法的偽代碼表示：Begin（算法開始）輸入A，B，CIFA>B則

A→Max

否則B→MaxIFC>Max則C→MaxPrintMaxEnd(算法結束)要寫程序、先想算法算法的NS框圖表示：輸入A、B、CA>BMAX>C不成立成立MAX=AMAX=B成立不成立MAX不便MAX=C輸出MAX聯(lián)系實際、激發(fā)興趣例1、期未來臨了，班長小Q決定將剩余班費X元錢(4<=x<=1000)，用于購買若干支鋼筆獎勵給一些學習好、表現(xiàn)好的同學。已知商店里有三種鋼筆，它們的單價為6元、5元和4元。小Q想買盡量多的筆（多鼓勵同學），同時他又不想有剩余錢。請您編一程序，幫小Q制訂出一種買筆的方案。聯(lián)系實際、激發(fā)興趣題義分析：用X元錢，買最多的筆，且恰好用完算法設計：求CX

div4;A0;B0;CaseXmod4of1:beginb:=1;C:=c-1;end;2:beginA:=1;C:=C-1;end;3:beginA:=1;B:=1;C:=C-2;end;End輸出A、B、C的值聯(lián)系實際、激發(fā)興趣例2：編寫一個程序，幫你的爸媽計算個人所得稅。注重結構、培養(yǎng)習慣注重程序結構(模塊化、結構化),培養(yǎng)好的設計習慣。Programex1;VarA,B,C,X:integer; {想好要主要變量的類型}Beginreadln(x); {輸入}C:=xdiv4;A:=0;B:=0; {算出初始答案}CaseXmod4of {調(diào)整，使得錢恰好用完}1:beginb:=1;C:=c-1;end;2:beginA:=1;C:=C-1;end;3:beginA:=1;B:=1;C:=C-2;end;End;Writeln(a,b:5,c:5); {輸出答案}End.制作多組測試數(shù)據(jù)，進行測試。測試自己的程序序號輸入輸出(各種筆的數(shù)目)正確否？110101YES215111YES31000025YES45010YES599911247YES數(shù)據(jù)：(1)有幾個小的范圍的，自己能算出答案且涵蓋各種情況；

(2)也有一兩個大的數(shù)據(jù)，自己無法算出答案，但可以測試自己程序是否能承受最大數(shù)據(jù)。引導變通，提高能力語句可變量的變通程序設計方法的變通算法的變通語句可變量的變通一、引導對語句可變量的變通，加強語句的理解與應用。

例如，對典型的求和問題：

S=1+2+3+……+100

在學習讀寫過程、賦值語、條件語句和循環(huán)語句之后，啟發(fā)學生設計以下程序：

Programeg1;

vari,s:integer;Begins:=0;fori:=1to100dos:=s+i;

writeln('S=',s);

readlnEnd.語句可變量的變通在這一簡單程序基礎上可引導學生作以下變通：(1)求S=1+1/2+1/3+……+1/100，應作哪些變更？(2)求平方和S=12+22+32+……+1002，應修改哪個語句？(3)求S=2+4+6+……+100，需要修改哪些地方？(4)一般地，求和S=m+…+n，其中m，n為鍵盤輸入量，應作哪些增加與改動？程序設計方法的變通二、引導對程序設計方法的變通，加強語句與程序結構的理解。

例如：求N!=1*2*3*……*12

先采用for語句設計發(fā)如下：

Programeg2;

var

i,n:longint;Beginn:=1;fori:=1to12don:=n*i;

witeln(n,'!=',n);

readlnEnd.程序設計方法的變通

Programeg2_1;

var

i,n:longint;Beginn:=1;i:=1;repeatn:=n*i;i:=i+1;untili>12;

writeln(n,'!=',n);

readln;End.Programeg2_2;

var

i,n:longint;Beginn:=1;i:=1;whilei<=12dobeginn:=n*i;i:=i+1;end;

writeln(n,'!=',n);readln;End.采用while和repeat…until語句如何設計：學生分析發(fā)現(xiàn)：可以用while和repeat循環(huán)代替，但沒有什么優(yōu)勢，更容易錯。程序設計方法的變通求出下式中n的最大值：s=22+42+62……+n2<2000先向?qū)W生提問：用什么循環(huán)語句來設計程序？通過討論，學生自己得出結論：用for語句無法設計；只能使用repeat……until與while兩種循環(huán)設計；同時再次對repeat……until和while兩種循環(huán)中的布爾表達式之間的關系有進一步的認識程序設計方法的變通TurboPascal提供的三種語句實現(xiàn)循環(huán)結構，即for語句，while語句和repoeat……until語句，對于能確定循環(huán)次數(shù)且可利用一個簡單循環(huán)控制變量（只能使用順序類型數(shù)據(jù)）時，使用for語句最合適了；對于循環(huán)次數(shù)不能預先確定，宜使用while或repeat……until語句，但while語句適用于有可能根據(jù)條件判斷使其成為空語句的情況，而repeat……until語句適用于不論什么條件至少要執(zhí)行一次循環(huán)體的情況。通過如此的引導變通，使學生對循環(huán)結構的三條語句使用得心應手，在編程過程中能夠靈活應用；同時也培養(yǎng)了學生發(fā)散性思維。算法的變通三、引導對算法的變通，提高編程解決實際問題的能力。算法是程序設計的依據(jù)。確定合理的算法是編程解決實際問題的前提與關鍵。引導對算法的變通，包括迭代、遞推、模擬等基本算法的改造，傳統(tǒng)算法的推陳出新，必須緊密聯(lián)系具體問題的實際。

算法的變通例如，一個整數(shù)的每位數(shù)字都是1，至少多少位才能使這個數(shù)被1987整除呢？這是一個有趣的實際問題，一般考慮的，無非是整除，一個個進行試商檢驗是基本的算法，一些學生往往“滿有把握”地編出程序：算法的變通Programeg5;Varb,i:integer;Beginb:=0;i:=0;repeati:=i+1;b:=b*10+1;untilbmod1987=0;

writeln('i=',i);

readlnEnd.算法的變通在程序運行受阻之后，就要啟發(fā)學生分析算法上的問題：當數(shù)的位數(shù)超過定義的整型數(shù)范圍后，程序出錯，然后引導學生思考：如果不用計算機，怎么求解？讓學生在寫出幾步整數(shù)除法的豎式的基礎上進行模擬尋求模擬變量（被除數(shù)、余數(shù)、商）建立模擬循環(huán)，從而設計出簡練可行的程序：算法的變通

Programeg6;

varb,i,a:integer;Beginb:=1111,i:=4;repeati:=i+1;a:=(b*10+1)div1987;b:=b*10+1-1987*a;untilb=0;

writeln('i=',i);readlnEnd.由于以上程序中每次作整除運算所得的余數(shù)B要小于1987，因此下一輪的被除數(shù)B*10+1（體現(xiàn)增加一個“1”）最多是五位數(shù)，可確保整除的實現(xiàn)?？梢?，算法的變通，有時直接關系到程序設計的成敗。答案為331個連續(xù)的1引導變通，提高能力程序設計引導變通教學法是啟發(fā)式教學原則在計算機語言教學中的體現(xiàn)與發(fā)展。實施引導變通程序設計，課堂教學氣氛活躍，辯謬糾錯，比較鑒別，層次分明，思維靈活，可以在提高程序設計能力，增強程序優(yōu)化意識上收到良好成效。程序設計引導變通，究竟在哪幾個問題上變，如何去變，本身就是“應變”的，并沒有一成不變的模式可套，必須因課制宜，因題制宜，因不同專業(yè)特點和學生實際而異。變通的實施，關鍵在引導，切忌想當然，脫離實際，強加于人，代替學生去完成變通。同時，變通應有梯度，有針對性，不能面面俱到，貪廣求深，欲速不達。運用網(wǎng)絡進行自主學習建立網(wǎng)絡在線評測系統(tǒng)利用網(wǎng)絡在線系統(tǒng)，自主完成合理安排，扎實基礎合理安排好學習內(nèi)容控制好學習的難度培養(yǎng)學生的自學能力積極營造討論氣氛鼓勵學生撰寫解題報告與小論文合理安排好學習內(nèi)容初一上學期，安排程序設計語言的學習；初一下學期，安排基本數(shù)據(jù)結構知識的學習（如棧、隊、鏈表）；初二上學期，安排簡單的算法的學習（如回溯、遞歸、枚舉）；初二下學期，安排基礎算法（深度、廣度、雙向、A*）及圖論知識的學習；初三安排貪心、動態(tài)規(guī)劃算法學習與綜合解題訓練。高中后，可以繼續(xù)安排網(wǎng)絡流算法的學習，綜合解題訓練，同時全面組織學生進行數(shù)據(jù)結構與算法的理論學習，撰寫小論文等。控制好學習的難度培訓的難度應根據(jù)學生的認識規(guī)律，先易后難，易中有稍難，有條理、循序漸進地進行。如在學習雙向搜索時，我們可以先以“8數(shù)碼問題”這一經(jīng)典問題為例，講解該算法的基本結構，然后在布置的作業(yè)時，先做一些簡單的題目（如，IOI96的“魔方問題”），在學生對該算法有所掌握的基礎上，再布置再增加一些稍難、稍加變型的題目，激發(fā)學生思考問題的興趣。初中學生要盡快學習完主要算法（不要做太難題目）努力培養(yǎng)學生的自學能力在以上的有關知識的學習中，我們也只能是重點學習，而對于詳細的理論知識學習要通過學生自學。同時，由于奧賽中還涉及到許多高等數(shù)學，計算幾何，組合數(shù)學的知識，所以也教師也不可能給他們詳細地上課，也可以通過學生自學來實現(xiàn)。教師可定期組織學生進行學習交流討論，并通過一定的相關的問題考查學生的學習情況。也可以請大學的教授給他們概括性再上若干次課，進一步幫助他們鞏固這些知識。積極營造討論氣氛當每次解題訓練結束后，我們都要組織學生進行討論，對所做的題目的解法進行充分交流，使得他們都有發(fā)表自己見解的機會。這不僅對于有好的解法的同學以鼓勵，也是對其他同學有很大的激勵，營造出友好、競爭的討論氣氛。同時交流好的解法，也讓所有同學共享他的解法，他們往往會研究該解法正確性與優(yōu)缺點，并創(chuàng)造出更好的解法。多年實踐表明，小組討論這種形式，促進學生之間的共同進步，同時也培養(yǎng)他們科學認真的治學態(tài)度。鼓勵學生撰寫解題報告與小論文學生在學習算法或其它知識時，往往對某一算法或知識的理解不夠深刻。通過撰寫解題報告可以讓學生對一道題目的解題過程有更深刻的理解。通過對問題的分析，確定出解決問題的算法，進而對算法進行時空效率的分析，發(fā)現(xiàn)算法的不足之處，進一步挖掘問題特性，優(yōu)化算法，最后逐漸得出一個較好的算法，并進行算法優(yōu)化前后的效率比較等。通過撰寫解題報告，使學生對問題分析得更加透徹，思考問題更全面，算法更趨優(yōu)化，這對提高學生分析問題和解決問題的能力有很大的幫助。方法比知識更重要歸納法思想進行解題問題分析法(回文素數(shù))類比法歸納法思想進行解題多年的教學，我發(fā)現(xiàn)解決許多信息競賽問題都可以采用歸納法思想進行思考，進而建立起數(shù)學模型。下面我們結合一些例子談一談在算法教學中，是如何引導學生應用歸納法思想來解題的。如何引導學生應用歸納法思想進行解題歸納推理，又稱歸納法，它是從一般性較小的前提出發(fā)，推出一般性較大的結論的推理。歸納法有完全歸納與不完全歸納兩種。歸納法常常從觀察開始，通過分析特殊一些例子，進而進行猜想，進行歸納。即它是觀察所啟發(fā)而由特例所揭示的。歸納解題流程圖如何引導學生應用歸納法思想進行解題這里，“研究規(guī)模小的問題，得出解”就相當于歸納法思想中的“觀察分析”，而“提出（猜測）一個解決問題的數(shù)學模型”，這就相當于歸納法思想中的歸納。而如果能“運用某數(shù)學模型的理論驗證模型的正確性”則我們對解題的歸納是完全的。在信息學解題時，有時很難嚴密地驗證解法的正確性，這種時候我們的解法就是一種不完全歸納，可能對于有些情況，算法得出的結果可能是不對的，但這種解法可能得出部分的解，也是一種不錯的選擇。例一、骨牌覆蓋問題設有一個2n*2n方格組成的棋盤，其中恰有一個方格有缺陷?，F(xiàn)要用下圖所示的L形骨牌覆蓋棋盤上除有缺陷的方格外的所有方格。L形骨牌的4種不同形態(tài)分別標記為1，2，3，4型骨牌如圖所示。

（1）（2）（3）（4）編程任務:

對于給定的及有缺陷的方格位置，編程求出一種用L形骨牌覆蓋2n*2n個方格組成的棋盤的方案[算法分析]規(guī)模小的數(shù)據(jù)分析對于n=1的情況，2＊2的方格棋盤中，有一塊缺陷，則顯然可以用一個L型骨牌來覆蓋。我們分別對2＊2的方格棋盤中的四個格子進行編號如下。1234則若缺陷位置為I，則我們可以用一個5-I號L型骨牌來覆蓋。算法分析對于n=2的情況，我們研究其中一個例子如下：圖中黑色格子為缺陷，我們可以手工得出一個唯一的解如上圖所示。由于圖中的缺陷在右上角，所以右上角2*2格子必可用一個L型骨牌覆蓋（n=1情況）。再仔細分析圖中左上角、左下角和右下角，剛好每個部分都少一格，這些被一塊3型骨牌覆蓋（如上圖中白色部分）。正是這個特例的啟發(fā)，使我們有了如下的建立模型思路。提出問題的數(shù)學模型（猜想）事實上對于任意的N，2n*2n－1能被3整除。

因此我們可以假設對于任意的N，2n*2n方格棋盤中存在一個缺陷，則這個棋盤一定可以被若干個L型骨牌所覆蓋。現(xiàn)在我們要找到一個覆蓋的方案。我們提出以下的猜想模型：我們將棋盤等分成四個部分，確定缺陷的位置號T（左上角、右上角、左下角、右下角），分別用1、2、3、4表示；則缺陷所在的一角是一個2n－1*2n－1的子問題，我們可以用L型骨牌完全覆蓋。對于其它三個部分中每部分靠原圖中心的一個格子，就構成一個L型，就可以一個5-T號的L型骨牌覆蓋，而這三個部分各少一個格子。對這三個部分的覆蓋，也對應一個2n－1*2n－1子問題，可以被完全覆蓋。證明數(shù)學模型的正確性①顯然n=1時，以上模型是正確的；②假設n=2,3,…,k-1時，以上模型是正確的，那么從以上模型的構造過程我們可以證明當n=k時，以上模型是正確的。所以以上的數(shù)學模型是正確的。[算法描述]ProcedureCover(x,y,x1,y2,size);{(x,y)為一個2^size*2^size正方形的棋盤中左上角坐標，(x1,y1)為缺陷的坐標}Begin

計算出(x1,y1)所在的區(qū)域號T；

Fori:=1to4doBegin

計算出每個部分方陣中的左上角坐標(x2,y2)和缺陷坐標(x3,y3)；

IfT=IthenCover(x2,y2,x1,y1,sizediv2)ElseBeginCover(x2,y2,x3,y3,sizediv2);Map[x3,y3]:=5-T;{(x3,y3)格子被5-T號骨牌所覆蓋}End;End;End;例二、乘法難題乘法難題是一種用一行的卡片來玩的單人游戲，每張卡片上有一個正整數(shù)。在游戲者從中拿出一卡片，并且得到一個分數(shù)，它等于被拿走的卡片上的數(shù)與這張卡片左右兩張卡片上的整數(shù)的積。第一張與與最后一張卡片不能被拿出。在最后一次移動后，這行卡片中只剩下兩張。你的目標是怎樣確定拿卡片的順序，以使得總分數(shù)的值最小。例如，有一行的卡片，它上面的數(shù)字為10150205,游戲者可以先取走1這張卡片,然后是20和50,總分數(shù)為10*1*50+50*20*5+10*50*5=500+5000+2500=8000，如果他先拿50,然接著20，最后取出1,總分數(shù)為1*50*20+1*20*5+10*1*5=1000+100+50=1150。輸入輸入文件的第一行包含卡片的總數(shù)N(3<=N<=100)，第二行包含N個范圍在1到100之間的整數(shù)（兩個整數(shù)之間有一個空格）。輸出輸出文件包含一個整數(shù)，為最少的分數(shù)。例二、乘法難題SampleInput61015050205SampleOutput3650

[算法分析]（1）簡單實例的分析同樣，我們先來研究一個N＝3的例子｛10150｝，顯然游戲只有一種玩法，最少的分數(shù)就是這三個整數(shù)的積，即10＊1＊50＝500。接著，我們研究一個N＝4的例子{101205}，游戲有兩種玩法，它們的取數(shù)順序分別為（2,3）與（3,2），這兩種玩法的積分分別為10＊1＊20＋10＊20＊5＝1200和1＊20＊5＋10＊1＊5＝150，最少游戲積分為150。仔細分析，我們會發(fā)現(xiàn)，最后一個取的數(shù)，它總是和原數(shù)列中的第一個與最后一個數(shù)相乘作為最后一步的得分。通過這個例子很容易猜想到一種貪心方法，就是按數(shù)從大到小的順序拿走中間的所有數(shù)。恰巧樣例也可用貪心方法得到解。這時，我們要看能不能找到這個貪心方法的反例。[算法分析]

實事上，很容易找到一個反例，如：{1，5，1，10，200，5}，若按貪心方法得出積分為10＊200＊5＋1＊10＊5＋1＊5＊1＋1＊1＊5＝10070，而若把200這個數(shù)改為最后取，其它取數(shù)的順序不變，則積分為1＊10＊200＋1＊5＊1＋1＊1＊200＋1＊200＊5＝3205。所以貪心方法是不對的，試一試能不能用動態(tài)規(guī)劃算法來解。（2）提出猜想模型

對于一個N張卡片的游戲，拿卡片的順序會影響積分的值，而拿卡片的順序?qū)嶋H上是一個關于(2,3,…,N-1)的一個排列。我們假設策略W是一個最優(yōu)策略，該策略中最后一個拿走的卡片號為K，則W可以轉(zhuǎn)化成W1＋W2＋{k}，其中W1是W中所有小于K的卡號按W中的原來順序組成的一個子策略，W2是W中所有大于K的卡號按W中的原來順序組成的一個子策略。顯然，W1是關于前K個整數(shù)組成的一個子問題的最優(yōu)策略，W2是關于后N-K＋1個整數(shù)組成的問題的最優(yōu)策略，這兩個子問題是相互獨立的。動態(tài)規(guī)劃模型d[I,j]表示子問題第I至第J個之間的整數(shù)的最少的分數(shù)值。（3）模型的正確性驗證事實上，我們可按N個整數(shù)序列的子序列的長度來嚴格劃分出動態(tài)規(guī)劃的階段，子序列作為狀態(tài)。而問題顯然滿足最優(yōu)子問題性質(zhì)，且狀態(tài)[I,K]與狀態(tài)[K,J]是相互獨立的。因此這個動態(tài)規(guī)劃模型是正確的。使用歸納法進行解題教學在信息學奧賽解題教學中，訓練學生使用歸納法進行解題時，要注意做到以下三個方面的訓練：訓練學生“讀懂題目，研究若干實例，得出答案，分析解答”的能力；訓練學生“大膽的進行歸納假設，提出解題的數(shù)學模型”的能力；訓練學生“應用相應的模型的理論對自己的數(shù)學模型進行正確性驗證”的能力。問題分析法

這里所謂的問題分析是指：對于一個問題，我們一般都有一個普通的解決方法，但這種方法解決問題的效率可能很低。此時我們通過對問題進行進一步的分析，發(fā)現(xiàn)原來做法的不足之處，并找到克服的辦法，這樣達到更好的方法來解決問題。PrimePalindromes

回文質(zhì)數(shù)（1S）因為151即是一個質(zhì)數(shù)又是一個回文數(shù)(從左到右和從右到左是看一樣的)，所以151號是回文質(zhì)數(shù)。

寫一個程序來找出范圍[a,b](5<=a<b<=100,000,000)間的所有回文質(zhì)數(shù);PROGRAMNAME:pprimeINPUTFORMAT

第1行:二個整數(shù)a和b.SAMPLEINPUT(filepprime.in)

5500OUTPUTFORMAT

輸出一個回文質(zhì)數(shù)的列表，一行一個。SAMPLEOUTPUT(filepprime.out)

5

7

11

101

131

151

181

191

313

353

373

383算法一（容易想到的方法）

Fori:=atobdo

ifprime(i)andpalindromes(i)thenwriteln(i)

functionprime(i:longint):boolean;var

x:longint;beginprime:=false;forx:=2totrunc(sqrt(i))doifimodx=0thenexit;prime:=true;end;functionpalindromes(i:longint):boolean;vars:string;x,y:integer;begin

str(i,s);x:=1;y:=length(s);while(x<y)and(s[x]=s[y])dobegin

inc(x);dec(y);end;pl:=x>=y;end;PrimePalindromes

回文質(zhì)數(shù)對以上算法的分析：其中prime(i)函數(shù)是判斷i是否為素數(shù)，從2到sqrt(n)進行判斷Palindromes(i)用于判斷i是否為回文該算法對于5－1000000，運行時間就會超過1秒。這時如果我們把條件改為palindromes(i)andprime(i),會發(fā)現(xiàn)，運行時間大大提高。分析原因為回文數(shù)比素數(shù)更少。但對于題目中的極限數(shù)據(jù)5－100000000，運行時間要18.8秒。PrimePalindromes

回文質(zhì)數(shù)因此我們應該著重解決的問題是“如何加快判斷回文”。而原方法中對回文的判斷palindromes(i)的復雜度為近似O（4），對于5－100000000范圍的數(shù)據(jù)逐個進行判斷回文都會超時。得出結論：不能對a-b范圍內(nèi)的所有數(shù)判斷是否回文。于是我們就想出：用構造法直接構造出回文數(shù)。12312321(奇數(shù)位）和123321（偶數(shù)位）PrimePalindromes

回文質(zhì)數(shù)算法二：Fori=1to9999do用i分別構造出奇數(shù)位的回文數(shù)m和偶數(shù)位的回文n，并將它們存入數(shù)組a對a數(shù)組進行排序Fori:=1tonum_of_adoif(i>=a)and(i<=b)and(prime(i))thenwriteln(i)以上的算法最壞的復雜度為：O（lg(20000)），可以在1s內(nèi)出解functiongz(x:integer):longint;

var

t:longint;begint:=x;x:=xdiv10;whilex<>0dobegint:=t*10+xmod10;x:=xdiv10;end;

gz:=t;end;begin

assign(input,'pprime.in');reset(input);readln(a,b);close(input);assign(output,'pprime.out');rewrite(output);if(5>=a)and(5<=b)thenwriteln(5);if(7>=a)and(7<=b)thenwriteln(7);if(11>=a)and(11<=b)thenwriteln(11);ifb>11thenbeginfori:=10to9999dobeginc:=gz(i);if(c>=a)and(c<=b)andss(c)thenwriteln(c);end;end;close(output);end.一個數(shù)被11整除的特征：奇數(shù)位數(shù)字和與偶數(shù)位數(shù)字和的差能否被11整除。所以偶數(shù)位的回文數(shù)會被11整除。如2442算法三：PrimePalindromes

回文質(zhì)數(shù)通過以上的不斷“分析問題－解決問題”的過程，進而產(chǎn)生了新的、好的算法，這就培養(yǎng)了學生的創(chuàng)新精神。這種方法的掌握對學生可以說是終生受用的。當然也會對學生的創(chuàng)新能力的提高有很大的幫助。一題多解、發(fā)散思維輸入一串長為N（N<=20000）的整數(shù)（在0到30000