蓝桥杯“奇怪的比赛”赛题递归与非递归解题算法的研究
龚春亚 喻子剑
摘要：通过仔细审题，针对蓝桥杯竞赛题目奇怪的比赛，给出了审题细目分解，给出递归算法与非递归算法。
关键词：蓝桥杯;算法;递归与非递归
中图分类号：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.
【通联编辑：王力】
