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

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

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

4、盡量減少這種現(xiàn)象，李老師想到一個辦法，將這些上課喜歡說話的同學(xué)用過道分開。即某兩個左右相鄰的同學(xué)經(jīng)常上課說話，則從這兩個同學(xué)之間增加一條縱向過道，讓他們的距離拉開，即可杜絕他們兩個上課說話了。同樣，若前后相鄰?fù)瑢W(xué)喜歡上課說話，也在他們之間增加一條橫向過道，將他們的距離拉開。 李老師決定按這種辦法重新安排教室中的過道，以盡量減少上課時私下說話的同學(xué)的數(shù)量。如果教室中共有M行N列桌椅，需設(shè)置K條橫向過道和L條縱向地道。請你編寫程序，從輸入文件中讀入上課時喜歡私下說話的D對同學(xué)的坐標(biāo)位置，然后根據(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提高組試題精解,一個天平秤配有若干砝碼，這些砝碼的重量分別為1g、2g、3g、5g、10g、20g等6種，所有砝碼的總重量不超過1000g，各種砝碼的數(shù)量在輸入文件中給出，要求根據(jù)輸入文件中給出的各種重量的砝碼數(shù)量，計算出該天平能稱出的重量的種類數(shù)。,9.2.1 碼碼稱重,9.2 NOIP提高組試題精解,爸爸每月給阿明300元零花錢，由阿明自己管理使用。阿明每個月會自己做一個預(yù)算，計算本月需要用多少錢，并且總能嚴格地執(zhí)行預(yù)算

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

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

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