信息學(xué)奧林匹克競(jìng)賽

1、信息學(xué) 奧林匹克競(jìng)賽2014.03.16u交流內(nèi)容：一一. . 信息學(xué)奧林匹克競(jìng)賽賽事介紹信息學(xué)奧林匹克競(jìng)賽賽事介紹二二. . 目前我省信息學(xué)奧賽開(kāi)展情況目前我省信息學(xué)奧賽開(kāi)展情況三三. . 考試內(nèi)容考試內(nèi)容四四. . 學(xué)生的選拔與組織學(xué)生的選拔與組織五五. . 輔導(dǎo)進(jìn)度與時(shí)間安排輔導(dǎo)進(jìn)度與時(shí)間安排六六. . 對(duì)輔導(dǎo)老師的一點(diǎn)建議對(duì)輔導(dǎo)老師的一點(diǎn)建議七七. . 問(wèn)題解答問(wèn)題解答 高中階段五科奧林匹克競(jìng)賽：高中階段五科奧林匹克競(jìng)賽： 數(shù)學(xué)、物理、化學(xué)、生物、數(shù)學(xué)、物理、化學(xué)、生物、信息學(xué)信息學(xué)全國(guó)聯(lián)賽（省賽區(qū)）全國(guó)聯(lián)賽（省賽區(qū)）全國(guó)競(jìng)賽全國(guó)競(jìng)賽一 .信息學(xué)奧林匹克競(jìng)賽賽事介紹u1、省賽區(qū)的競(jìng)賽名

2、稱(chēng) 全國(guó)高中數(shù)學(xué)聯(lián)賽；全國(guó)高中數(shù)學(xué)聯(lián)賽； 全國(guó)中學(xué)生物理競(jìng)賽全國(guó)中學(xué)生物理競(jìng)賽(省級(jí)賽區(qū)省級(jí)賽區(qū))； 全國(guó)高中學(xué)生化學(xué)競(jìng)賽全國(guó)高中學(xué)生化學(xué)競(jìng)賽(省級(jí)賽區(qū)省級(jí)賽區(qū))； 全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽； 全國(guó)中學(xué)生生物學(xué)聯(lián)賽。全國(guó)中學(xué)生生物學(xué)聯(lián)賽。 u2. 全國(guó)決賽的名稱(chēng) 中國(guó)數(shù)學(xué)奧林匹克；中國(guó)數(shù)學(xué)奧林匹克； 全國(guó)中學(xué)生物理競(jìng)賽決賽；全國(guó)中學(xué)生物理競(jìng)賽決賽； 全國(guó)高中學(xué)生化學(xué)競(jìng)賽；全國(guó)高中學(xué)生化學(xué)競(jìng)賽； 全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽；全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽； 全國(guó)中學(xué)生生物學(xué)競(jìng)賽。全國(guó)中學(xué)生生物學(xué)競(jìng)賽。 國(guó)家對(duì)獲獎(jiǎng)學(xué)生的政策：u高中2013屆（2010級(jí)）前： 高中

3、階段：高中階段：學(xué)科奧林匹克競(jìng)賽：學(xué)科奧林匹克競(jìng)賽： 下列兩個(gè)之一就具備保送資格：下列兩個(gè)之一就具備保送資格： 省賽區(qū)中獲得一等獎(jiǎng)省賽區(qū)中獲得一等獎(jiǎng) 全國(guó)決賽一、二、三等獎(jiǎng)全國(guó)決賽一、二、三等獎(jiǎng)的應(yīng)屆高中畢業(yè)生的應(yīng)屆高中畢業(yè)生u2011級(jí)開(kāi)始： 參加全國(guó)決賽進(jìn)入國(guó)家集訓(xùn)隊(duì)保送（全國(guó)前參加全國(guó)決賽進(jìn)入國(guó)家集訓(xùn)隊(duì)保送（全國(guó)前50，金牌），金牌） 金銀銅高考加金銀銅高考加20分分 省賽區(qū)聯(lián)賽一等獎(jiǎng)不再具有保送資格省賽區(qū)聯(lián)賽一等獎(jiǎng)不再具有保送資格 大學(xué)有自己的自主招生政策（單獨(dú)）大學(xué)有自己的自主招生政策（單獨(dú)）信息學(xué)奧林匹克競(jìng)賽信息學(xué)奧林匹克競(jìng)賽 面向全國(guó)中學(xué)生的一種競(jìng)賽活動(dòng)，旨在激發(fā)中學(xué)生在計(jì)算機(jī)科

4、學(xué)方面的興趣，培養(yǎng)他們邏輯思維的能力，給那些有才華的學(xué)生提供相互交流和學(xué)習(xí)的機(jī)會(huì)，通過(guò)競(jìng)賽和相關(guān)的活動(dòng)培養(yǎng)和選拔優(yōu)秀的計(jì)算機(jī)后備人才。信息學(xué)奧林匹克競(jìng)賽賽事：信息學(xué)奧林匹克競(jìng)賽賽事：1.NOIP1.NOIP（全國(guó)信息學(xué)奧林匹克聯(lián)賽）（全國(guó)信息學(xué)奧林匹克聯(lián)賽） National Olympiad in Informatics in Provinces 2.NOI 2.NOI （全國(guó)信息學(xué)奧林匹克競(jìng)賽）（全國(guó)信息學(xué)奧林匹克競(jìng)賽） National Olympiad in Informatics3.IOI 3.IOI （國(guó)際信息學(xué)奧林匹克競(jìng)賽）（國(guó)際信息學(xué)奧林匹克競(jìng)賽） International

5、Olympiad in Informatics NOIP分區(qū)聯(lián)賽 初賽：初賽： 10月中旬（周六下午月中旬（周六下午2:30-4:30） 筆試（筆試（100分）分） 資格賽，地市獨(dú)立組織（全國(guó)統(tǒng)一命題，統(tǒng)一時(shí)間）資格賽，地市獨(dú)立組織（全國(guó)統(tǒng)一命題，統(tǒng)一時(shí)間） 復(fù)賽：復(fù)賽： 11月份中旬（第二周月份中旬（第二周,周六、周日上午周六、周日上午8:30-12:00） 兩試（上機(jī)）兩試（上機(jī)） 每試每試3個(gè)題目，每題個(gè)題目，每題100分，共分，共600分分 提交源程序，黑盒子測(cè)試法提交源程序，黑盒子測(cè)試法 各省統(tǒng)一組織考試各省統(tǒng)一組織考試 全國(guó)統(tǒng)一評(píng)測(cè)全國(guó)統(tǒng)一評(píng)測(cè)uNOI全國(guó)賽： 7月底舉行（兩試月底

6、舉行（兩試,每試每試3個(gè)題目，每試個(gè)題目，每試5小時(shí)）小時(shí)） 每個(gè)省選拔隊(duì)員參加每個(gè)省選拔隊(duì)員參加10-15名名 我省從上一年參加我省從上一年參加NOIP的獲得一等獎(jiǎng)的選手中經(jīng)過(guò)兩次的獲得一等獎(jiǎng)的選手中經(jīng)過(guò)兩次選拔賽選拔當(dāng)年參加選拔賽選拔當(dāng)年參加NOI的隊(duì)員的隊(duì)員 4月份，月份，5月份兩次選拔賽月份兩次選拔賽二. 目前我省信息學(xué)奧賽開(kāi)展情況 NOIP 報(bào)名參賽人數(shù)全國(guó)前兩位。報(bào)名參賽人數(shù)全國(guó)前兩位。 一等獎(jiǎng)分?jǐn)?shù)線(xiàn)基本前一等獎(jiǎng)分?jǐn)?shù)線(xiàn)基本前5 一等獎(jiǎng)人數(shù)分配到省（山東一等獎(jiǎng)人數(shù)分配到?。ㄉ綎|50左右，不包括重復(fù)獲獎(jiǎng)）左右，不包括重復(fù)獲獎(jiǎng)） NOI 全國(guó)前全國(guó)前6左右左右 金牌金牌8枚枚(4所學(xué)校所

7、學(xué)校)u全省地市學(xué)校情況：NOIP201376個(gè)一等獎(jiǎng)分布在個(gè)一等獎(jiǎng)分布在29個(gè)學(xué)校個(gè)學(xué)校獲獎(jiǎng)學(xué)生呈分散趨勢(shì)獲獎(jiǎng)學(xué)生呈分散趨勢(shì)傳統(tǒng)成績(jī)較好的學(xué)校，實(shí)力減弱傳統(tǒng)成績(jī)較好的學(xué)校，實(shí)力減弱越來(lái)越多的學(xué)校開(kāi)始著手抓奧賽越來(lái)越多的學(xué)校開(kāi)始著手抓奧賽 信息學(xué)奧林匹克競(jìng)賽屬于信息學(xué)奧林匹克競(jìng)賽屬于智力智力與應(yīng)用計(jì)算機(jī)解題與應(yīng)用計(jì)算機(jī)解題能力能力的的比賽，題目有相當(dāng)?shù)碾y度，解好這類(lèi)題目，需要具備比賽，題目有相當(dāng)?shù)碾y度，解好這類(lèi)題目，需要具備很很強(qiáng)的強(qiáng)的綜合能力綜合能力1.1.觀察和分析問(wèn)題的能力；觀察和分析問(wèn)題的能力；2.2.將實(shí)際問(wèn)題轉(zhuǎn)化為將實(shí)際問(wèn)題轉(zhuǎn)化為數(shù)學(xué)模型數(shù)學(xué)模型的能力；的能力；3.3.靈活地運(yùn)用各

8、種靈活地運(yùn)用各種算法算法的能力；的能力；4.4.熟練編寫(xiě)程序熟練編寫(xiě)程序并將其調(diào)試通過(guò)的能力；并將其調(diào)試通過(guò)的能力；5.5.根據(jù)題目的要求，自己設(shè)計(jì)測(cè)試數(shù)據(jù)，檢查自己的解法是否根據(jù)題目的要求，自己設(shè)計(jì)測(cè)試數(shù)據(jù)，檢查自己的解法是否正確、是否完備的能力正確、是否完備的能力 三. 考試內(nèi)容 能夠參加信息學(xué)競(jìng)賽的選手應(yīng)該具有很強(qiáng)的自學(xué)能力。 需要學(xué)習(xí)有關(guān)組合數(shù)學(xué)、圖論、基本算法、數(shù)據(jù)結(jié)構(gòu)、人工智能搜索算法等知識(shí) 熟練高級(jí)語(yǔ)言和編程技巧，要具備很強(qiáng)的上機(jī)操作能力u要求：掌握一門(mén)計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言掌握一門(mén)計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言(怎樣選擇怎樣選擇)： Pascal C C+數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法一、語(yǔ)言：

9、一、語(yǔ)言：Free pascal Free pascal （c/c+c/c+）基礎(chǔ)）基礎(chǔ) 二、數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)結(jié)構(gòu) 線(xiàn)性表、棧、隊(duì)列、樹(shù)、圖線(xiàn)性表、棧、隊(duì)列、樹(shù)、圖三、算法：三、算法： 高精度運(yùn)算高精度運(yùn)算 排序算法排序算法 搜索算法（搜索算法（dfsdfs，bfsbfs） 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃dpdp 貪心算法、模擬算法等貪心算法、模擬算法等 相關(guān)的數(shù)論知識(shí)相關(guān)的數(shù)論知識(shí) 全國(guó)聯(lián)賽（NOIP）知識(shí)點(diǎn)：主要考察基本數(shù)據(jù)結(jié)構(gòu)與算法的應(yīng)用能力主要考察基本數(shù)據(jù)結(jié)構(gòu)與算法的應(yīng)用能力全國(guó)競(jìng)賽（NOI） 并查集、樹(shù)狀數(shù)組、線(xiàn)段樹(shù)并查集、樹(shù)狀數(shù)組、線(xiàn)段樹(shù) 查找樹(shù)查找樹(shù) 網(wǎng)絡(luò)流網(wǎng)絡(luò)流 幾何算法幾何算法主要考查建立

10、模型和算法的主要考查建立模型和算法的優(yōu)化優(yōu)化能力能力四. 學(xué)生的選拔與組織u信息學(xué)奧賽是一種選拔性競(jìng)賽u不是一般計(jì)算機(jī)知識(shí)的普及。 興趣興趣 能力能力 勤奮勤奮1.1.綜合成績(jī)突出。綜合成績(jī)突出。2.2.扎實(shí)的數(shù)學(xué)基礎(chǔ)。扎實(shí)的數(shù)學(xué)基礎(chǔ)。3.3.很強(qiáng)的自學(xué)能力。很強(qiáng)的自學(xué)能力。4.4.樂(lè)于和同學(xué)合作與交流。樂(lè)于和同學(xué)合作與交流。5.5.能坐得住。能坐得住。學(xué)生自身：外力：家長(zhǎng)和班主任老師的支持家長(zhǎng)和班主任老師的支持u人數(shù)每個(gè)年級(jí)保持在每個(gè)年級(jí)保持在15人左右較好人左右較好開(kāi)始多一點(diǎn)，慢慢的淘汰開(kāi)始多一點(diǎn)，慢慢的淘汰u吸引學(xué)生、培養(yǎng)興趣第一堂課很重要第一堂課很重要信息學(xué)奧賽解決的問(wèn)題： 經(jīng)過(guò)思考能

11、夠得出解決的方法，但是卻很難或者根本不可能用人工的做出來(lái)。 設(shè)計(jì)算法，用計(jì)算機(jī)語(yǔ)言設(shè)計(jì)程序?qū)崿F(xiàn)自己的方法，從而解決問(wèn)題。步驟： 觀察分析問(wèn)題 思考問(wèn)題，得出模型（數(shù)學(xué)模型） 設(shè)計(jì)解決問(wèn)題的算法或者步驟 用計(jì)算機(jī)語(yǔ)言設(shè)計(jì)程序?qū)崿F(xiàn)算法 調(diào)試驗(yàn)證算法的正確性 要將一張要將一張100元的大鈔票，換成等值的元的大鈔票，換成等值的10元、元、5元、元、2元、元、1元一張的小鈔票，每次換成元一張的小鈔票，每次換成40張小鈔票，張小鈔票，每種至少每種至少1張。張。如，有一種換法：如，有一種換法： 10元：元： 1 張張 5元：元： 5 張張 2元：元： 31 張張 1元：元： 3 張張問(wèn)：一共有多少種換法。問(wèn)

12、：一共有多少種換法?！九e例舉例1 1】換錢(qián)問(wèn)題換錢(qián)問(wèn)題舉幾個(gè)例子激發(fā)學(xué)生的學(xué)習(xí)興趣和欲望 1010元：元： a a 張張 ( (不超過(guò)不超過(guò)1010張張) ) 5 5元：元： b b 張張 ( (不超過(guò)不超過(guò)2020張張) ) 2 2元：元： c c 張張 ( (不超過(guò)不超過(guò)5050張張) ) 1 1元：元： d d 張張 ( (不超過(guò)不超過(guò)100100張張) ) 不定方程組：不定方程組： 1010* *a+5a+5* *b+2b+2* *c+d=100c+d=100 a+b+c+d=40a+b+c+d=40 a=1;b=1;c=1;d=1a=1;b=1;c=1;d=1 問(wèn)題轉(zhuǎn)化為：方程組有多

13、少組正整數(shù)解？問(wèn)題轉(zhuǎn)化為：方程組有多少組正整數(shù)解？分析：分析：給學(xué)生代碼：試運(yùn)行給學(xué)生代碼：試運(yùn)行varvar a,b,c,d,n:longint; a,b,c,d,n:longint;beginbegin n:=0; n:=0; for a:=1 to 10 do for a:=1 to 10 do for b:=1 to 20 do for b:=1 to 20 do for c:=1 to 50 do for c:=1 to 50 do for d:=1 to 100 do for d:=1 to 100 do if (10 if (10* *a+5a+5* *b+2b+2* *c+d=

14、100)and(a+b+c+d=40)c+d=100)and(a+b+c+d=40) then n:=n+1; then n:=n+1; writeln(n); writeln(n);end.end. 換成換成50張有多少種換法？張有多少種換法？ 兩張兩張100的換成的換成40張，有多少種換法？張，有多少種換法？ 讓學(xué)生試一試：讓學(xué)生試一試：已知：已知： s=1+1/2+1/3+1/n求：使求：使s的值大于的值大于10時(shí)最小的時(shí)最小的n?！九e例2 2】 求最小的求最小的n n varvar n:longint; n:longint; s:real; s:real; beginbegin s:=

15、0; s:=0; n:=0; n:=0; repeat repeat n n:=:=n+1;n+1; s s:=:=s+1/n;s+1/n; until s10; until s10; writeln(n); writeln(n); end.end.u使s的值大于10時(shí)最小的n? n=123467u使s的值大于15時(shí)最小的n? u使s的值大于30時(shí)最小的n? 知道：計(jì)算機(jī)的計(jì)算范圍是有限的。知道：計(jì)算機(jī)的計(jì)算范圍是有限的。 有兩個(gè)無(wú)刻度標(biāo)志的水杯，分別可裝滿(mǎn)有兩個(gè)無(wú)刻度標(biāo)志的水杯，分別可裝滿(mǎn)x x升和升和y y升的水。設(shè)升的水。設(shè)另一個(gè)水缸，可以用來(lái)向水杯灌水或從水杯向水缸里倒水，兩另一個(gè)水缸

16、，可以用來(lái)向水杯灌水或從水杯向水缸里倒水，兩個(gè)水杯之間也可以相互倒水。已知個(gè)水杯之間也可以相互倒水。已知x x升的水杯開(kāi)始是盛滿(mǎn)水的，升的水杯開(kāi)始是盛滿(mǎn)水的，y y升的杯子是空的，問(wèn)如何通過(guò)倒水和灌水操作，用最少的步升的杯子是空的，問(wèn)如何通過(guò)倒水和灌水操作，用最少的步數(shù)能在數(shù)能在y y升的杯子里量出升的杯子里量出z z升水。升水。YX水缸（足夠的水水缸（足夠的水,未滿(mǎn)）未滿(mǎn)）X=20 Y=15 Z=10 ？Y10【問(wèn)題3】：倒水問(wèn)題開(kāi)始開(kāi)始: 20 0step 1: 5 15step 2: 0 15step 3: 15 0step 4: 15 15step 5: 20 10X Y算法：廣度優(yōu)先

17、搜索算法：廣度優(yōu)先搜索數(shù)據(jù)結(jié)構(gòu)：隊(duì)列數(shù)據(jù)結(jié)構(gòu)：隊(duì)列找學(xué)生回答找學(xué)生回答復(fù)雜一點(diǎn)的還能嗎？復(fù)雜一點(diǎn)的還能嗎？u知識(shí)的講解 任務(wù)驅(qū)動(dòng)任務(wù)驅(qū)動(dòng) 根據(jù)任務(wù)的需要講知識(shí)點(diǎn)根據(jù)任務(wù)的需要講知識(shí)點(diǎn) 避免使用以前大學(xué)老師的講課方式避免使用以前大學(xué)老師的講課方式五. 輔導(dǎo)進(jìn)度與時(shí)間安排u三個(gè)階段： 高一年級(jí)高一年級(jí)：（周六一個(gè)上午：（周六一個(gè)上午3個(gè)小時(shí)）個(gè)小時(shí)） 語(yǔ)言語(yǔ)言 基本算法與數(shù)據(jù)結(jié)構(gòu)（基本的，不要貪多）基本算法與數(shù)據(jù)結(jié)構(gòu)（基本的，不要貪多） 高一假期高一假期 專(zhuān)項(xiàng)強(qiáng)化訓(xùn)練：算法的完善和補(bǔ)充專(zhuān)項(xiàng)強(qiáng)化訓(xùn)練：算法的完善和補(bǔ)充 高二復(fù)賽考試前（高二復(fù)賽考試前（11月份）月份） 模擬訓(xùn)練模擬訓(xùn)練高一u語(yǔ)言部分

18、用什么講什么 粗放型，不要面目俱到 1.三種基本結(jié)構(gòu)（if for while） 2.數(shù)組 結(jié)合滲透：枚舉算法；一種簡(jiǎn)單的排序算法 3.遞歸（自定義函數(shù)與過(guò)程）及簡(jiǎn)單應(yīng)用 慢慢熟練語(yǔ)言（6到7個(gè)半天）u算法與數(shù)據(jù)結(jié)構(gòu)： 1.深度優(yōu)先搜索算法 2.廣度優(yōu)先搜索算法（數(shù)據(jù)結(jié)構(gòu)隊(duì)列） 3.簡(jiǎn)單的動(dòng)態(tài)規(guī)劃算法 4.樹(shù)及其應(yīng)用 5.圖論算法 鄰接矩陣存儲(chǔ)法存數(shù) 兩種最小生成樹(shù)算法: 普里姆算法（prim）;克魯斯卡爾（kruskal） 兩種最短路徑方法算法：弗洛伊德算法：floyed迪杰斯特拉算法：dijkstra,側(cè)重基本知識(shí)，勿貪多，講練結(jié)合側(cè)重基本知識(shí)，勿貪多，講練結(jié)合高一暑假期間（重要的集中學(xué)習(xí)時(shí)間）u算法與數(shù)據(jù)結(jié)構(gòu)的補(bǔ)充和加深（實(shí)用性） 堆的使用 并查集 最短路徑算法spfa，圖的鄰接表存儲(chǔ)方法 動(dòng)態(tài)規(guī)劃 技巧與處理方法建議參加山東省夏令營(yíng)活動(dòng)建議參加山東省夏令營(yíng)活動(dòng) （7月中旬下旬）月中旬下旬）學(xué)校自己訓(xùn)練學(xué)校自己訓(xùn)練u高二開(kāi)學(xué)（9月份，10月份，每周兩次） 10月中旬的初賽月中旬的初賽 根據(jù)具體情況，一般不需專(zhuān)門(mén)準(zhǔn)備根據(jù)具體情況，一般不需專(zhuān)門(mén)準(zhǔn)備 多報(bào)一部分人（參加學(xué)習(xí)是分子多報(bào)一部