藍(lán)橋杯“奇怪的比賽”賽題遞歸與非遞歸解題算法的研究

龔春亞 喻子劍

摘要：通過仔細(xì)審題，針對(duì)藍(lán)橋杯競賽題目奇怪的比賽，給出了審題細(xì)目分解，給出遞歸算法與非遞歸算法。

關(guān)鍵詞：藍(lán)橋杯;算法;遞歸與非遞歸

中圖分類號(hào)：TP311? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）17-0215-02

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

藍(lán)橋杯大賽由工業(yè)和信息化部人才交流中心主辦，國信藍(lán)橋教育科技（北京）股份有限公司承辦，是高校教育教學(xué)改革和創(chuàng)新人才培養(yǎng)的重要競賽項(xiàng)目。經(jīng)過多年的發(fā)展，藍(lán)橋杯大賽吸引了包括北京大學(xué)、清華大學(xué)、上海交通大學(xué)、復(fù)旦大學(xué)、南京大學(xué)、哈爾濱工業(yè)大學(xué)、北京航空航天大學(xué)、北京理工大學(xué)、四川大學(xué)、華中科技大學(xué)、華東師范大學(xué)、華南理工大學(xué)等知名院校在內(nèi)的1400多所高校參與，參賽選手總數(shù)已經(jīng)超過30萬人，成為國內(nèi)首屈一指的IT類專業(yè)賽事。

本論文介紹了藍(lán)橋杯比賽的內(nèi)容和特點(diǎn)，研究了一道填空題的兩種解法，以供同行參考。

1 大賽的基本內(nèi)容和特點(diǎn)

本屆藍(lán)橋杯比賽，因?yàn)橐咔樵颍谑粚檬≠惙謨蓚€(gè)批次進(jìn)行，分別在2020年7月和2020年10月競賽。我校信息工程學(xué)院共派出16名選手參加藍(lán)橋杯江蘇賽區(qū)比賽，其中一名同學(xué)獲得江蘇賽區(qū)C語言B組一等獎(jiǎng)，晉級(jí)全國總決賽。經(jīng)過4個(gè)小時(shí)的激戰(zhàn)，該同學(xué)獲得全國決賽三等獎(jiǎng)。

藍(lán)橋杯軟件大賽不僅需要學(xué)生掌握基本知識(shí)點(diǎn)，而且要求學(xué)生具有一定的信息獲取、理解、處理、問題分析和創(chuàng)新的能力，才能把相關(guān)知識(shí)轉(zhuǎn)化為解決問題的具體方法，這正是培養(yǎng)創(chuàng)新人才所需要的。

2 賽題內(nèi)容

題目名稱，奇怪的比賽。

題目大意如下：某電視臺(tái)答題類比賽。計(jì)分規(guī)則如下：

參賽選手每人需要回答10個(gè)問題（其編號(hào)為1到10），題號(hào)越往后，難度越大。答對(duì)的，當(dāng)前分?jǐn)?shù)翻倍;答錯(cuò)了則扣掉與題號(hào)相同的分?jǐn)?shù)（選手必須回答問題，不回答按錯(cuò)誤處理）。

每位選手都有一個(gè)起步的分?jǐn)?shù)為10分。

某獲勝選手最終得分剛好是100分，如果不讓你看比賽過程，你能推斷出他（她）哪個(gè)題目答對(duì)了，哪個(gè)題目答錯(cuò)了嗎？

如果把答對(duì)的記為1，答錯(cuò)的記為0，則10個(gè)題目的回答情況可以用僅含有1和0的串來表示。例如：0010110011 就是可能的情況。

你的任務(wù)是算出所有可能情況。每個(gè)答案占一行。

多個(gè)答案順序不重要。

3 審題

審題很關(guān)鍵，總共就10題，每道題必須解答，如果答對(duì)分?jǐn)?shù)乘以2，答錯(cuò)扣掉當(dāng)前題號(hào)對(duì)應(yīng)的分值。首先得研究答題情況0010110011時(shí)，為什么得分是100分。答題前的初始分?jǐn)?shù)是10分，根據(jù)題目中的測(cè)試用例，用例的得分過程如表1所示。

從上表可以清晰地看到答題得分的具體情況，為后面寫程序奠定基礎(chǔ)。

4 遞歸思路解題

遞歸總共調(diào)用10層，到第十一層就停止。

設(shè)計(jì)遞歸的出口和形式。遞歸函數(shù)名取作competition，參數(shù)設(shè)兩個(gè)，一個(gè)是待打題號(hào)step，一個(gè)是分?jǐn)?shù)sum遞歸函數(shù)聲明為void competition （int sum，int step）。遞歸的答題調(diào)用情況如圖1所示。

遞歸解法的完整代碼如下：

#include

using namespace std;

int ans[12];

void competition（int sum，int step）{

if（step==11）{

if（sum==100）{

for（int i=1 ;i<11 ;i++）{

printf（"%d"，ans[i]）;

}

puts（""）;

}

}

else{

ans[step]=0;

competition （sum-step，step+1）; //錯(cuò)

ans[step]=1;

competition （sum*2，step+1）; //對(duì)

}

}

int main（）{

competition （10，1）;

return 0;

}

5 非遞歸暴力窮舉法解題

用整形數(shù)組表示答題情況，在main函數(shù)中聲明數(shù)組char dati[12]，其中dati[0]不使用，dati[11]也不使用，用dati[1]～dati[10]依次存儲(chǔ)答題標(biāo)記，0表示答錯(cuò)，1表示答對(duì)。

有學(xué)生用十層循環(huán)的嵌套來窮舉所有的答題情況，而本論文的思路是先研究十位無符號(hào)二進(jìn)制的表述范圍0～1023，將訪問到的十進(jìn)制值轉(zhuǎn)化為二進(jìn)制，十進(jìn)制轉(zhuǎn)二進(jìn)制（10位）的流程圖如圖2所示，數(shù)組的使用是關(guān)鍵。

然后是根據(jù)答題得分規(guī)則寫得分判斷函數(shù)。參考表1，設(shè)計(jì)計(jì)算得分函數(shù)如下所示。

int getResult（char *bn）

{

int score=10;

int i;

for（i=1;i<=10;i++）

{

if（bn[i]=='0'）score=score-i;

else if（bn[i]=='1'）score=score*2;

}

return score;

}

最后設(shè)計(jì)主函數(shù)main，代碼如下：

int main（）

{

char dati[12];

int score;

int num;

score=10;

for（num=0;num<=1023;num++）

{

change（dati，num）;

score=getResult（dati）;

if（score==100）

{

print（dati）;

printf（"＼n"）;

}

}

}

最后，運(yùn)行程序，結(jié)果如圖3所示：

如此，題目已經(jīng)解答正確。

6 結(jié)束語

藍(lán)橋杯程序競賽近年來得到越來越多的關(guān)注，每年有接近?上萬的選手參賽，如何輔導(dǎo)選手更好地發(fā)揮所長取得成績，需要不斷地研究賽題，本文只是針對(duì)一道填空題的遞歸和非遞歸解法做示范，希望能給同行參考。未來將更多地關(guān)注難度更高的賽題，希望能得到同行的建議和指點(diǎn)。

參考文獻(xiàn)

[1] 朱曉青，等. 基于藍(lán)橋杯的“以賽促學(xué)”教學(xué)方法實(shí)踐[J].計(jì)算機(jī)工程與科學(xué)，2016（1）：46-49.

[2] 任正云.藍(lán)橋杯“巧排撲克牌”試題的算法研究[J].荊楚理工學(xué)院學(xué)報(bào)，2013，28（2）：17-21.

【通聯(lián)編輯：王力】