1、信息學奧賽復賽練習題1 模擬開關（題目名稱: moni.bas）（12分）題目描述:有N盞電燈排成一行，依次編號為1，2，3，,N。現各有一個開關，開始燈都亮著的。現在還有N個人，第一人走過來依次把1和1的倍數電燈的開關都拉一下。第三個人走過來依次把3和3的倍數的開關都拉一下，第五個人走過來依次把5和5的倍數的開關都拉一下（按奇數的規律），問最后都有哪些燈是關著的？輸入文件 文件名：moni.in文件中只有一行，包含1個整數N(其中5N30)輸出文件 文件名：moni.out文件中共有若干行，每一行一個數據，分別為那些關著的燈泡的編號。要求：每一行的輸出數據都從第一列開始。樣例輸入：moni.

2、in的內容為：10樣例輸出：moni.out的內容為：12489main() int i,n,s,x; int a1000; scanf("%d",&n); for(i=1;i<n;i+) ai=1; x=1; while(x<=n) s=0; while(s<=n) s=s+x; as=1-as; x=x+2; s=0; for(i=1;i<n;i+) if(ai=0) printf("%d ",i);s=s+1; if(s=0) printf("0");3【問題描述-明明的隨機數】明明想在學校中請一

3、些同學一起做問卷調查，為了實驗的客觀性，他先用計算機生成了N 個1 到1000 之間的隨機整數，（N100），對于其中重復的數字，只保留一個，把其余相同的數去掉，不同的數對應著不同的學生的學號。然后再把這些數從小到大排序，按照排好的順序去找同學做調查。請你協助明明完成“去重”與“排序”的工作。【輸入文件】輸入文件random.in 有2 行，第1 行為1 個正整數，表示所生成的隨機數的個數：N 第二行有N 個用空格隔開的正整數，為所產生的隨機數。【輸出文件】輸出文件random.out 也是2 行，第1 行為1 個正整數M，表示不相同的隨機數的個數。第2 行為M 個用空格隔開的正整數，為從小到

4、大排好序的不相同的隨機數。【輸入樣例】10 20 40 32 67 40 20 89 300 400 15 【輸出樣例】815 20 32 40 67 89 300 400 /*本題主要是考察對排序算法的掌握，只不過外加了一個去重的操作。本題的算法有很多，我們在考試時，時間緊，題目難度大。如果我們能用最簡單的思維方式解決問題的話，就不一定把很多的時間放在代碼執行效率的優化問題上。有時候犧牲一點空間（內存）和時間對于獲取更多的考試時間是非常有必要的。本題最簡單的思想方法，就是根據題目要求，先對給定的一組數據進行排序，排序的方法可以使用最簡單的冒泡算法來完成。由于本題的輸出結果要求我們必須先統計出

5、不重復數據的個數，所以當數據排序之后，我們可以先對所有的數據遍歷一次，這一次遍歷的目的就是讓我們統計出不重復數據的個數，并將其輸出。最后，我們還需進行一次遍歷，這次遍歷用于打印出排序之后不重復的所有數據結果.*/#include int main() FILE *fp1,*fp2; int N,M=0; int i,j; int a; int num100; /根據題目所給的數據規模定義數組的大小 if(fp1=fopen("random.in","r")=NULL) printf("cannot open filen"); retu

6、rn 0; fscanf(fp1,"%d",&N); /輸入隨機數的個數 for(i=0;i<N;i+) fscanf(fp1,"%d",&numi); /將已知的隨機數存放到初始數組中 for(i=0;i for(j=i+1;j<N;j+) if(numi>numj) a=numi; numi=numj; numj=a; fp2=fopen("random.out","w"); /打開寫文件的指針 for(i=0;i if(i>0&&numi=numi-1)

7、 /思考一下這個去重的操作中為什么有i>0這個條件 continue; M+; fprintf(fp2,"%dn",M); /在結果文件中打印出不重復數據的個數 并鍵入一個回車符 for(i=0;i if(i>0&&numi=numi-1) /思考一下這個去重的操作中為什么有i>0這個條件 continue; fprintf(fp2,"%d ",numi); fclose(fp1); fclose(fp2); return 0; 4【問題描述-開心的金明】金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間他自己專用

8、的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N 元錢就行”。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N 元。于是，他把每件物品規定了一個重要度，分為5 等：用整數15 表示，第5 等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過N 元（可以等于N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第j 件物品的價格為vj，重要度為wj，共選中了k 件物品，編號依次為，j1,j2,jk ，則所求的總和為：vj1*wj1+vj2*wj2+vjk*wjk （其中*為乘號） 請

9、你幫助金明設計一個滿足要求的購物單。【輸入文件】輸入文件happy.in 的第1 行，為兩個正整數，用一個空格隔開： N m （其中N（<30000）表示總錢數，m(<25)為希望購買物品的個數。） 從第2 行到第m+1 行，第j 行給出了編號為j-1的物品的基本數據，每行有2 個非負整數v p （其中v 表示該物品的價格（v10000），p 表示該物品的重要度（1-5） 【輸出文件】輸出文件happy.out 只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（<100000000）【輸入樣例】1000 5 800 2 400 5 300 5 400 3

10、200 2 【輸出樣例】3900 背包問題的解決辦法有很多，但是都不太容易理解，本算法采用窮舉法結合二進制數據的排列來窮舉所有價值組合主要思想：根據物品的個數先計算出所有物品排列組合的排列數，每件物品取為1，不取為0假設用n個物品，從n個物品中任意取出若干個的最大組合次數為：2n-1種，因此只要窮舉出2n-1種組合情況，計算出其中的最大價值組合，就是本題的算法本題的關鍵是計算出對應的二進制數據列，每一種組合對應一個二進制數列，然后根據二進制數組的0，1值來形成物品不同的組合，從而計算出當前二進制組合下的價值和，通過2n-1比較后就能計算出最大價值#include int main() int

11、N,m; /其中N（<30000）表示總錢數，m(<25)為希望購買物品的個數 int bi24; /用于每次取物組合的0，1序列 int wi24; /用于存放每件物品的價格 int vi24; /用于存放每件物品的重要度 int i,j,n,num; int MaxValueSum=0,ValueSum=0,TotalWeight=0; long k=1; FILE *fp1,*fp2; fscanf(fp1,"%d%d",&N,&m); /讀取數據：其中N（<30000）表示總錢數，m(<25)為希望購買物品的個數 for(i=

12、0;i<m;i+) fscanf(fp1,"%d%d",&wii,&vii); /讀取數據：將各個物品的價格和重要度分別存放到對應的數組當中 n=m;/將物品的總個數存放到一個中間變量中以方便計算 /*首先計算出n種物品取舍組合的總數*/ while(n>0) k=2*k; n-; k=k-1; /求得k的值，即為n種物品取舍的（0，1）組合總數 2n-1 n=m; /恢復n的值以便下面計算所用 for(i=1;i<=k;i+) /該循環的功能是循環遍歷k種組合，比較并計算出”價值和“最大的組合 /第1步，必須求出每次取舍組合的二進制序列

13、num=i; /*以下這段代碼段完成將num轉換成n位二進制數組的過程*/ while(num!=0) /其中第一個while循環完成了有效數值的轉換 y=num%2; num=num/2; bin-1=y; n-; while(n>=0) /第二個while 循環用于將二進制序列的高位置0 bin=0; n-; /*以上這段代碼段完成將num轉換成n位二進制數組的過程*/ n=m; /恢復n的值以便下面計算所用 /第2步：計算出當前取舍組合（0，1）中的價值和，并于最大價值和進行比較，找到新的最大的價值和 for(j=0;j<n;j+) if(bij=0) /當bij=0,表示當

14、前物品并沒有取操作，因此直接跳轉考察下一個物品的取舍狀態 continue; TotalWeight+=wij; ValueSum+=wij*vij; /循環結束后，可求得本次組合的總價格Totalweight和總價值和ValueSum if(TotalWeight>N) /首先考察計算出來的總價格是否超過了允許的總價格 TotalWeight=0; /計算下一趟組合之前清0 ValueSum=0; /計算下一趟組合之前清0 continue; /當計算出本次組合的總價格超出既定總價格時，continue到下一趟組合（即跳轉到外層for循環 ) if(ValueSum>MaxVal

15、ueSum) /在上一步保證總價格沒有超過既定價格的條件下，判斷本次組合的價值和是否超過最大的價值和 MaxValueSum=ValueSum; TotalWeight=0; /計算下一趟組合之前清0 ValueSum=0; /計算下一趟組合之前清0 fp2=fopen("bag.out","w"); fprintf(fp2,"%d",MaxValueSum); /輸出最大的價值和的結果 fclose(fp1); fclose(fp2); return 0;5【問題描述-猴子選大王】：M只猴子要選大王，選舉辦法如下：所有猴子按1-M編

16、號圍坐一圈，從1號開始按順序1，2，K報數，凡報到K的猴子退出到圈外，如此循環報數，直到圈內只剩下一只猴子時，這只猴子就是大王。M和K由輸入文件提供，要求在輸出文件中打印出最后剩下的猴子的編號。數據規模（M<=1000,K<=10）【輸入文件】 輸入文件monkey.in 的第1 行，為兩個正整數，用一個空格隔開:M K【輸出文件】輸出文件monkey.out 只有一個正整數,輸出最后一個猴子的編號【輸入樣例】7 3【輸出樣例】4這個問題記得給大家上機練習中做過，即對報數問題的求解。在我做完這個題目的時候，我其實并不知道這就是頂頂有名的約瑟夫問題。之后有個學生（陳亮宇）告訴我才知道

17、這是一個據說是由古羅馬著名史學家Josephus提出的問題演變而來的。稱之為約瑟夫問題。很多資料上對這一問題解釋得過于繁雜，實現起來不好理解。在這里介紹一下本人的一些想法以供大家參考。 這個題目其實就是一種編程的經驗問題。我們可以假設猴子就位的狀態用1表示，把猴子離開的狀態用0表示。那么我們就可以用一個aM的數組來存放M個猴子是否就位的狀態。我們可以一邊報數一邊遍歷該數組，每遇到第K個1時，就把當前位置的1變為0，表示當前位置的猴子已經出局了。一直循環遍歷到我們的狀態數組只有一個1的時候，這個存放1的數組下標再加上1（因為數組下標是由0開始的，所以要加1）即為選出的大王的編號。想法很簡單，現在

18、關鍵的問題是如何解決當報數到第M個猴子的時候如何使得下一個報數重新回到第1個猴子處，也就是如何使用一維數組來解決環型問題的求解技巧。大家想一下當我們的猴子圍成圈坐的時候，問題其實由簡單的一維數組變成了首尾相接的環型數組，也就是我們數據結構中的環型隊列。假設p為當前數組某一元素的下標，對于一維數組來說，我們只要p+就可以移動到下一個元素的位置上。那么當p=M時，如果我們直接使用p+的話，p的值就超出了aM數組的最大長度，我們想要的是p+之后等于0。那么如何實現呢？解決環型數組循環遍歷元素的方法：對于環型數組移動下標時，我們如果每次在p+之后再加上p=p%M的話就能解決先前遇到的越界的問題。下標變

19、量p也就可以周而復始的在aM中順時針地循環移動了.請認真查閱以下程序源代碼分析，關鍵掌握環型數組的遍歷！程序參考:#include int main() int n; int n1=0; /表示報數記數器 int p=0; /指向當前數組元素的下標 int NumOfKing; /大王的編號 int M,K; /M為已知猴子總數,K為報數的量級 int a1000; FILE *fp1,*fp2;fp1=fopen("monkey.in","r"); fscanf(fp1,"%d%d",&M,&K); /從文件中讀取已

20、知數據 n=M; /M為圈的長度，即初始猴子數 for(int i=0;i<n;i+) ai=1; /初試話狀態數組，所有猴子都是就位的 while(n>1) /n當前圈內還剩下的猴子數,控制循環在圈內只剩下一只猴子時結束循環 while(n1 if(ap=1 ) /如果當前位置有猴子 n1+; /報數記數器加1 if(n1=K) ap=0; /將第K次報數的猴子置0，表示退出圈子 p+; /移動到下一個位置 p=p%M; /這一步是為了解決循環數組成環遍歷的目的 n1=0; /當報完K個數后將報數記數變量清0，以備下次重新報數 n-; /當報完一輪后總猴子數減1 for(int

21、i=0;i if(ai=1) NumOfKing=i+1; break; fp2=fopen("monkey.out","w"); fprintf(fp2,"%d",NumOfKing); fclose(fp1); fclose(fp2); return 0;6【問題描述:合并果子】 在一個果園里,多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆.多多決定把所有的果子合成一堆. 每一次合并,多多可以把兩堆果子合并到一起,消耗的體力等于兩堆果子的重量之和.可以看出,所有的果子經過n-1次合并之后,就只剩下一堆了.多多在合

22、并果子時總共消耗的體力等于每次合并所消耗體力之和. 因為還要花大力氣把這些果子般回家,所以多多在合并果子時要盡可能地節省體力.假定每個果子重量都是1,并且已知果子的種類數和每種果子的數目,你的任務是設計出合并的次序方案,使多多耗費的體力最少,并輸出這個最小的體力耗費值.例如:有3種果子,數目依次為1,2,9.可以先將1,2堆合并,新堆數目為3,耗費體力為3.接著,將新堆與原先的第三堆合并,又得到新的堆,數目為12,耗費體力為12.所以多多總共耗費體力為3+12=15.可以證明15為最小的體力耗費值.【輸入文件】輸入文件fruit.in包括兩行,第一行是一個整數n(1n30000),表示果子的種

23、類數.第二行包含n個整數,用空格分隔,第i個整數ai(1ai20000)是第i種果子的數目.【輸出文件】輸出文件fruit.out包括一行,這一行只包含一個整數,也就是最小的體力耗費值.【輸入樣例】32 1 9【輸出樣例】15【解題思路】為了使最終的體力耗費值最小,我們應該每一次都選擇最小的兩堆果子合并,使每次合并耗費的體力值最小.我們可以按照以下算法過程來解決問題:1. 讀入每堆果子的數目ai(ai為第i堆果子的數目).2. 將果子數目按遞增順序進行排序.3. 合并數目最少的兩堆果子,并增加體力耗費值到total變量4. 在果子序列中清除合并的兩堆果子數目,增加合并后的果子數目.5. 重復步

24、驟2-4,直到所有果子合并為一堆.6. 輸出total問題的關鍵在于第4步,如何在數組中清除合并的兩堆果子,并增加合并后的果子數到數組中,然后再完成剩余果子的重排序. 解決這個問題的方法有很多,可以在同一數組中解決,也可以利用另外一個空數組來重新存放每次合并之后的堆.建議大家考慮在同一數組中如何解決這樣的問題.【基本算法練習部分】1. 在實際應用中我們經常遇到這樣的問題,在處理一些高精度的計算時,由于數據類型字長的限制,使得對一些海量數據不能直接用某種數據類型來定義,比如:1234567890987654321,已經超出了我們基本數據類型的范圍,那么我們如何處理這些高精度的海量數據呢?在處理這樣的數據時,我們一般的方法是首先定義一個字符數組來存放將這些高精度的字符數據,然后將其每一位字符數據轉化為對應的整型,并重新保存在一個整形數組中.當所有的字符數組轉存到整型數組后,我們就可以對其進行運算了.試寫一個程序,將字符串”1234567890987654321”,轉換成對應的整數并輸出.提示:字符數字0-9對應的ASCII分別為48-57例如: 字符數字6,轉換成整型數字6的方法如下: Int k=6-48; /k的值即為6#define lim 6555int a1000,b1000; void sort(int x,int y) int i