注册 登录
编程论坛 → C语言论坛

一个竞赛题目，求指教

花脸 发布于 2018-03-19 22:02， 2114 次点击
  某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：
    每位选手需要回答10个问题（其编号为1到10），越后面越有难度。答对的，当前分数翻倍；答错了则扣掉与题号相同的分数（选手必须回答问题，不回答按错误处理）。
    每位选手都有一个起步的分数为10分。
    某获胜选手最终得分刚好是100分，如果不让你看比赛过程，你能推断出他（她）哪个题目答对了，哪个题目答错了吗？
    如果把答对的记为1，答错的记为0，则10个题目的回答情况可以用仅含有1和0的串来表示。例如：0010110011 就是可能的情况。
    你的任务是算出所有可能情况。每个答案占一行。


#include <iostream>
#include <cstring>
using namespace std;
int a[15],v[15];

void DFS(int Max,int i)
{
    if(Max==100)
    {
        for(int i=1;i<10;i++)
            cout<<v[i];
        cout<<endl;
        return;
    }
    if(i==10)
        return ;
    for(int j=1;j<=10;j++)
    {
        v[j]=1;
        DFS(Max+a[j],++i);    //做对
        v[j]=0;
        DFS(Max-a[j],++i);//做错
    }
   
}
int main()
{
    memset(a,0,sizeof(a));
    memset(v,0,sizeof(v));
    a[1]=1;
    for(int i=2;i<=10;i++)
        a[i]=2*a[i-1];
    DFS(0,0);
    return 0;
}
19 回复
#2
花脸2018-03-19 22:02
求指教、
#3
九转星河2018-03-20 14:37
https://bbs.bccn.net/thread-481334-1-1.html

好像和这个题目差不多~
#4
word1232018-03-20 19:53
#include<iostream>
#include<vector>
using namespace std;

vector<int> stack;
void dfs(int score , int questionNumber){
    if(questionNumber>10){   //超过10道一定会停,若满足条件输出
        if(score==100){
            for(int i=0;i<10;i++){
            cout<<stack[i];
        }
        cout<<endl;
        }
        return;
    }
    stack.push_back(1);    //答对压入1
    dfs(score*2 , questionNumber+1);
    stack.pop_back();    //遍历完所有情况后弹出该数1

    stack.push_back(0);   //打错压入0
    dfs(score-questionNumber , questionNumber+1);
    stack.pop_back();    //遍历完所有情况后弹出该数0
}

int main()
{
    dfs(10,1);    //当前分   题号
    return 0;
}

感觉这样要好理解点，你觉得呢
#5
a4514102018-03-20 20:34
不懂
#6
花脸2018-03-20 22:37
回复 4楼 word123
恩 能理解，我感觉我们两个的思路差不多啊，代码也差不多，我的代码哪里出现问题了呢？
#7
花脸2018-03-20 23:07
回复 3楼 九转星河
学习了。。但是我还没想明白我的哪里出错了
#8
九转星河2018-03-20 23:11
回复 7楼 花脸
根据题意

DFS(Max-a[j],++i);//做错

这里应该是DFS(Max-j,++i);

相信4楼明白了答错扣掉与题号相同的分数这句话的是啥意思~
#9
花脸2018-03-21 12:36
回复 8楼 九转星河
只有本站会员才能查看附件，请 登录

昨天看过之后已经改过了还是不对。。

[此贴子已经被作者于2018-3-21 12:41编辑过]
#10
word1232018-03-21 15:06
#include <iostream>
#include <cstring>
using namespace std;
int a[15],v[15];

void DFS(int Max,int i)
{
    if(Max==100)      //万一题还没答完怎么办(就算后面全错了也应该把分数减去)
    {
        for(int i=1;i<10;i++)   //和上面i冲突了,该成其他变量
            cout<<v[i];
        cout<<endl;
        return;
    }
    if(i==10)
        return ;
    for(int j=1;j<=10;j++)    //这个循环什么鬼？每次调用递归循环10次，不会死循环吗？
    {
        v[j]=1;
        DFS(Max+a[j],++i);    //做对  Max是当前分，当前分两倍
        v[j]=0;
        DFS(Max-a[j],++i);//做错     减去题号   a[j]是什么鬼？
    }
   
}
int main()
{
    memset(a,0,sizeof(a));
    memset(v,0,sizeof(v));   //v可以不赋值，读数据是在你把10道题都遍历完了才读的
    a[1]=1;
    for(int i=2;i<=10;i++)
        a[i]=2*a[i-1]; //a没用，是动态在变的，是当前分的两倍，而不是之前连续正确后得分的2倍
    DFS(0,0);    //初始分是10分，初始题号是1
    return 0;
}
反正你这道题问题太多了，没掌握清楚
#11
word1232018-03-21 15:10
#include <iostream>
#include <cstring>
using namespace std;
int a[15],v[15];

void DFS(int Max,int i)
{
    if(i==11){
        if(Max==100)
        {
            for(int ii=1;ii<=10;ii++)
                cout<<v[ii];
            cout<<endl;
        }
        return;
    }
    v[i]=1;
    DFS(Max*2,i+1);    //做对
    v[i]=0;
    DFS(Max-i,i+1);//做错
}
int main()
{
    DFS(10,1);
    return 0;
}

吧你的代码按刚才我说的调整一下，就是这样
#12
九转星河2018-03-21 15:25
回复 9楼 花脸
其实我没啥细看代码,没留意多了个for循环以及初始赋值问题按11楼那样改就可以了~

[此贴子已经被作者于2018-3-21 15:28编辑过]
#13
花脸2018-03-21 17:52
回复 11楼 word123
嗯好的 谢谢
#14
花脸2018-03-21 17:52
回复 12楼 九转星河
好的
#15
wmf20142018-03-22 08:31
下面代码不知道是否符合题意：
程序代码：
#include <stdio.h>
void main()
{
    int i,j,k,s;
    char a[11]={0};
    for(i=0;i<1024;i++)
    {
        for(j=0,k=i,s=10;j<10;k/=2,j++)
        {
            a[j]=k%2+'0';
            s+=k%2?s:-j-1;
        }
        if(s==100)printf("%s\n",a);
    }
}

运行结果如下：
1011010000
0111010000
0010110011
Press any key to continue


[此贴子已经被作者于2018-3-22 08:38编辑过]
#16
花脸2018-03-22 12:11
回复 15楼 wmf2014
不是很理解
#17
wmf20142018-03-22 13:06
回复 16楼 花脸
2^10=1024，遍历0-1023的二进制组合，输出符合要求的对应二进制字符串。
#18
sunus2018-03-22 15:55
楼上思路是对的，程序不太好懂，我重写一下：
程序代码：

#include <stdio.h>
#define ACC 100    //最终得分

int main(int argc, char* argv[])
{
    int i, j, n;
    int iCoun;    //计分
   
    for (i = 0; i <= 1023; i++)    //10位2进制，0代表错，1代表对，0000000000到1111111111中包含了所有的可能，只要遍历就可以得出答案
    {
        iCoun = 10;    //初始分数10

        n = 1;    //掩码，用来检查对应题目的二进制位，初始0000000001代表第一题对
        for (j = 1; j <= 10; j++)
        {
            if ((i & n) == n)
                iCoun *= 2;    //答对，分数翻倍
            else
                iCoun -= j;    //答错，分数减题号
            n *= 2;    //左移一位，代表下一题
        }

        if (iCoun == ACC)    //计算出的分数=题目要求的最终得分，则2进制输出i就是答案
        {
            n = i;
            for (j = 1; j <= 10; j++)    //将i转成2进制输出
            {
                printf("%d", n % 2);
                n /= 2;
            }
            printf("\n");
        }
    }
    return 0;
}



[此贴子已经被作者于2018-3-22 16:03编辑过]
#19
花脸2018-03-22 22:04
回复 18楼 sunus
好的 谢谢
#20
花脸2018-03-22 22:05
回复 17楼 wmf2014
谢谢
1
©2024, BCCN.NET
电脑版