蓝桥杯“奇怪的比赛”赛题递归与非递归解题算法的研究

龚春亚 喻子剑

摘要：通过仔细审题，针对蓝桥杯竞赛题目奇怪的比赛，给出了审题细目分解，给出递归算法与非递归算法。

关键词：蓝桥杯;算法;递归与非递归

中图分类号：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.

【通联编辑：王力】