蓝桥杯递归与非递归解题算法的研究

蓝桥杯大赛由工业和信息化部人才交流中心主办，国信蓝桥教育科技（北京）股份有限公司承办，是高校教育教学改革和创新人才培养的重要竞赛项目。经过多年的发展，蓝桥杯大赛吸引了包括北京大学、清华大学、上海交通大学、复旦大学、南京大学、哈尔滨工业大学、北京航空航天大学、北京理工大学、四川大学、华中科技大学、华东师范大学、华南理工大学等知名院校在内的1400多所高校参与，参赛选手总数已经超过30万人，成为国内首屈一指的IT类专业赛事。研究了一道填空题的两种解法，以供同行参考

赛题内容

题目名称，奇怪的比赛。题目大意如下：某电视台答题类比赛。计分规则如下：参赛选手每人需要回答10个问题（其编号为1到10），题号越往后，难度越大。答对的，当前分数翻倍；答错了则扣掉与题号相同的分数（选手必须回答问题，不回答按错误处理）。每位选手都有一个起步的分数为10分。某获胜选手最终得分刚好是100分，如果不让你看比赛过程，你能推断出他（她）哪个题目答对了，哪个题目答错了吗？如果把答对的记为1，答错的记为0，则10个题目的回答情况可以用仅含有1和0的串来表示。例如：0010110011 就是可能的情况。

你的任务是算出所有可能情况。每个答案占一行。多个答案顺序不重要。

审题

审题很关键，总共就10题，每道题必须解答，如果答对分数乘以2，答错扣掉当前题号对应的分值。首先得研究答题情况0010110011时，为什么得分是100分。答题前的初始分数是10分，根据题目中的测试用例，用例的得分过程如表1所示。

从上表可以清晰地看到答题得分的具体情况，为后面写程序奠定基础。

递归思路解题

递归总共调用10层，到第十一层就停止。设计递归的出口和形式。递归函数名取作competition，参数设两个，一个是待打题号step，一个是分数sum递归函数声明为void competition (int sum,int step)。递归的答题调用情况如图1所示。

递归解法的完整代码如下：

#include <iostream>
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;
}

非递归暴力穷举法解题

用整形数组表示答题情况，在 main 函数中声明数组 chardati[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");
             }
		}
}