2023年c語言復賽題

信息學奧賽復賽練習題

1.模擬開關(題目名稱：moni.bas)(12分)

［題目描述］:有N盞電燈排成一行，依次編號為1,2,3,…,N?，F(xiàn)各有一個開關，開始燈都亮著的?，F(xiàn)在尚有N個人，第一人走過來

依次把1和1的倍數(shù)電燈的開關都拉一下。第三個人走過來依次把3和3的倍數(shù)的開關都拉一下，第五個人走過來依次把5和5的倍數(shù)的

開關都拉一下(按奇數(shù)的規(guī)律)，…問最后都有哪些燈是關著的？

［輸入文獻］文獻名：moni.in

文獻中只有一行，包含1個整數(shù)N(其中5<N<30)

［輸出文獻］文獻名：moni.out

文獻中共有若干行，每一行一個數(shù)據(jù)，分別為那些關著的燈泡的編號。

規(guī)定：每一行的輸出數(shù)據(jù)都從第一列開始。

［樣例輸入］:moni.in的內(nèi)容為:

10

［樣例輸出］：moni.out的內(nèi)容為：

1

2

4

8

9

main()

{

inti,n,s,x;

inta［1000］;

scanf("%cT,&n);

for(i=1;i<n;i++)

a［i］=1；

x=1；

while(x<=n)

s=0;

while(s<=n)

{s=s+x;

a[s]=1-a[s];

)

x=x+2;

)

s=0;

for(i=1;i<n;i++)

if(a[i]==O)

{printf("%d",i);s=s+1;

}

if(s==O)printf("O");

)

3.【問題描述-明明的隨機數(shù)】

明明想在學校中請一些同學一起做問卷調查，為了實驗的客觀性，他先用計算機生成了

N個1JIJ1000之間的隨機整數(shù)，(NR00),對于其中反復的數(shù)字，只保存一個，把其余相

同的數(shù)去掉，不同的數(shù)相應著不同的學生的學號。然后再把這些數(shù)從小到大排序，按照排好

的順序去找同學做調查。請你協(xié)助明明完畢“去重”與“排序”的工作。

【輸入文獻】

輸入文獻random.in有2行，第1行為1個正整數(shù)，表達所生成的隨機數(shù)的個數(shù)：N

第二行有N個用空格隔開的正整數(shù)，為所產(chǎn)生的隨機數(shù)。

【輸出文獻】

輸出文獻random.out也是2行，第1行為1個正整數(shù)M,表達不相同的隨機數(shù)的個數(shù)。

第2行為M個用空格隔開的正整數(shù)，為從小到大排好序的不相同的隨機數(shù)。

【輸入樣例】

10

2040326740208930040015

【輸出樣例】

8

152032406789300400

〃本題重要是考察對排序算法的掌握，只但是外加了一個去重的操作。本題的算法有很多，我們在考試時，時間緊，題目難度大。假

如我們能用最簡樸的思維方式解決問題的話，就不一定把很多的時間放在代碼執(zhí)行效率的優(yōu)化問題上。有時候犧牲一點空間(內(nèi)存)和時

間對于獲取更多的考試時間是非常有必要的。本題最簡樸的思想方法，就是根據(jù)題目規(guī)定，先對給定的一組數(shù)據(jù)進行排序，排序的方法可

以使用最簡樸的冒泡算法來完畢。由于本題的輸出結果規(guī)定我們必須先記錄出不反復數(shù)據(jù)的個數(shù)，所以當數(shù)據(jù)排序之后，我們可以先對所

有的數(shù)據(jù)遍歷一次，這一次遍歷的目的就是讓我們記錄出不反復數(shù)據(jù)的個數(shù)，并將其輸出。最后，我們還需進行一次遍歷，這次遍歷用于

打印出排序之后不反復的所有數(shù)據(jù)結果.

7

include

intmain()

(

FILE*fp1,*fp2;

intN,M=0;

inti,j;

inta;

intnum[100];〃根據(jù)題口所給的數(shù)據(jù)規(guī)模定義數(shù)組的大小

if((fp1=fopen(,'random.in,,,,,r,,))==NULL)

(

printf("cannotopenfile\nM);

return0;

)

fscanf(fp1,”％d”,&N);//輸入隨機數(shù)的個數(shù)

for(i=0;i<N;i++)

fscanf(fp1,”％d”,&num[i]);〃將己知的隨機數(shù)存放到初始數(shù)組中

for(i=0;i

for(j=i+1;j<N;j++)

if(num[i]>num[j])

a=num[i];

num[i]=num[j];

num[j]=a;

)

)

fp2=fopen("random.out","w");〃打開寫文獻的指針

for(i=0;i

(

if(i>0&&num[i]==num/1])〃思考一下這個去重的操作中為什么有i>0這個條件

continue;

M++;

)

fprintf(fp2J%d\rT,M);〃在結果文獻中打印出不反復數(shù)據(jù)的個數(shù)并鍵入一個回車符

for(i=0;i

(

計(i>0&&num[i]==num/1])〃思考一下這個去重的操作中為什么有i>0這個條件

continue;

fprintf(fp2；'%d",num[i]);

)

fclose(fpl);

fclose(fp2);

return0;

4.【問題描述-開心的金明】

金明今天很開心，家里購置的新房就要領鑰匙了，新房里有?間他自己專用的很寬敞的房間。更讓他快樂的是，媽媽昨天對他說：“你

的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行，今天一早金明就開始做預算，但是他想買的東西太多了，肯

定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)1~5表達，第5等最重要。他還從因特網(wǎng)上查

到了每件物品的價格（都是整數(shù)元）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設第j件物品的價格為v[j],重要度為w[j],共選中了k件物品，編號依次為，

j1,j2.......jk,則所求的總和為:v[j1]*w[j1]+vD2]*w[j2]+……+v[jk]*w[jk]（其中*為乘號）

請你幫助金明設計一個滿足規(guī)定的購物單。

【輸入文獻】

輸入文獻happy.in的第1行，為兩個正整數(shù)，用一個空格隔開：

Nm（其中N（＜30000）表達總錢數(shù)，m（＜25）為希望購買物品的個數(shù)。）

從第2行到第m+1行，第j行給出了編號為卜1的物品的基本數(shù)據(jù)，每行有2個非負整數(shù)

vp（其中v表達該物品的價格（v＜10000）,p表達該物品的重要度（1-5））

【輸出文獻】

輸出文獻happy.out只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（＜）

【輸入樣例】

10005

8002

4005

3005

4003

2002

【輸出樣例】

3900

背包問題的解決辦法有很多，但是都不太容易理解，本算法采用窮舉法結合二進制數(shù)據(jù)的排列來窮舉所有價值組合

重要思想：

根據(jù)物品的個數(shù)先計算出所有物品排列組合的排列數(shù)，每件物品取為1,不取為0

假設用n個物品，從n個物品中任意取出若干個的最大組合次數(shù)為：2叮-1種，因此只要窮舉出2"n-1種組合情況，計算出其中的最

大價值組合，就是本題的算法

本題的關鍵是計算出相應的二進制數(shù)據(jù)列，每一種組合相應一個二進制數(shù)列，然后根據(jù)二進制數(shù)組的0,1值來形成物品不同的組合,

從而計算出當前二進制組合下的價值和，通過2、-1比較后就能計算出最大價值

#include

intmain()

{

intN,m;//其中N(<30000)表達總錢數(shù)，m(<25)為希望購買物品的個數(shù)

intbi[24];//用于每次取物組合的0,1序列

intwi[24];〃用于存放每件物品的價格

intvi[24];//用于存放每件物品的重要度

inti,j,n,num;

intMaxValueSum=0,ValueSum=0,TotalWeight=0;

longk=1;

FILE*fp1,*fp2;

fscanf(fp1,"%d%d",&N,&m);//讀取數(shù)據(jù)：其中N(<30000)表達總錢數(shù)，m(<25)為希望購買物品的個數(shù)

for(i=0;i<m;i++)

(

fscanf(fp1,"%d%d”,&wi[i],&vi[i]);〃讀取數(shù)據(jù)：將各個物品的價格和重要度分別存放到相應的數(shù)組當中

)

n=m;〃將物品的總個數(shù)存放到一個中間變量中以方便計算

/*一方面計算出n種物品取舍組合的總數(shù)*/

while(n>0)

(

k=2*k;

n-;

)

k=k-1;〃求得k的值，即為n種物品取舍的(0,1)組合總數(shù)25-1

n=m;〃恢復n的值以便下面計算所用

for(i=1；iv=k;i++)//該循環(huán)的功能是循環(huán)遍歷k種組合，比較并計算出”價值和“最大的組合

(

〃第1步，必須求出每次取舍組合的二進制序列

num=i;

/*****以下這段代碼段完畢將num轉換成n位二進制數(shù)組的過程*****/

while(num!=O)〃其中第一個while循環(huán)完畢了有效數(shù)值的轉換

(

y=num%2;

num=num/2;

bi[n-1]=y;

n-；

)

while(n>=0)〃第二個while循環(huán)用于將二進制序列的高位置0

(

bi[n]=O;

n-；

)

/*****以上這段代碼段完畢將num轉換成n位二進制數(shù)組的過程*****/n=m;〃恢復n的值以便下面計算所用

〃第2步：計算出當前取舍組合(0,1)中的價值和，并于最大價值和進行比較，找到新的最大的價值和

for(j=0;j<n;j++)

(

訐(bi[j]==0)〃當bi[j]==0,表達當前物品并沒有取操作，因此直接跳轉考察下一個物品的取舍狀態(tài)

continue;

TotalWeight+=wi[j];

ValueSum+=wi[j]*vi[j];

)〃循環(huán)結束后，可求得本次組合的總價格Totalweight和總價值和ValueSum

if(TotalWeight>N)〃一方面考察計算出來的總價格是否超過了允許的總價格

(

TotalWeight=0;//計算下一趟組合之前清0

ValueSum=O;〃計算下一趟組合之前清0

continue;〃當計算出本次組合的總價格超過既定總價格時，continue到下一趟組合(即跳轉到外層for循環(huán))

)

if(ValueSum>MaxValueSum)〃在上一步保證總價格沒有超過既定價格的條件下，判斷本次組合的價值和是否超過最大的價值和

MaxValueSum=ValueSum;

TotalWeight=0;〃計算下一趟組合之前清0

ValueSum=O;〃計算下一趟組合之前清0

)

fp2=fopen("bag.out","w");

fprintf(fp2,"％d",MaxValueSum);〃輸出最大的價值和的結果

fclose(fpl);

fclose(fp2);

return0;

)

5.【問題描述-猴子選大王】：M只猴子要選大王，選舉辦法如下：所有猴子按1-M編號圍坐一圈，從1號開始按順序1,2,,,K

報數(shù)，凡報到K的猴子退出到圈外，如此循環(huán)報數(shù)，直到圈內(nèi)只剩下一只猴子時，這只猴子就是大王。M和K由輸入文獻提供，規(guī)定在

輸出文獻中打印出最后剩下的猴子的編號。數(shù)據(jù)規(guī)模(Mv=1000,Kv=10)

【輸入文獻】

輸入文獻monkey.in的第1行，為兩個正整數(shù)，用一個空格隔開：

MK

【輸出文獻】

輸出文獻monkey.out只有一個正整數(shù)，輸出最后一個猴子的編號

【輸入樣例】

73

【輸出樣例】

4

這個問題記得給大家上機練習中做過，即對報數(shù)問題的求解。在我做完這個題口的時候，我其實并不知道這就是頂頂有名的約瑟夫問

題。之后有個學生(陳亮宇)告訴我才知道這是一個據(jù)說是由古羅馬著名史學家Josephus提出的問題演變而來的。稱之為約瑟夫問題。

很多資料上對這一問題解釋得過于繁雜，實現(xiàn)起來不好理解。在這里介紹一下本人的一些想法以供大家參考。

這個題目其實就是一種編程的經(jīng)驗問題。我們可以假設猴子就位的狀態(tài)用1表達，把猴子離開的狀態(tài)用0表達。那么我們就可以用

一個a[M]的數(shù)組來存放M個猴子是否就位的狀態(tài)。我們可以一邊報數(shù)一邊遍歷該數(shù)組，每碰到第K個1時，就把當前位置的1變?yōu)?,

表達當前位置的猴子已經(jīng)出局了。一直循環(huán)遍歷到我們的狀態(tài)數(shù)組只有?個1的時候，這個存放1的數(shù)組下標再加上1(由于數(shù)組下標是

由。開始的，所以要加1)即為選出的大王的編號。想法很簡樸，現(xiàn)在關鍵的問題是如何解決當報數(shù)到第M個猴子的時候如何使得下一個

報數(shù)重新回到第1個猴子處，也就是如何使用一維數(shù)組來解決環(huán)型問題的求解技巧。大家想一下當我們的猴子圍成圈坐的時候，問題其實

由簡樸的一維數(shù)組變成了首尾相接的環(huán)型數(shù)組，也就是我們數(shù)據(jù)結構中的環(huán)型隊列?假設p為當前數(shù)組某一元素的下標，對于一維數(shù)組來

說，我們只要p++就可以移動到下一個元素的位置上。那么當p=M時，假如我們直接使用p++的話，p的值就超過了數(shù)組的最大長

度，我們想要的是P++之后等于0。那么如何實現(xiàn)呢？解決環(huán)型數(shù)組循環(huán)遍歷元素的方法：對于環(huán)型數(shù)組移動下標時，我們假如每次在p++

之后再加上p=p%M的話就能解決先前碰到的越界的問題。下標變量p也就可以周而復始的在a[M]中順時針地循環(huán)移動了.請認真查閱以

下程序源代碼分析，關鍵掌握環(huán)型數(shù)組的遍歷！

程序參考：

#include

intmain()

(

intn;

intn1=0;〃表達報數(shù)記數(shù)器

intp=0;〃指向當前數(shù)組元素的下標

intNumOfKing;//大王的編號

intM,K;//M為已知猴子總數(shù),K為報數(shù)的量級

inta[1000];

FILE*fp1,*fp2;

fp1=fopen("monkey.in","r");

fscanf(fp1,"%d%d”,&M,&K);//從文獻中讀取已知數(shù)據(jù)

n=M;〃M為圈的長度，即初始猴子數(shù)

for(inti=O;i<n;i++)

a[i]=1;〃初試話狀態(tài)數(shù)組，所有猴子都是就位的

while(n>1)〃n當前圈內(nèi)還剩下的猴子數(shù)，控制循環(huán)在圈內(nèi)只剩下一只猴子時結束循環(huán)

(

while(n1

(

if(a[p]==1)//假如當前位置有猴子

(

n1++;〃報數(shù)記數(shù)器加1

if(n1==K)

a[p]=O;〃將第K次報數(shù)的猴子置0,表達退出圈子

)

P++；//移動到下一個位置

p=p%M;〃這一步是為了解決循環(huán)數(shù)組成環(huán)遍歷的目的

}

n1=0;〃當報完K個數(shù)后將報數(shù)記數(shù)變量清0,以備下次重新報數(shù)

n--;〃當報完一輪后總猴子數(shù)減1

)

for(inti=0;i

(

if(a[il==1)

(

NumOfKing=i+1;

break;

)

)

fp2=fopen("monkey.out","w");

fpnntf(fp2,H%d",NumOfKing);

fclose(fpl);

fclose(fp2);

return0;

6.1問題描述:合并果子】

在一個果園里，多多已經(jīng)將所有的果子打了下來，并且按果子的不同種類提成了不同的堆.多多決定把所有的果子合成一堆.

每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和.可以看出，所有的果子通過n-1次合并之后,就只剩

下一堆了.多多在合并果子時總共消耗的體力等于每次合并所消耗體力之和.

由于還要花大力氣把這些果子般回家，所以多多在合并果子時要盡也許地節(jié)省體力.假定每個果子重量都是1,并且己知果子的種類數(shù)

和每種果子的數(shù)目,你的任務是設計出合并的順序方案，使多多花費的體力最少，并輸出這個最小的體力花費值.

例如:有3種果子，數(shù)目依次為1,2,9.可以先將1,2堆合并，新堆數(shù)目為3,花費體力為3.接著，將新堆與原先的第三堆合并，又得到新的堆，

數(shù)口為12,花費體力為12.所以多多總共花費體力為3+12=15.可以證明15為最小的體力花費值.

【輸入文獻】

輸入文獻fruit.in涉及兩行，第一行是一個整數(shù)n(1Vnv30000),表達果子的種類數(shù).第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)

ai(Eais20230)是第i種果子的數(shù)目.

【輸出文獻】

輸出文獻fruit.out涉及一行，這一行只包含一個整數(shù),也就是最小的體力花費值.

【輸入樣例】

3

219

【輸出樣例】

15

【解題思緒】

為了使最終的體力花費值最小，我們應當每一次都選擇最小的兩堆果子合并，使每次合并花費的體力值最小.我們可以按照以下算法過程

來解決問題：

1.讀入每堆果子的數(shù)目a[i](a[i]為第i堆果子的數(shù)目).

2.將果子數(shù)目按遞增順序進行排序.

3.合并數(shù)目最少的兩堆果子,并增長體力花費值到total變量

4.在果子序列中清除合并的兩堆果子數(shù)目,增長合并后的果子數(shù)目.

5.反復環(huán)節(jié)2-4,直到所有果子合并為一堆.

6.輸出total

問題的關鍵在于第4步,如何在數(shù)組中清除合并的兩堆果子，并增長合并后的果子數(shù)到數(shù)組中，然后再完畢剩余果子的重排序.解決這個

問題的方法有很多，可以在同一數(shù)組中解決，也可以運用此外一個空數(shù)組來重新存放每次合并之后的堆.建議大家考慮在同一數(shù)組中如何解決

這樣的問題.

【基本算法練習部分】

1.在實際應用中我們經(jīng)常碰到這樣的問題,在解決?些高精度的計算時，由于數(shù)據(jù)類型字長的限制，使得對一些海量數(shù)據(jù)不能直接用某

種數(shù)據(jù)類型來定義，比如7654321,已經(jīng)超過了我們基本數(shù)據(jù)類型的范圍，那么我們?nèi)绾谓鉀Q這些高精度的海量數(shù)據(jù)呢?在解決這樣的數(shù)據(jù)時,

我們一般的方法是一方面定義一個字符數(shù)組來存放將這些高精度的字符數(shù)據(jù)，然后將其每一位字符數(shù)據(jù)轉化為相應的整型，并重新保存在一

個整形數(shù)組中.當所有的字符數(shù)組轉存到整型數(shù)組后，我們就可以對其進行運算了.

試寫一個程序，將字符串”7654321”,轉換成相應的整數(shù)并輸出.

提醒:字符數(shù)字'0'-'9'相應的ASCII分別為48-57