NOIP初賽復(fù)習(xí)練習(xí).ppt

1、NIOP初賽輔導(dǎo) v1.0beta4,福州八中 林榮輝 ,1.大綱,2,一、初賽內(nèi)容與要求：（#表示普及組不涉及，以下同） 計(jì)算機(jī)基本常識(shí) * 誕生與發(fā)展 *特點(diǎn)*在現(xiàn)代社會(huì)中的應(yīng)用 * 計(jì)算機(jī)系統(tǒng)的基本組成 * 計(jì)算機(jī)的工作原理#*計(jì)算機(jī)中的數(shù)的表示 * 計(jì)算機(jī)信息安全基礎(chǔ)知識(shí) *計(jì)算機(jī)網(wǎng)絡(luò) 計(jì)算機(jī)基本操作 * MS DOS與Windows的使用基礎(chǔ) * 常用輸入/輸出設(shè)備的種類、功能、使用 * 漢字輸入/輸出方法 * 常用計(jì)算機(jī)屏示信息,全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽競(jìng)賽大綱,3,一、初賽內(nèi)容與要求：（#表示普及組不涉及，以下同） 程序設(shè)計(jì)基本知識(shí) 程序的表示 * 自然語(yǔ)言的描

2、述 * PASCAL或BASIC語(yǔ)言 數(shù)據(jù)結(jié)構(gòu)的類型 * 簡(jiǎn)單數(shù)據(jù)的類型 * 構(gòu)造類型：數(shù)組、字符串 * 了解基本數(shù)據(jù)結(jié)構(gòu)（線性表、隊(duì)列與棧） 程序設(shè)計(jì) * 結(jié)構(gòu)化程序的基本概念 * 閱讀理解程序的基本能力 * 具有完成下列過(guò)程的能力： 現(xiàn)實(shí)世界（指知識(shí)范疇的問(wèn)題） 信息世界（表達(dá)解法） 計(jì)算機(jī)世界（將解法用計(jì)算機(jī)能實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)和算法描述出來(lái)）,全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽競(jìng)賽大綱,4,一、初賽內(nèi)容與要求：（#表示普及組不涉及，以下同） 基本算法處理 * 簡(jiǎn)單搜索 * 字串處理 * 排序 * 查找 * 統(tǒng)計(jì) * 分類 * 合并 * 簡(jiǎn)單的回溯算法 * 簡(jiǎn)單的遞歸算法,全國(guó)青少年

3、信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽競(jìng)賽大綱,5,二、復(fù)賽內(nèi)容與要求： 在初賽的內(nèi)容上增加以下內(nèi)容 計(jì)算機(jī)軟件 *操作系統(tǒng)的使用知識(shí) *編程語(yǔ)言的使用 數(shù)據(jù)結(jié)構(gòu) *結(jié)構(gòu)類型中的記錄類型 *文件（提高組必須會(huì)使用文本文件輸入） *鏈表 *樹(shù) *圖#,全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽競(jìng)賽大綱,6,二、復(fù)賽內(nèi)容與要求： 在初賽的內(nèi)容上增加以下內(nèi)容 程序設(shè)計(jì) *程序設(shè)計(jì)能力 *設(shè)計(jì)測(cè)試數(shù)據(jù)的能力 *運(yùn)行時(shí)間和占用空間的估算能力# 算法處理 *排列組合的應(yīng)用 *進(jìn)一步加深回溯算法、遞歸算法 *分治法 *搜索算法：寬度、深度優(yōu)先算法 *表達(dá)式處理：計(jì)算、展開(kāi)、化簡(jiǎn)等# *動(dòng)態(tài)規(guī)劃#,全國(guó)青少年信息學(xué)

4、（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽競(jìng)賽大綱,7,三、初賽試題類型：注：試題語(yǔ)言兩者選一 （程序設(shè)計(jì)語(yǔ)言：基本BASIC或PASCAL） *判斷 *填空 *完善程序 *讀程序?qū)戇\(yùn)行結(jié)果 *問(wèn)答,全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽競(jìng)賽大綱,NIOP初賽輔導(dǎo),福州八中 林榮輝 ,2.計(jì)算機(jī)基礎(chǔ)選擇題,9,計(jì)算機(jī)的發(fā)展和應(yīng)用,1946年2月，在美國(guó)賓夕法尼亞大學(xué)誕生了世界上第一臺(tái)電子計(jì)算機(jī)ENIAC（Electronic Numerical Integrator And Computer），這臺(tái)計(jì)算機(jī)占地170平方米，重30噸，用了18000多個(gè)電子管，每秒能進(jìn)行5000次加法運(yùn)算。,復(fù)雜指令計(jì)算機(jī)C

5、ISC,精簡(jiǎn)指令計(jì)算機(jī)RISC,10,計(jì)算機(jī)體系的提出,馮諾依曼理論 1944年，美籍匈牙利數(shù)學(xué)家 馮諾依曼 提出 計(jì)算機(jī)基本結(jié)構(gòu)和工作方式的設(shè)想，為計(jì)算機(jī) 的 誕生和發(fā)展提供了理論基礎(chǔ)。時(shí)至今日，盡 管 計(jì)算機(jī)軟硬件技術(shù)飛速發(fā)展，但計(jì)算機(jī)本身 的 體系結(jié)構(gòu)并沒(méi)有明顯的突破，當(dāng)今的計(jì)算機(jī) 仍屬于馮諾依曼架構(gòu)。,輸 入 設(shè) 備,輸 出 設(shè) 備,運(yùn)算器,存儲(chǔ)器,控制器,計(jì)算機(jī)的類型,大型通用機(jī),巨型機(jī),小型機(jī),工作站,微型機(jī),網(wǎng)絡(luò)計(jì)算機(jī),11,我國(guó)的計(jì)算機(jī)發(fā)展情況*,我國(guó)從1956年開(kāi)始計(jì)算機(jī)的科研和教學(xué)工作； 1960年我國(guó)第一臺(tái)自行設(shè)計(jì)的通用電子計(jì)算機(jī)107機(jī)誕生； 1964年我國(guó)研制成大型通

6、用電子計(jì)算機(jī)119機(jī)； 1983年每秒運(yùn)行一億次的銀河巨型計(jì)算機(jī)在國(guó)防科技大學(xué)誕生； 1992年研制成功每秒運(yùn)行10億次的“銀河II”巨型計(jì)算機(jī)； 1997年又研制成功每秒運(yùn)行130億次的“銀河III”巨型計(jì)算機(jī)； 我國(guó)較有名的微型計(jì)算機(jī)品牌有：“聯(lián)想”、“長(zhǎng)城”、“方正”等；,“三金”工程,金橋工程,金關(guān)工程,金卡工程,12,計(jì)算機(jī)系統(tǒng)（硬件）,存儲(chǔ)器,內(nèi) 存,地址 譯碼器,讀寫控制電路,數(shù)據(jù)總線,讀寫命令,出入內(nèi)存的信息,地址總線,存貯器地址,存儲(chǔ)器,內(nèi)存,外存,硬盤,光盤,半導(dǎo)體,13,計(jì)算機(jī)系統(tǒng)（硬件）,CPU,程序計(jì)數(shù)器,地址寄存器,運(yùn)算器,數(shù)據(jù)寄存器,操作控制器,指令譯碼器,指令寄

7、存器,內(nèi)存,ALU,DR,IR,PC,CPU結(jié)構(gòu),14,計(jì)算機(jī)系統(tǒng)（軟件）,計(jì)算機(jī)軟件,應(yīng)用軟件,系統(tǒng)軟件,數(shù)據(jù)庫(kù)系統(tǒng),語(yǔ)言程序,操作系統(tǒng),各種功能的軟件,應(yīng)用軟件必須有系統(tǒng)軟件的支持,操作系統(tǒng),MS-DOS,WINDOWS,UNIX,Linux,Mactonish-OS,數(shù)據(jù)庫(kù),Oracle,Foxpro,SQL,Access,15,1101101.0101 =1*20+0*21+1*22+1*23+0*24+1*25+1*26+0*2-1+1*2-2+0*2-3+1*2-4 =109.3125,信息的表示與存儲(chǔ),進(jìn)制轉(zhuǎn)換,R進(jìn)制數(shù)轉(zhuǎn)10進(jìn)制,2進(jìn)制轉(zhuǎn)10進(jìn)制,（1101101.0101）2

8、,（1101101.0101）B,16,3506.2 =6*80+0*81+5*82+3*83+2*8-1 =1862.25,8進(jìn)制轉(zhuǎn)10進(jìn)制,（3506.2）8,0.2A =2*16-1+10*16-2 =0.1640625,16進(jìn)制轉(zhuǎn)10進(jìn)制,（0.2A）H,17,進(jìn)制轉(zhuǎn)換,10進(jìn)制數(shù)轉(zhuǎn)R進(jìn)制,57,28,14,1,7,3,2,2,0,2,2,2,2,1,0,0,1,1,1,余數(shù),5710=1110012,整數(shù)部分,小數(shù)部分,0.3125*2=0.625 0.625*2=1.25 0.25*2=0.5 0.5*2=1,0.312510=0.01012,取整,18,進(jìn)制轉(zhuǎn)換,2、8、16進(jìn)制

9、互轉(zhuǎn),指數(shù)=位數(shù),1011010.102轉(zhuǎn)換為8進(jìn)制和16進(jìn)制 001 011 010 . 100 1 3 2 . 4 132.48 0101 1010.1000 5 A . 8 5A.816,8=23,16=24,F7.28H轉(zhuǎn)換為2進(jìn)制 F 7 . 2 8 1111 0111 . 0010 1000 F7.2816=11110111.001012 25.638轉(zhuǎn)換為2進(jìn)制數(shù) 2 5 . 6 3 010 101. 110 011 25.638=10101.1100112,24,23,19,計(jì)算機(jī)中數(shù)的表示法,在生活中表示數(shù)的時(shí)候一般都是把正數(shù)前面加一個(gè)“+”，負(fù)數(shù)前面加一個(gè)“-”，但是在數(shù)字

10、設(shè)備中，機(jī)器是不認(rèn)識(shí)這些的，我們就把“+”用“0”表示，“-”用“1”表示。,原碼,-1101001原=11101001,原數(shù)據(jù)加上符號(hào)位,反碼,-1101001反=11101001反 =10010110,除符號(hào)位，按位取反,補(bǔ)碼,-1101001補(bǔ)=11101001補(bǔ) =10010111,除符號(hào)位，按位取反再加1,正數(shù)的原反補(bǔ)是一樣的,20,信息存儲(chǔ)單位,位,度量數(shù)據(jù)的最小單位，表示一位2進(jìn)制信息,bit，縮寫為b,注意小寫,字節(jié),字節(jié)是信息存儲(chǔ)中最常用的基本單位,一字節(jié)由8位2進(jìn)制數(shù)組成,1 Byte=8 bit,KB（千字節(jié)） 1K=1024 Byte MB(兆) 1M=1024K GB

11、（千兆字節(jié)） 1G=1024M,21,非數(shù)值信息的表示,西文,中文,美國(guó)信息交換標(biāo)準(zhǔn)代碼,國(guó)家標(biāo)準(zhǔn)信息交換用漢字編碼,簡(jiǎn)稱“國(guó)標(biāo)碼”,國(guó)標(biāo)碼共6763個(gè)漢字，一級(jí)漢字3755個(gè)，二級(jí)漢字3008個(gè),即ASCII碼. 用7位2進(jìn)制表示，有128個(gè)狀態(tài),常用碼：A=65;0=48;a=97,按拼音,按部首,22,練習(xí),練習(xí)1微型計(jì)算機(jī)的問(wèn)世是由于( ) 的出現(xiàn)。 A)中小規(guī)模集成電路 B)晶體管電路 C) (超)大規(guī)模集成電路 D) 電子管電路 練習(xí)2中央處理器(CPU)能訪問(wèn)的最大存儲(chǔ)器容量取決于( ) 。 A)地址總線 B)數(shù)據(jù)總線 C) 控制總線 D) 實(shí)際內(nèi)存容量 練習(xí)3微型計(jì)算機(jī)中，(

12、) 的存取速度最快。 A)高速緩存 B)外存儲(chǔ)器 C) 寄存器 D) 內(nèi)存儲(chǔ)器 練習(xí)4在計(jì)算機(jī)硬件系統(tǒng)中，cache是( )存儲(chǔ)器。 A)只讀 B)可編程只讀 C)可擦除可編程只讀 D)高速緩存,寄存器高速緩存內(nèi)存儲(chǔ)器外存儲(chǔ)器,23,練習(xí)5若我們說(shuō)一個(gè)微機(jī)的CPU是用的PII300，此處的300確切指的是( )。 A)CPU的主時(shí)鐘頻率 B)CPU產(chǎn)品的系列號(hào) C)每秒執(zhí)行300百萬(wàn)條指令 D)此種CPU允許最大內(nèi)存容量 練習(xí)6計(jì)算機(jī)主機(jī)是由CPU與（）構(gòu)成的。 控制器B. 輸入、輸出設(shè)備C. 運(yùn)算器D.內(nèi)存儲(chǔ)器 練習(xí)7計(jì)算機(jī)系統(tǒng)總線上傳送的信號(hào)有（ ）。 A.地址信號(hào)與控制信號(hào)B. 數(shù)據(jù)信號(hào)

13、、控制信號(hào)與地址信號(hào) C.控制信號(hào)與數(shù)據(jù)信號(hào)D. 數(shù)據(jù)信號(hào)與地址信號(hào) 練習(xí)8不同類型的存儲(chǔ)器組成了多層次結(jié)構(gòu)的存儲(chǔ)器體系，按存取速度從快到慢的排列是（ ）。 A.快存/輔存/主存B. 外存/主存/輔存C. 快存/主存/輔存D. 主存/輔存/外存,24,練習(xí)9微機(jī)內(nèi)存儲(chǔ)器的地址是按（ ）編址的。 A.二進(jìn)制位 B. 字長(zhǎng) C.字節(jié) D. 微處理器的型號(hào) 練習(xí)10在微機(jī)中，通用寄存器的位數(shù)是（ ）。 A 8 位 B16位 C.計(jì)算機(jī)字長(zhǎng) D32位 練習(xí)11不同的計(jì)算機(jī)，其指令系統(tǒng)也不同，這主要取決于（ ）。 A 所用的操作系統(tǒng) B. 系統(tǒng)的總體結(jié)構(gòu) C所用的CPU D所用的程序設(shè)計(jì)語(yǔ)言 練習(xí)12下

14、列說(shuō)法中，哪個(gè)（些）是錯(cuò)誤的（ ）。 A）程序是指令的序列，它有三種結(jié)構(gòu)：順序、分支和循環(huán)。 B）數(shù)據(jù)總線決定了中央處理器CPU所能訪問(wèn)的最大內(nèi)存空間的大小。 C）中央處理器CPU內(nèi)部有寄存器組，用來(lái)儲(chǔ)存數(shù)據(jù)。 D）不同廠家生產(chǎn)的CPU所能處理的指令集是相同的。 E）數(shù)據(jù)傳輸過(guò)程中可能會(huì)出錯(cuò)，奇偶校驗(yàn)法可以檢測(cè)出數(shù)據(jù)中哪一位在傳輸中出了差錯(cuò)。 練習(xí)13CPU訪問(wèn)內(nèi)存的速度比訪問(wèn)下列哪個(gè)（些）存儲(chǔ)設(shè)備要慢（AD ）。 A）寄存器 B）硬盤 C）軟盤 D）高速緩存 E）光盤,在字節(jié)增加一位，按位相加判斷奇偶，以便校對(duì),25,練習(xí)14下列哪個(gè)不是CPU（中央處理單元）（ ）。 A. Intel It

15、anium B. DDR SDRAM C. AMD Athlon64 D. AMD Opteron E. IBM Power 5 練習(xí)15下列說(shuō)法中錯(cuò)誤的是（ ）。 A.CPU的基本功能就是執(zhí)行指令。 B.CPU訪問(wèn)內(nèi)存的速度快于訪問(wèn)高速緩存的速度。 C.CPU的主頻是指CPU在1秒內(nèi)完成的指令周期數(shù)。 D.在一臺(tái)計(jì)算機(jī)內(nèi)部，一個(gè)內(nèi)存地址編碼對(duì)應(yīng)唯一的一個(gè)內(nèi)存單元。 E.數(shù)據(jù)總線的寬度決定了一次傳遞數(shù)據(jù)量的大小，是影響計(jì)算機(jī)性能的因素之一。 練習(xí)16用靜電吸附墨粉后轉(zhuǎn)移到紙張上，是哪種輸出設(shè)備的工作方式（ ）。 針式打印機(jī) B. 噴墨打印機(jī) C. 激光打印機(jī) D. 筆式繪圖儀 E. 噴墨繪圖儀

16、 練習(xí)17以下哪個(gè)不是計(jì)算機(jī)的輸出設(shè)備（ ）。 A. 音箱 B. 顯示器 C. 打印機(jī) D. 掃描儀 E. 繪圖儀,原復(fù)習(xí)文檔答案有誤,26,練習(xí)18十進(jìn)制數(shù)11/128可用二進(jìn)制數(shù)碼序列表示為( ) 。 A)1011/1000000 B)1011/100000000 C) 0.001011 D) 0.0001011 練習(xí)19算式(2047)10(3FF)16(2000)8的結(jié)果是( ) 。 A)(2048)10 B)(2049)10 C) (3746)8 D) (1AF7)16 練習(xí)20已知x=(0.1011010)2,則x/2 =( ) 2 。 0.1011101. B) 11110110

17、 C) 0.0101101 D) 0.100110 練習(xí)21已知A=35H,則A05HA3OH的結(jié)果是:( ) 。 A)3OH B)05H C) 35H D) 53H 練習(xí)22x補(bǔ)碼=10011000，其原碼為( ) A)011001111 B)11101000 C)11100110 D)01100101 練習(xí)23下列無(wú)符號(hào)數(shù)中，最小的數(shù)是（） A.（11011001）2B.(75)10C.(37)8D.(2A)16,1023,1024,and與; or或; not非;,NIOP初賽輔導(dǎo),福州八中 林榮輝 ,3.多媒體選擇填空題,28,多媒體技術(shù),多媒體計(jì)算機(jī),音頻信號(hào)處理,圖形和圖像處理,視

18、頻處理,視頻輸入輸出,日常辦公,通信網(wǎng)絡(luò),外部設(shè)備,多媒體技術(shù)個(gè) 人計(jì)算機(jī)系統(tǒng),29,光盤,CD,DVD,BR-DVD,VCD,Compact Disc,Digital CD,Video CD,Blue-Ray DVD,CD表面,OFF,光感測(cè)器,0,解碼電路,ON,光感測(cè)器,1,解碼電路,棱鏡,棱鏡,激光束,激光束,凸,凹,導(dǎo)出區(qū),數(shù)據(jù)區(qū),導(dǎo)入?yún)^(qū),目錄區(qū),光盤讀取數(shù)據(jù)原理,30,人眼睛能分辨的顏色大約有16000種，這么多顏色我們用24bit來(lái)描述，這種顯示模式就稱為真彩色。,自然界常見(jiàn)的各種顏色光，都可由紅、綠、藍(lán)3種顏色按不同比例配制而成，反之亦可三原色原理,圖形圖像,彩色的描述,亮度,

19、色調(diào),飽和度,明亮程度,顏色種類,顏色純度,圖形圖像分類,位圖,矢量圖,點(diǎn)陣像素,幾何元素,拉伸變形,拉伸不變形,圖像占用 空間計(jì)算,圖像存儲(chǔ)空間=分辨率*顏色（*數(shù)據(jù)壓縮比）,點(diǎn)陣大小,位數(shù),某圖片分辨率為1024*768，256色，則他的存儲(chǔ)空間=1024*768*8=6291456bit 他的大小=空間/8=786432Byte786K,28=256,真彩色,224=16M,31,練習(xí),練習(xí)1目前，圖像文件格式有很多種，其中，windows附件所帶的畫圖程序默認(rèn)的圖形格式是（ ）；Photoshop的標(biāo)準(zhǔn)文件格式是（ ）；JPG文件的主要特點(diǎn)是（） ：JPG B.PSD C.BMP D.

20、GIF 2 : JPG B.PSD C.BMP D.GIF 3 : A.圖像質(zhì)量高 B.圖像色彩數(shù)高 C.圖像占用空間大 D.壓縮效率很高 練習(xí)2若視頻信號(hào)的每幅黑白圖像均為256級(jí)灰度，1024*768的點(diǎn)陣表示，當(dāng)數(shù)據(jù)的壓縮比為30時(shí)，每幅圖像的存儲(chǔ)空間為1（ ）比特。以每秒25幅的方式播出時(shí)，容量為600M比特的視頻圖像以壓縮形式在網(wǎng)絡(luò)上需傳輸2（ ）秒，傳輸速度不應(yīng)低于每秒3（ ）比特。 1： 1024*768*8/300.2MB 2： 600/(0.2MB*25)=120s 3: 0.2MB*25=5MB,顏色？,32,網(wǎng)絡(luò)基礎(chǔ),網(wǎng)絡(luò)歷程,1.“主機(jī)-中端”系統(tǒng),多臺(tái)設(shè)備連接到一臺(tái)中

21、央計(jì)算機(jī),雛形,2.ARPANET,阿帕網(wǎng),里程碑,3.廣域網(wǎng) （1) 已知中綴表達(dá)式：A+B*C/D 求它的前綴表達(dá)式和后綴表達(dá)式？ （2）已知前綴表達(dá)式：+A*BC 注表示一元運(yùn)算符負(fù)號(hào)，即A表示-A 求它的中綴表達(dá)式和后綴表達(dá)式？ 解答：畫（二叉）表達(dá)式樹(shù)。 （1）的結(jié)果：+A*B/CD；ABCD/*+ （2）的結(jié)果：（-A）+B*（-C）；ABC*+,74,例題6已知一個(gè)數(shù)列U1,U2,U3.Un.,往往可以找到一個(gè)最小的K值和K個(gè)數(shù)a1,a2,.,ak,使得數(shù)列從某項(xiàng)開(kāi)始都滿足:U(n+k)=a1*U(n+k-1)a2*U(n+k-2)+.akUn (式A) 例如數(shù)列 1,1,2,3

22、,5.可以發(fā)現(xiàn):當(dāng)K=2,a1=1,a2=1時(shí),從第3項(xiàng)起(N=1)滿足: U(n+2)U(n+1) Un 試對(duì)數(shù)列13 ,23 ,33 ,.,N3,求K和a1,a2,.ak,使得式A成立。 解答：解方程，先設(shè)K=2，列出方程組： a1*23+a2*13=33 a1*33+a2*23=43 以上方程組無(wú)整數(shù)解。再設(shè)K=3，列出方程組： a1*02+a2*12+a3*22=32 a1*12+a2*22+a3*32=42 a1*22+a2*32+a3*42=52 以上方程的整數(shù)解為：a1=1，a2=-3，a3=3，此時(shí)K=3,75,例題7設(shè)有一個(gè)共有n級(jí)的樓梯，某人每步可走1級(jí)，也可走2級(jí)，也可走

23、3級(jí)，用遞推公式給出某人從底層開(kāi)始走完全部樓梯的走法。例如：當(dāng)n=3時(shí)，共有4種走法，即1+1+1,1+2,2+1,3。 解答：兩種方法，一是“猜”+“湊”，從具體的n=1,2,3算起，只能算比較簡(jiǎn)單的，容易錯(cuò)；二是用組合數(shù)學(xué)和歸納法進(jìn)行推導(dǎo)，一般先假設(shè) F（n）= a*F（n-1）+b*F（n-2）+c*F（n-3）+， 然后算a，b，c直到某個(gè)系數(shù)=0就結(jié)束，再代入式子中。 F（1）1 F（2）2 F（3）4 F（N）F（N3）F（N2）F（N1） （N4）,76,例題8將N個(gè)紅球和M個(gè)黃球排成一行。例如:N=2,M=3可得到以下6種排法:紅紅黃黃黃 紅黃紅黃黃 紅黃黃紅黃 黃紅紅黃黃 黃

24、紅黃紅黃 黃黃黃紅紅。問(wèn)題：當(dāng)N=4,M=3時(shí)有多少種不同排法?(不用列出每種排法) 解答：35 例題9在書架上放有編號(hào)為1 ，2 ，n的n本書?，F(xiàn)將n本書全部取下然后再放回去，當(dāng)放回去時(shí)要求每本書都不能放在原來(lái)的位置上。例如：n = 3時(shí)： 原來(lái)位置為：1 2 3 放回去時(shí)只能為：3 1 2 或 2 3 1 這兩種 問(wèn)題：求當(dāng)n = 5時(shí)滿足以上條件的放法共有多少種？（不用列出每種放法） 解答：f(n)=n*f(n-1) 1(n1,且n為偶數(shù)時(shí)取+，n為奇數(shù)時(shí)取-) f(1)=0 所以，當(dāng)n=5時(shí)，滿足以上條件的方法共有44種。,NIOP初賽輔導(dǎo),福州八中 林榮輝 ,6.閱讀程序部分,78,

25、閱讀和分析程序,由于初賽沒(méi)有上機(jī)條件，因此只能通過(guò)人工閱讀程序得到計(jì)算結(jié)果。閱讀一份沒(méi)有任務(wù)說(shuō)明的程序是十分費(fèi)力的工作。在閱讀時(shí)，由于疏忽或考慮不周全可能對(duì)程序的理解出現(xiàn)各種各樣的偏差，導(dǎo)致錯(cuò)誤的計(jì)算結(jié)果。正確的閱讀方法和熟練的分析技巧能大大縮短理解程序原意的時(shí)間。,79,1.直接推理/模擬,例題1 var m,n,i:integer; t:extended; begin readln(n,m); t:=1; for i:=1 to m do t:=t*(n-i+1)/i; writeln(t:0:0); end. 輸入 10 5 輸出_,extended擴(kuò)展類型，即使不知道，也不會(huì)影響計(jì)算,

26、252,80,2.動(dòng)態(tài)模擬,例題2 var i,j:integer; a:array1.3,1.3of integer; begin for i:=1 to 3 do begin for j:=1 to 3 do begin if i=3 then ai,j:=ai-1,ai-1,j+1; else ai,j:=j; writeln(ai,j); end; writeln; end; readln; end. 輸出_,直接模擬的進(jìn)化，過(guò)程中記錄現(xiàn)場(chǎng)的變化,81,例題3 var a,d:array1.100of integer; n,i,j,k,x,s:integer; begin n:=5;a

27、1:=1;d1:=1; for i:=1 to n do begin s:=i+1;x:=0; for j:=1 to n+1-i do begin k:=s+x;x:=x+1;aj+1:=aj+k; writeln(aj, ); end; writeln(.);di+1:=di+i;a1:=di+1; end; end.,1 3 6 10 15 . 2 5 9 14 . 4 8 13 . 12 . 11 .,82,3.觀察輸入,例題4 label 10,20,30; var s,p:string; i,k,n,j,m:integer; begin readln(s);n:=length(s)

28、; readln(p);m:=length(p); i:=0; 10: i:=i+1; j:=i; k:=1; 20: if sjpk then begin if in-m+1 then goto 10; i:=0; goto 30; end; else if km then begin j:=j+1;k:=k+1; goto 20; end; 30: writeln(i); end. 輸入 asabcdffdin fdi 輸出_,遇到?jīng)]見(jiàn)過(guò)的語(yǔ)句不必慌張，觀察語(yǔ)句的實(shí)現(xiàn)作用,看到goto，猜想是不是跳轉(zhuǎn)語(yǔ)句,兩段字符串的輸入，猜想是不是比較子序列,繼續(xù)觀察20這步，發(fā)現(xiàn)是找匹配字串的位置,8

29、,NIOP初賽輔導(dǎo),福州八中 林榮輝 ,7.完善程序部分,84,初賽中，程序填空題的內(nèi)容通常有以下幾個(gè)方面,變量方面的填空； 循環(huán)方面的填空； 分支轉(zhuǎn)移方面的填空； 主程序和子程序關(guān)系方面的填空； 輸入和輸出方面的填空。,85,1.完善不含子程序的程序,例題1求元素之和最大的子方陣：在m*n（m,n=20）的正整數(shù)方陣中，找出一個(gè)p*q的子陣(1=p=m,1=q=n)使其元素之和最大。例如，下面給出的矩陣中，元素之和最大為一個(gè)2*3的子陣,86,程序(求p*q最大方陣元素之和子陣),var a:array1.20,1.20of integer; m,n,p,q,i,j,max,p1,q1,s,

30、i1,j1:integer; begin for i:=1 to 20 do for j:=1 to 20 do ai,j:=0; readl(m,n); for i:=1 to m do begin for j:=1 to n do read(ai,j); readln; end; readln(p,q); max:=0;,for i:=1 to m-p+1 do for j:=1 to n-q+1 do begin _; for i1:=i to p+i-1 do for j1:= j to q+j-1 do _; if smax then begin _; p1:=i; q1:=j; e

31、nd; end; for i:=p1 to _do begin for j:=q1 to _do writeln(ai,j:3); writeln; end; readln; end.,方陣清零,根據(jù)規(guī)模讀方陣,根據(jù)規(guī)模讀子陣，計(jì)數(shù)器初始化,窮舉子陣,由 i+p-1=m 得 i=m-p+1,因窮舉且無(wú)數(shù)組供 數(shù)據(jù)存放故累加無(wú) 望推得此處必定為 累加數(shù)之初始化,s:=0,累加,s:=s+ai1,j1,崗哨,max:=s,記錄位置,由 i+p-1 得 p1+p-1,p1+p-1,q1+q-1,87,例題2以下程序完成對(duì)數(shù)組每個(gè)元素向后移動(dòng)n個(gè)單位。數(shù)組元素的下標(biāo)依次為0到m-1，對(duì)任意一個(gè)數(shù)組元素

32、ai而言，他的值移動(dòng)后將存儲(chǔ)在數(shù)組元素a(i+n)mod m中。 例如，m=10，n=3，移動(dòng)前數(shù)組中數(shù)據(jù)如下第一行，運(yùn)行后數(shù)據(jù)如下第二行。 0 3 86 20 27 67 31 16 37 42 16 37 42 0 3 86 20 27 67 31 分析：循環(huán)鏈移動(dòng)為ai-a(i+n) mod m-a(i+n+n) mod m-a(i+3*n) mod m-.-ai 移動(dòng)前注意判斷是否已經(jīng)移動(dòng)過(guò)，避免重復(fù)移動(dòng)。,即i+2*n,88,程序(數(shù)組循環(huán)鏈),const maxm=10000; var i,k,m,n,rest,start,temp:longint; a:array0.maxm o

33、f longint; begin randomize; write(input m,n:); readln(m,n); for i:=0 to m-1 do ai:=random(100); writeln(before move); for i:=0 to m-1 do write(ai:5); writeln; rest:=m;start:=0;,while _do begin k:=start; repeat k:=(k+n) mod m until k=start; if _then begin temp:=ak; repeat ak:=a(m*n+k-n)mod m; k:=(m*n

34、+k-n)mod m; _ until k=start; _ end; _ end; writeln(after move); for i:=0 to m-1 do write(ai:5); writeln; end.,下標(biāo)和移動(dòng)單位,輸出初始值,看變量名猜含義： rest(余下未移動(dòng)) start(首元素),仍然有余下的數(shù),含mod參考題目 猜想k是當(dāng)前指針,追加猜想start 為移動(dòng)起始元素,眼前推斷不能，暫留,看變量名猜含義2： temp(暫存？),移動(dòng)開(kāi)始,下面是移動(dòng)，那么這里應(yīng)該就是判斷整條鏈?zhǔn)欠褚呀?jīng)移動(dòng),k由start起，不斷后移，直到鏈頭(kstart表示原start位置已移動(dòng)；

35、k=start表示未移動(dòng)過(guò)）,k=start,rest0,移一個(gè)，少一個(gè),rest：=rest-1,最后temp里的數(shù) 給新的astart或者ak,a(k+n) mod m:=temp,尋找下一個(gè)鏈,inc（start）,89,2.完善含子程序結(jié)構(gòu)的程序,例題3用09中的n(1=n=10)個(gè)數(shù)字填入如下乘法運(yùn)算的*處，數(shù)字可重復(fù)使用，且所使用的數(shù)字至少有一個(gè)是素?cái)?shù)，要求輸出滿足下列算式的方案數(shù)。函數(shù)有作用提示 * * * X * * * * * * * * * * * *,90,程序（乘法填空）,const p:set of 0.9=2,3,5,7; var s:set of 0.9; n:i

36、nteger; ans:longint; procedure init; var i:integer; t:byte; begin readln(n); s:=; for i:=1 to n do begin read(t); s:=s+t; end; end;,判斷x是否滿足條件,function ok(x,l:integer):boolean; var t:byte; begin ok:=false; if _l then exit; while x0 do begin t:=x mod 10; if not (t in s) then exit; x:=x div 10; end; ok

37、:=true; end;,素?cái)?shù)集,也是整型,集成操作數(shù)集,exit結(jié)束子程序 break結(jié)束循環(huán),不等于1的時(shí)候退出函數(shù)，猜想是位數(shù),求位數(shù)我們引入對(duì)數(shù)log,logab可以理解為求a的多少次方等于b，即ax=b，求x,那么，一個(gè)多位數(shù)的位數(shù)可以表示為 trunc(log10 x)+1,如584在100和1000之間，即102 ,103,求的trunc（2.XX）+1為3,pascal里對(duì)數(shù)不方便寫，我們改寫為trunc(ln(x)/ln(10)+1; 利用的對(duì)數(shù)的換底公式： logaN=logbN/logba. log10 x可以寫成ln(x),trunc(ln(x)/ln(10)+1,這里對(duì)10取模印證了我們對(duì)位數(shù)的猜測(cè),91,判斷x中是否包含素?cái)?shù),function inset(x:integer):boolean; var t:byte; begin inset:=false; while _do begin t:=x mod 10; if t in p then begin inset:=true; exit; end; _; end; end;,procedure work; var i,i1,i2,i3,j1,j2: