算法 零基礎(chǔ)學(xué) 第9章 信息學(xué)奧賽試題精解.ppt

1、零基礎(chǔ)學(xué)算法,第9章：信息學(xué)奧賽試題精解,課程安排,9.1 NOIP普及組試題精解 9.2 NOIP提高組試題精解,9.1 NOIP普及組試題精解,9.1.1 求級(jí)數(shù)之和,9.1 NOIP普及組試題精解,在輸入文件中有n個(gè)整數(shù)，每個(gè)數(shù)都在1500萬之間，從這些數(shù)中選出k個(gè)整數(shù)進(jìn)行相加，可得到不同的組合。 例如：有4個(gè)整數(shù)8、11、12、13，用其中的3個(gè)數(shù)進(jìn)行相加，可得到如下所示的4種組合： 8+11+12=31 8+11+13=32 8+12+13=34 11+12+13=36 在以上的4個(gè)和值中，只有8+11+12=31的結(jié)果為素?cái)?shù)。 現(xiàn)在要求你編寫程序，計(jì)算給定n個(gè)整數(shù)，從中選中k個(gè)整數(shù)

2、進(jìn)行組合相加，其和值為素?cái)?shù)的情況有多少種？,9.1.2 求素?cái)?shù)組合,9.1 NOIP普及組試題精解,在中國(guó)象棋中，卒過了界河以后不僅可以向前移動(dòng)，也可以橫向移動(dòng)?，F(xiàn)在假設(shè)有一個(gè)過河的卒位地圖9-3所示的A點(diǎn)，要使該卒從A點(diǎn)移到B點(diǎn)（目標(biāo)位置）可有多少種不同的路線？,9.1.3 計(jì)算卒的路線,9.1 NOIP普及組試題精解,對(duì)于正式出版的圖書，都必須有一個(gè)ISBN碼。ISBN碼一共有10位數(shù)字，前9位分別表示國(guó)家、出版者、書名號(hào)，最后一位是根據(jù)前9位數(shù)字計(jì)算得來的，作為校驗(yàn)碼使用。一般ISBN的格式如下： 7-118-01984-4 以上ISBN碼中，7表示中國(guó)，118表示國(guó)防工業(yè)出版社，019

3、84代表書名號(hào)，最后一位4表示校驗(yàn)碼。 校驗(yàn)碼是其他9位數(shù)字的求余函數(shù)。計(jì)算方法是：用102這九個(gè)數(shù)分別順序乘以ISBN的前九位數(shù)字，所得乘積之和被模數(shù)11除，其余數(shù)與11的差，即是校驗(yàn)位的數(shù)值。所以，校驗(yàn)位的數(shù)值可能是111中的任何一個(gè)整數(shù)，當(dāng)校驗(yàn)位為10時(shí)，用大寫字母“X”表示；當(dāng)校驗(yàn)位為11時(shí)，用“0”表示。由此可見校驗(yàn)位只能是0、1、2、3、4、5、6、7、8、9、X，恒為一位數(shù)。,9.1.4 檢查校驗(yàn)碼,9.1 NOIP普及組試題精解,六（一）班有幾個(gè)調(diào)皮的同學(xué)，當(dāng)這些同學(xué)坐在相鄰位置（前后或左右相鄰）時(shí)，在上課的時(shí)候總是會(huì)交頭接耳，影響其他同學(xué)上課。這讓班主任李老師非常頭疼。 為了

4、盡量減少這種現(xiàn)象，李老師想到一個(gè)辦法，將這些上課喜歡說話的同學(xué)用過道分開。即某兩個(gè)左右相鄰的同學(xué)經(jīng)常上課說話，則從這兩個(gè)同學(xué)之間增加一條縱向過道，讓他們的距離拉開，即可杜絕他們兩個(gè)上課說話了。同樣，若前后相鄰?fù)瑢W(xué)喜歡上課說話，也在他們之間增加一條橫向過道，將他們的距離拉開。 李老師決定按這種辦法重新安排教室中的過道，以盡量減少上課時(shí)私下說話的同學(xué)的數(shù)量。如果教室中共有M行N列桌椅，需設(shè)置K條橫向過道和L條縱向地道。請(qǐng)你編寫程序，從輸入文件中讀入上課時(shí)喜歡私下說話的D對(duì)同學(xué)的坐標(biāo)位置，然后根據(jù)這些已知條件，設(shè)計(jì)出在什么位置設(shè)置橫向和縱向過道可使上課時(shí)私下說話的同學(xué)的數(shù)量最少。,9.1.5 排座位

5、,9.1 NOIP普及組試題精解,輸入數(shù)據(jù)： 5 6 1 2 3 4 2 4 3 2 2 1 2 3 4 3 5 輸出數(shù)據(jù) 1 2 4,9.1.5 排座位,9.2 NOIP提高組試題精解,一個(gè)天平秤配有若干砝碼，這些砝碼的重量分別為1g、2g、3g、5g、10g、20g等6種，所有砝碼的總重量不超過1000g，各種砝碼的數(shù)量在輸入文件中給出，要求根據(jù)輸入文件中給出的各種重量的砝碼數(shù)量，計(jì)算出該天平能稱出的重量的種類數(shù)。,9.2.1 碼碼稱重,9.2 NOIP提高組試題精解,爸爸每月給阿明300元零花錢，由阿明自己管理使用。阿明每個(gè)月會(huì)自己做一個(gè)預(yù)算，計(jì)算本月需要用多少錢，并且總能嚴(yán)格地執(zhí)行預(yù)算

6、，即每月花的錢與預(yù)算相同。 為了讓阿明從小養(yǎng)成儲(chǔ)蓄的習(xí)慣，爸爸建議阿明可以將沒用完的錢（整百的錢）存在他那里，到年底將存的錢再加上20%的獎(jiǎng)勵(lì)還給阿明。 為此，阿明制定了一個(gè)儲(chǔ)蓄計(jì)劃：在每個(gè)月的月初，爸爸將零花錢給他后，根據(jù)這個(gè)月的預(yù)算，到月末手中還會(huì)有多于100元或恰好100元的錢，就將余下的錢中的整百部分交給爸爸存起來，剩余的錢留在自己手中。,9.2.2 阿明的零花錢,9.2 NOIP提高組試題精解,馬上要過春節(jié)了，媽媽到超市進(jìn)行大采購，一共購買n種年貨商品。年貨采購齊以后，媽媽決定將所有年貨商品都合并到一起，好搬回家里。 每一次合并時(shí)，可以把兩種商品合并到一起，消耗的體力等于兩種商品的重

7、量之和?？梢钥闯?，所有的商品經(jīng)過n-1次合并之后，就只剩下一大包了。在合并這些商品時(shí)總共消耗的體力等于每次合并時(shí)所耗體力之和。 因?yàn)檫€要花大力氣把這些年貨商品搬回家，所以在合并這些商品時(shí)，要盡可能地節(jié)省體力?，F(xiàn)在要求你給媽媽設(shè)計(jì)一種方案，讓媽媽在合并這些商品時(shí)耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。,9.2.3 購買年貨,9.2 NOIP提高組試題精解,合唱隊(duì)的隊(duì)員在演出時(shí)一般是按這種形式排列隊(duì)伍：最高的隊(duì)員排在中間，然后各隊(duì)員按身高降序向兩側(cè)排列。設(shè)有K位合唱隊(duì)員，從左到右依次編號(hào)為1、2、K，他們的身高分別為T1、T2、TK，則他們的身高滿足T1 Ti+1 TK-1 TK （1=i=K

8、）。 現(xiàn)在合唱隊(duì)有N個(gè)隊(duì)員隨機(jī)地站成一排（并未按高矮次序排列），要想構(gòu)成演出時(shí)的中間高兩邊矮的隊(duì)形，則需要請(qǐng)其中的(N-K)位隊(duì)員出列，使得剩下的K位隊(duì)員正好排成合唱隊(duì)形。 請(qǐng)你根據(jù)數(shù)據(jù)輸入文件中給出的各隊(duì)員的身高數(shù)據(jù)，計(jì)算最少需要幾位隊(duì)員出列，才能使使剩下的隊(duì)員正好組成合唱隊(duì)形。,9.2.4 調(diào)整隊(duì)形,9.2 NOIP提高組試題精解,9.2.4 調(diào)整隊(duì)形,9.2 NOIP提高組試題精解,將一副牌隨機(jī)分成了N堆，編號(hào)分別為1、2、N。每堆上有若干張，但紙牌總數(shù)一定是牌堆數(shù)N的倍數(shù)。為了使各堆牌的張數(shù)相同，可以在任一堆上取若干張紙牌，然后移動(dòng)其附近的兩堆牌中。具體的移牌規(guī)則為： （1）編號(hào)為1的牌堆上的牌，只能移到編號(hào)為2的牌堆上（因?yàn)榫幪?hào)為1的牌堆左側(cè)沒有牌堆）； （2）編號(hào)為N的牌堆上的牌，只能移到編號(hào)為N-1的