标题 | 蓝桥杯“奇怪的比赛”赛题递归与非递归解题算法的研究 |
范文 | 龚春亚 喻子剑 摘要:通过仔细审题,针对蓝桥杯竞赛题目奇怪的比赛,给出了审题细目分解,给出递归算法与非递归算法。 关键词:蓝桥杯;算法;递归与非递归 中图分类号: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. 【通联编辑:王力】 |
随便看 |
|
科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。