2023年c語(yǔ)言復(fù)賽題

信息學(xué)奧賽復(fù)賽練習(xí)題

1.模擬開(kāi)關(guān)(題目名稱：moni.bas)(12分)

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

依次把1和1的倍數(shù)電燈的開(kāi)關(guān)都拉一下。第三個(gè)人走過(guò)來(lái)依次把3和3的倍數(shù)的開(kāi)關(guān)都拉一下，第五個(gè)人走過(guò)來(lái)依次把5和5的倍數(shù)的

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

［輸入文獻(xiàn)］文獻(xiàn)名：moni.in

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

［輸出文獻(xiàn)］文獻(xiàn)名：moni.out

文獻(xiàn)中共有若干行，每一行一個(gè)數(shù)據(jù)，分別為那些關(guān)著的燈泡的編號(hào)。

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

［樣例輸入］: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.【問(wèn)題描述-明明的隨機(jī)數(shù)】

明明想在學(xué)校中請(qǐng)一些同學(xué)一起做問(wèn)卷調(diào)查，為了實(shí)驗(yàn)的客觀性，他先用計(jì)算機(jī)生成了

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

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

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

【輸入文獻(xiàn)】

輸入文獻(xiàn)random.in有2行，第1行為1個(gè)正整數(shù)，表達(dá)所生成的隨機(jī)數(shù)的個(gè)數(shù)：N

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

【輸出文獻(xiàn)】

輸出文獻(xiàn)random.out也是2行，第1行為1個(gè)正整數(shù)M,表達(dá)不相同的隨機(jī)數(shù)的個(gè)數(shù)。

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

【輸入樣例】

10

2040326740208930040015

【輸出樣例】

8

152032406789300400

〃本題重要是考察對(duì)排序算法的掌握，只但是外加了一個(gè)去重的操作。本題的算法有很多，我們?cè)诳荚嚂r(shí)，時(shí)間緊，題目難度大。假

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

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

以使用最簡(jiǎn)樸的冒泡算法來(lái)完畢。由于本題的輸出結(jié)果規(guī)定我們必須先記錄出不反復(fù)數(shù)據(jù)的個(gè)數(shù)，所以當(dāng)數(shù)據(jù)排序之后，我們可以先對(duì)所

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

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

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);//輸入隨機(jī)數(shù)的個(gè)數(shù)

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

fscanf(fp1,”％d”,&num[i]);〃將己知的隨機(jī)數(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");〃打開(kāi)寫(xiě)文獻(xiàn)的指針

for(i=0;i

(

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

continue;

M++;

)

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

for(i=0;i

(

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

continue;

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

)

fclose(fpl);

fclose(fp2);

return0;

4.【問(wèn)題描述-開(kāi)心的金明】

金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有?間他自己專用的很寬敞的房間。更讓他快樂(lè)的是，媽媽昨天對(duì)他說(shuō)：“你

的房間需要購(gòu)買(mǎi)哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò)N元錢(qián)就行，今天一早金明就開(kāi)始做預(yù)算，但是他想買(mǎi)的東西太多了，肯

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

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

設(shè)第j件物品的價(jià)格為v[j],重要度為w[j],共選中了k件物品，編號(hào)依次為，

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

請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足規(guī)定的購(gòu)物單。

【輸入文獻(xiàn)】

輸入文獻(xiàn)happy.in的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：

Nm（其中N（＜30000）表達(dá)總錢(qián)數(shù)，m（＜25）為希望購(gòu)買(mǎi)物品的個(gè)數(shù)。）

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

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

【輸出文獻(xiàn)】

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

【輸入樣例】

10005

8002

4005

3005

4003

2002

【輸出樣例】

3900

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

重要思想：

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

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

大價(jià)值組合，就是本題的算法

本題的關(guān)鍵是計(jì)算出相應(yīng)的二進(jìn)制數(shù)據(jù)列，每一種組合相應(yīng)一個(gè)二進(jìn)制數(shù)列，然后根據(jù)二進(jìn)制數(shù)組的0,1值來(lái)形成物品不同的組合,

從而計(jì)算出當(dāng)前二進(jìn)制組合下的價(jià)值和，通過(guò)2、-1比較后就能計(jì)算出最大價(jià)值

#include

intmain()

{

intN,m;//其中N(<30000)表達(dá)總錢(qián)數(shù)，m(<25)為希望購(gòu)買(mǎi)物品的個(gè)數(shù)

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

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

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)表達(dá)總錢(qián)數(shù)，m(<25)為希望購(gòu)買(mǎi)物品的個(gè)數(shù)

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

(

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

)

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

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

while(n>0)

(

k=2*k;

n-;

)

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

n=m;〃恢復(fù)n的值以便下面計(jì)算所用

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

(

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

num=i;

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

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

(

y=num%2;

num=num/2;

bi[n-1]=y;

n-；

)

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

(

bi[n]=O;

n-；

)

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

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

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

(

訐(bi[j]==0)〃當(dāng)bi[j]==0,表達(dá)當(dāng)前物品并沒(méi)有取操作，因此直接跳轉(zhuǎn)考察下一個(gè)物品的取舍狀態(tài)

continue;

TotalWeight+=wi[j];

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

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

if(TotalWeight>N)〃一方面考察計(jì)算出來(lái)的總價(jià)格是否超過(guò)了允許的總價(jià)格

(

TotalWeight=0;//計(jì)算下一趟組合之前清0

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

continue;〃當(dāng)計(jì)算出本次組合的總價(jià)格超過(guò)既定總價(jià)格時(shí)，continue到下一趟組合(即跳轉(zhuǎn)到外層for循環(huán))

)

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

MaxValueSum=ValueSum;

TotalWeight=0;〃計(jì)算下一趟組合之前清0

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

)

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

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

fclose(fpl);

fclose(fp2);

return0;

)

5.【問(wèn)題描述-猴子選大王】：M只猴子要選大王，選舉辦法如下：所有猴子按1-M編號(hào)圍坐一圈，從1號(hào)開(kāi)始按順序1,2,,,K

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

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

【輸入文獻(xiàn)】

輸入文獻(xiàn)monkey.in的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：

MK

【輸出文獻(xiàn)】

輸出文獻(xiàn)monkey.out只有一個(gè)正整數(shù)，輸出最后一個(gè)猴子的編號(hào)

【輸入樣例】

73

【輸出樣例】

4

這個(gè)問(wèn)題記得給大家上機(jī)練習(xí)中做過(guò)，即對(duì)報(bào)數(shù)問(wèn)題的求解。在我做完這個(gè)題口的時(shí)候，我其實(shí)并不知道這就是頂頂有名的約瑟夫問(wèn)

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

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

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

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

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

由。開(kāi)始的，所以要加1)即為選出的大王的編號(hào)。想法很簡(jiǎn)樸，現(xiàn)在關(guān)鍵的問(wèn)題是如何解決當(dāng)報(bào)數(shù)到第M個(gè)猴子的時(shí)候如何使得下一個(gè)

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

由簡(jiǎn)樸的一維數(shù)組變成了首尾相接的環(huán)型數(shù)組，也就是我們數(shù)據(jù)結(jié)構(gòu)中的環(huán)型隊(duì)列?假設(shè)p為當(dāng)前數(shù)組某一元素的下標(biāo)，對(duì)于一維數(shù)組來(lái)

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

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

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

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

程序參考：

#include

intmain()

(

intn;

intn1=0;〃表達(dá)報(bào)數(shù)記數(shù)器

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

intNumOfKing;//大王的編號(hào)

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

inta[1000];

FILE*fp1,*fp2;

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

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

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

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

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

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

(

while(n1

(

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

(

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

if(n1==K)

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

)

P++；//移動(dòng)到下一個(gè)位置

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

}

n1=0;〃當(dāng)報(bào)完K個(gè)數(shù)后將報(bào)數(shù)記數(shù)變量清0,以備下次重新報(bào)數(shù)

n--;〃當(dāng)報(bào)完一輪后總猴子數(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問(wèn)題描述:合并果子】

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

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

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

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

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

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

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

【輸入文獻(xiàn)】

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

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

【輸出文獻(xiàn)】

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

【輸入樣例】

3

219

【輸出樣例】

15

【解題思緒】

為了使最終的體力花費(fèi)值最小，我們應(yīng)當(dāng)每一次都選擇最小的兩堆果子合并，使每次合并花費(fèi)的體力值最小.我們可以按照以下算法過(guò)程

來(lái)解決問(wèn)題：

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

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

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

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

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

6.輸出total

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

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

這樣的問(wèn)題.

【基本算法練習(xí)部分】

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

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

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

個(gè)整形數(shù)組中.當(dāng)所有的字符數(shù)組轉(zhuǎn)存到整型數(shù)組后，我們就可以對(duì)其進(jìn)行運(yùn)算了.

試寫(xiě)一個(gè)程序，將字符串”7654321”,轉(zhuǎn)換成相應(yīng)的整數(shù)并輸出.

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