第9章 信息學(xué)奧賽試題精解

零基礎(chǔ)學(xué)算法第9章：信息學(xué)奧賽試題精解課程安排9.1

NOIP普及組試題精解9.2NOIP提高組試題精解9.1NOIP普及組試題精解9.1.1

求級數(shù)之和9.1NOIP普及組試題精解在輸入文件中有n個整數(shù)，每個數(shù)都在1~500萬之間，從這些數(shù)中選出k個整數(shù)進(jìn)行相加，可得到不同的組合。例如：有4個整數(shù)8、11、12、13，用其中的3個數(shù)進(jìn)行相加，可得到如下所示的4種組合：8+11+12=318+11+13=328+12+13=3411+12+13=36在以上的4個和值中，只有8+11+12=31的結(jié)果為素數(shù)。現(xiàn)在要求你編寫程序，計算給定n個整數(shù)，從中選中k個整數(shù)進(jìn)行組合相加，其和值為素數(shù)的情況有多少種？9.1.2求素數(shù)組合9.1NOIP普及組試題精解在中國象棋中，卒過了界河以后不僅可以向前移動，也可以橫向移動?，F(xiàn)在假設(shè)有一個過河的卒位地圖9-3所示的A點，要使該卒從A點移到B點（目標(biāo)位置）可有多少種不同的路線？9.1.3計算卒的路線9.1NOIP普及組試題精解對于正式出版的圖書，都必須有一個ISBN碼。ISBN碼一共有10位數(shù)字，前9位分別表示國家、出版者、書名號，最后一位是根據(jù)前9位數(shù)字計算得來的，作為校驗碼使用。一般ISBN的格式如下：7-118-01984-4以上ISBN碼中，7表示中國，118表示國防工業(yè)出版社，01984代表書名號，最后一位4表示校驗碼。校驗碼是其他9位數(shù)字的求余函數(shù)。計算方法是：用10～2這九個數(shù)分別順序乘以ISBN的前九位數(shù)字，所得乘積之和被模數(shù)11除，其余數(shù)與11的差，即是校驗位的數(shù)值。所以，校驗位的數(shù)值可能是1～11中的任何一個整數(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.1NOIP普及組試題精解六（一）班有幾個調(diào)皮的同學(xué)，當(dāng)這些同學(xué)坐在相鄰位置（前后或左右相鄰）時，在上課的時候總是會交頭接耳，影響其他同學(xué)上課。這讓班主任李老師非常頭疼。為了盡量減少這種現(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排座位9.1NOIP普及組試題精解輸入數(shù)據(jù)：56123424322123435輸出數(shù)據(jù)1249.1.5排座位9.2NOIP提高組試題精解

一個天平秤配有若干砝碼，這些砝碼的重量分別為1g、2g、3g、5g、10g、20g等