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

龔春亞 喻子劍

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

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

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

文章編號：1009-3044（2021）17-0215-02

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

藍(lán)橋杯大賽由工業(yè)和信息化部人才交流中心主辦，國信藍(lán)橋教育科技（北京）股份有限公司承辦，是高校教育教學(xué)改革和創(chuàng)新人才培養(yǎ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)容和特點，研究了一道填空題的兩種解法，以供同行參考。

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

本屆藍(lán)橋杯比賽，因為疫情原因，第十一屆省賽分兩個批次進(jìn)行，分別在2020年7月和2020年10月競賽。我校信息工程學(xué)院共派出16名選手參加藍(lán)橋杯江蘇賽區(qū)比賽，其中一名同學(xué)獲得江蘇賽區(qū)C語言B組一等獎，晉級全國總決賽。經(jīng)過4個小時的激戰(zhàn)，該同學(xué)獲得全國決賽三等獎。

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

2 賽題內(nèi)容

題目名稱，奇怪的比賽。

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

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

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

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

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

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

多個答案順序不重要。

3 審題

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

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

4 遞歸思路解題

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

設(shè)計遞歸的出口和形式。遞歸函數(shù)名取作competition，參數(shù)設(shè)兩個，一個是待打題號step，一個是分?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）; //錯

ans[step]=1;

competition （sum*2，step+1）; //對

}

}

int main（）{

competition （10，1）;

return 0;

}

5 非遞歸暴力窮舉法解題

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

有學(xué)生用十層循環(huán)的嵌套來窮舉所有的答題情況，而本論文的思路是先研究十位無符號二進(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è)計計算得分函數(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è)計主函數(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ā)揮所長取得成績，需要不斷地研究賽題，本文只是針對一道填空題的遞歸和非遞歸解法做示范，希望能給同行參考。未來將更多地關(guān)注難度更高的賽題，希望能得到同行的建議和指點。

參考文獻(xiàn)

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

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

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