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

龔春亞 喻子劍

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

關鍵詞：藍橋杯;算法;遞歸與非遞歸

中圖分類號：TP311? ? ? ? 文獻標識碼：A

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

開放科學（資源服務）標識碼（OSID）：

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

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

1 大賽的基本內容和特點

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

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

2 賽題內容

題目名稱，奇怪的比賽。

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

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

每位選手都有一個起步的分數為10分。

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

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

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

多個答案順序不重要。

3 審題

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

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

4 遞歸思路解題

遞歸總共調用10層，到第十一層就停止。

設計遞歸的出口和形式。遞歸函數名取作competition，參數設兩個，一個是待打題號step，一個是分數sum遞歸函數聲明為void competition （int sum，int step）。遞歸的答題調用情況如圖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 非遞歸暴力窮舉法解題

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

有學生用十層循環的嵌套來窮舉所有的答題情況，而本論文的思路是先研究十位無符號二進制的表述范圍0～1023，將訪問到的十進制值轉化為二進制，十進制轉二進制（10位）的流程圖如圖2所示，數組的使用是關鍵。

然后是根據答題得分規則寫得分判斷函數。參考表1，設計計算得分函數如下所示。

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;

}

最后設計主函數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"）;

}

}

}

最后，運行程序，結果如圖3所示：

如此，題目已經解答正確。

6 結束語

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

參考文獻

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

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

【通聯編輯：王力】