主题:第56次编程比赛题目
eastcowboy [专家分:25370] 发布于 2007-06-22 18:05:00
本次比赛的题目与“猜数字”游戏有关。
猜数字游戏由两个人参与。比赛规则如下:
1、玩家A随机选择一个数,该数由四个不同的数字组成(每个数字可以是0~9这十个数字之一,且该数的最高位可以是零)。玩家B并不知道玩家A选择的是哪个数字。
2、玩家B猜一个数,该数由四个数字组成(数字可以重复,且每一位都可以是零),并把这个数告诉玩家A。玩家A把这个数与自己选择的数比较。如果有数字和位置都相同的,称为一个A,如果有数字相同但位置不同的,称为一个B。如果有4个A,表示完全正确,游戏结束。否则,玩家B可以再猜。
3、玩家B最多可以猜7次,如果7次仍然没有猜正确,游戏结束。
(虽然规则可能还是叙述得不够清楚,但如果大家玩过文曲星上那个游戏的话,这种程度的叙述已经非常罗嗦了-_-)
现在,由我来扮演玩家A,各位可以编写代码扮演玩家B,来进行这个游戏。
参加编程比赛的各位[color=FF0000]只需要编写以下四个函数[/color]:
void begin();
void end();
int guess();
void result(int a, int b);
游戏开始时,我会调用begin函数;游戏结束时,我会调用end函数。游戏进行的过程中,我会在自己选好数字后,让你的程序猜一个数字,这时我调用guess函数,你可以把猜好的数字利用该函数返回。我会对你猜的数字进行判断,然后告诉你有几个A和几个B,这时我调用result函数,你可以从该函数的参数a知道有几个A,从该函数的参数b知道有几个B。(即使你猜对了,有4个A,我也会先调用result函数,再结束游戏)。
注意在一次游戏中,你可以有最多7次机会,因此我在调用begin函数和调用end函数之间,会多次调用guess函数和result函数。
提示:
1、你可以在begin函数中进行一些初始化动作,也可以写一个空的begin函数,里面没有任何语句。end函数也类似。
2、我将大致采用以下代码来进行游戏。
int n = 我猜的一个数
int i;
begin();
for(i=0; i<7; ++i)
{
int g = guess();
在这里判断有多少个A,多少个B
result(A, B);
if( A == 4 )
break;
}
end();
在这里判断得分
3、对于选择C++的选手,你可以把上面四个函数装到一个class中。或者从以下class继承一个自己的class。
class GamePlayerB
{
public:
GamePlayerB();
virtual ~GamePlayerB();
virtual void begin() = 0;
virtual void end() = 0;
virtual int guess() = 0;
virtual void result(int a, int b) = 0;
};
冠军的评选规则:
我将选多个数字让各位的程序去猜。对于每一个数字,一次就猜对的得8分,两次就猜对的得7分,依次类推,七次猜对的得一分,七次仍未猜对的不得分。分数高者将被评选为冠军。
如果遇到分数相同,且增加很多数字来进行游戏后分数仍然相同的情况,则我会根据其它因素(包括代码风格、容错处理等方面)来决定冠军。
冠军将作为下次编程比赛的出题人和主持人。
P.S.
这个东西可能已经有人做过了~这里拿来当题目,希望多点人参加吧。
不过要做到最好的话应该也不是太容易。大家尽量发挥吧。
有任何疑问可以在[url=http://www.programfan.com/club/post-238918.html]这里[/url]跟帖提出。
最后更新于:2007-06-22 18:07:00
回复列表 (共10个回复)
沙发
liu1103xwxw [专家分:160] 发布于 2007-06-23 02:39:00
有个疑问:
如果你选择的数是5555,
我猜的数是5656
则A的个数是2
B的个数是多少呢?
是2还是0?
板凳
jiaer0302 [专家分:70] 发布于 2007-06-23 10:34:00
应该是2A0B吧!
猜的
3 楼
magicyang87 [专家分:0] 发布于 2007-06-23 10:53:00
感觉这样冠军的随机性太大了吧,基本靠运气了
4 楼
ghxyydx [专家分:450] 发布于 2007-06-23 11:58:00
怎么没隐藏啊~~~
5 楼
lx-kun [专家分:0] 发布于 2007-06-24 11:36:00
游戏规则有问题的
2、玩家B猜一个数,该数由四个数字组成(数字可以重复,且每一位都可以是零),
文曲星里的猜数字,是不允许数字重复的,这样的话,就可以避免 1楼说说的问题
6 楼
eastcowboy [专家分:25370] 发布于 2007-06-24 16:08:00
对于liu1103xwxw在1楼的问题:
我选择的数是没有重复数字的,而你猜的数则可以有重复数字。
关于A和B个数的计算:我选的数的每一个数字会与你猜的数的每一个数字比较,然后单独判断是A还是B(或者都不是),最后计算总的A和总的B。例如我选1234,你猜1111,则结果为1A3B。
对于magicyang87在3楼的问题:
随机性并不大。好的方法可以有非常大的机会在7次以内猜到正确的数。
对于ghxyydx在4楼的问题:
这个实在是我的过失了。如果想参加比赛并且不希望自己的代码在比赛结束前被别人看到,可以把代码文件发送到我的邮箱:eastcowboy2002@163.com。比赛结束后,我可以把这些代码公布出来,并进行评判。
7 楼
eastcowboy [专家分:25370] 发布于 2007-06-24 18:03:00
另:将GamePlayerB的定义修改如下:
class GamePlayerB
{
public:
GamePlayerB() { }
virtual ~GamePlayerB() { }
virtual void begin() = 0;
virtual void end() = 0;
virtual int guess() = 0;
virtual void result(int a, int b) = 0;
};
8 楼
iAkiak [专家分:8460] 发布于 2007-06-24 20:26:00
不管那么多了...贴了再说:
[code=c]
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
class GamePlayerB
{
public:
GamePlayerB(){}
virtual ~GamePlayerB(){}
virtual void begin() = 0;
virtual void end() = 0;
virtual int guess() = 0;
virtual void result(int a, int b) = 0;
};
// 定义USE_RANDOM完全使用随机选择,不考虑各分支最大容量最小的问题
//#define USE_RANDOM
#ifndef USE_RANDOM
// 定义TRY_COUNT为只尝试不同数据数。否则尝试所有有效数据
//#define TRY_COUNT 1000
#endif
// 定义USE_COUNTTABLE用内存换时间,保存a,b的解,不过貌似效果不明显...
// #define USE_COUNTTABLE
#ifdef TRY_COUNT
#ifdef USE_RANDOM
#error TRY_COUNT is depend on NO USE_RANDOM
#endif
#endif
class GamePlayer_iAkiak : public GamePlayerB
{
public:
GamePlayer_iAkiak()
{
if (initCandidates.empty())
{
for (int i0 = 0; i0 < 10; i0++)
{
for (int i1 = i0 + 1; i1 < 10; i1++)
{
for (int i2 = i1 + 1; i2 < 10; i2++)
{
for (int i3 = i2 + 1; i3 < 10; i3++)
{
int g[4] = {i0, i1, i2, i3, };
do initCandidates.push_back(g[0] * 1000 + g[1] * 100 + g[2] * 10 + g[3]);
while(next_permutation(g, g + 4));
}
}
}
}
}
if (randindex.empty())
{
randindex.resize(10000);
for(int i = 0; i < 10000; i++)
randindex[i] = i;
#ifdef USE_COUNTTABLE
memset(countab, 0xff, sizeof(countab));
#endif
}
}
void begin()
{
history.clear();
candidates = initCandidates;
}
void end()
{
}
int guess()
{
//printf("DEBUG %d\n", candidates.size());
// search a candidate that will got
#ifndef USE_RANDOM
if (candidates.size() > 3 && candidates.size() < initCandidates.size())
{
int minMax = initCandidates.size();
int mmg = -1;
int numCount[10] = {0};
for (vector<int>::iterator r = candidates.begin(); r != candidates.end(); ++r)
{
int c = *r;
numCount[c % 10]++;
c /= 10;
numCount[c % 10]++;
c /= 10;
numCount[c % 10]++;
c /= 10;
numCount[c % 10]++;
}
int minZeroCountNumber = -1;
for (int i = 0; i < 10; i++)
{
if (numCount[i] == 0)
{
minZeroCountNumber = i;
break;
}
}
vector<int> validnumber;
random_shuffle(randindex.begin(), randindex.end());
#ifdef TRY_COUNT
int igCase = TRY_COUNT;
#endif
for (size_t ig = 0; ig < randindex.size(); ig++)
{
int g = randindex[ig];
bool skip = false;
for (int i = 0; i < 4; i++)
{
if (numCount[g%10] == 0 && g%10 != minZeroCountNumber)
{
skip = true;
break;
}
}
if (skip) // 不猜多于2种不存在数字的情况
continue;
int count[25] = {0};
int max = 0;
for (vector<int>::iterator r = candidates.begin(); r != candidates.end(); ++r)
{
pair<char,char> ab = countAB(*r, g);
int t = ++count[ab.first * 5 + ab.second];
if (t > max)
{
max = t;
if (max > minMax)
break;
}
}
if (max < minMax || mmg == -1)
{
mmg = g;
minMax = max;
}
#ifdef TRY_COUNT
if (--igCase == 0)
break;
#endif
}
lastGuess.g = mmg;
}
else
#endif //ifndef USE_RANDOM
lastGuess.g = candidates[rand() % candidates.size()];
return lastGuess.g;
}
void result(int a, int b)
{
assert(a >= 0 && a <= 4);
assert(b >= 0 && b <= 4);
assert(a + b >= 0 && a + b <= 4);
lastGuess.ab = pair<char, char>(a, b);
// remove failed candidates
for (vector<int>::iterator r = candidates.begin(); r != candidates.end();)
{
if (countAB(*r, lastGuess.g) != lastGuess.ab)
{
swap(*r, candidates.back());
candidates.pop_back();
}
else
++r;
}
history.push_back(lastGuess);
}
static pair<char, char> countAB(int a, int b)
{
assert(a < 10000 && b < 10000);
pair<char, char> ab(0, 0);
#ifdef USE_COUNTTABLE
if (countab[a][b] == (char)0xff)
{
#endif
int d[10] = {0}, i, c = a;
for (i = 0; i < 4; i++)
d[c % 10]++, c /= 10;
for (i = 0; i < 4; i++)
{
if (a % 10 == b % 10)
ab.first++;
else if (d[b % 10])
ab.second++;
a /= 10;
b /= 10;
}
#ifdef USE_COUNTTABLE
countab[a][b] = ab.first * 5 + ab.second;
}
else
{
ab.first = countab[a][b] / 5;
ab.second = countab[a][b] % 5;
}
a = ab.first;
b = ab.second;
assert(a >= 0 && a <= 4);
assert(b >= 0 && b <= 4);
assert(a + b >= 0 && a + b <= 4);
#endif
return ab;
}
static const vector<int> &GetInitCandidates()
{
return initCandidates;
}
protected:
struct Guess
{
short g;
pair<char, char> ab;
};
vector<Guess> history;
vector<int> candidates;
Guess lastGuess;
static vector<int> initCandidates;
static vector<int> randindex;
#ifdef USE_COUNTTABLE
static char countab[10000][10000];
#endif
};
vector<int> GamePlayer_iAkiak::initCandidates;
vector<int> GamePlayer_iAkiak::randindex;
#ifdef USE_COUNTTABLE
char GamePlayer_iAkiak::countab[10000][10000];
#endif
int main()
{
GamePlayerB *iakiak = new GamePlayer_iAkiak;
vector<int> testcase = GamePlayer_iAkiak::GetInitCandidates();
int score = 0;
for (vector<int>::iterator c = testcase.begin(); c != testcase.end(); ++c)
{
int n = *c;
int i;
iakiak->begin();
for (i = 0; i < 7; ++i)
{
int g = iakiak->guess();
pair<int, int> ab = GamePlayer_iAkiak::countAB(n, g);
int A = ab.first;
int B = ab.second;
iakiak->result(A, B);
//printf("%d: %04d %04d %dA%dB\n", i, n, g, A, B);
if (A == 4)
{
score += 8 - i;
break;
}
}
iakiak->end();
printf("%04d %.4f\n", *c, (float)score / (1 + c - testcase.begin()));
}
printf("%.4f\n", score / 5040.0f);
delete iakiak;
return 0;
}
[/code]
9 楼
yuanhongqian123 [专家分:90] 发布于 2007-06-24 23:10:00
要猜的数字在最开始已定义
#include <iostream.h>
int n=1234;
void begin()
{
cout<<"游戏中有个四位数字,你有7次机会猜中"<<endl;
}
int guess()
{
int m;
cout<<"请输入你要猜的数:";
cin>>m;
return m;
}
void result(int A,int B)
{
cout<<"A的个数为:"<<A<<endl;
cout<<"B的个数为: "<<B<<endl;
}
void end()
{
cout<<"制作者,袁鸿乾!"<<endl;
}
void main()
{
begin();
int A;
int B;
int a[4],b[4];
int i,j,k;
a[0]=n/1000;
a[1]=n/100%10;
a[2]=n/10%10;
a[3]=n%10;
for(i=0; i<7; ++i)
{
cout<<"你还有"<<7-i<<"机会 ";
A=0;
B=0;
int g = guess();
b[0]=g/1000;
b[1]=g/100%10;
b[2]=g/10%10;
b[3]=g%10;
for(j=0,k=0; j<4,k<4;j++,k++)
{
if(a[j]==b[k])
A++;
}
for(j=0;j<4;j++)
{
if(j==0)
{
for(k=1; k<4; k++)
{
if(a[j]==b[k])
B++;
}
}
if(j==1)
{
if(a[j]==b[0])
B++;
for(k=2;k<4;k++)
{
if(a[j]==b[k])
B++;
}
}
if(j==2)
{
for(k=0;k<2;k++)
{
if(a[j]==b[k])
B++;
}
if(a[j]==b[3])
B++;
}
if(j==3)
{
for(k=0;k<3;k++)
{
if(a[j]==b[k])
B++;
}
}
}
result(A, B);
if( A == 4 )
{
cout<<"恭喜你答对了!";
break;
}
if(i==7)
{
cout<<"别灰心,下次再来!"<<endl;
}
}
end();
}
10 楼
逆行行 [专家分:30] 发布于 2007-06-25 08:39:00
#include "stdio.h"
void begin(int *A,int *B);
void format(int *p,int n);
int pronum(int g);
int matchline(int *p,int n);
int matchtable(int a[7][6],int n,int i);
int guess(int A,int B,int i,int g);
void result(int *A,int *B,int g,int n);
void main()
{
int i;
int n,g=0;
int A,B;
begin(&A,&B);
scanf("%d",&n);
for(i=0;i<7;i++)
{
g=guess(A,B,i,g);
result(&A,&B,g,n);
if(A==4)
printf("You are right!%d",g);
}
}
void begin(int *A,int *B)
{
*A=0;
*B=0;
}
void format(int *p,int n)
{
p[0]=n/1000;
p[1]=(n-p[0]*1000)/100;
p[2]=(n-p[0]*1000-p[1]*100)/10;
p[3]=n-p[0]*1000-p[1]*100-p[2]*10;
}
int pronum(int g)
{
int n,a[4];
for(n=g+1;n<9876;n++){
format(a,n);
if(!(a[0]==a[1]||a[0]==a[2]||a[0]==a[3]||a[1]==a[2]||a[1]==a[3]||a[2]==a[3]))
return n;
}
}
int matchline(int *p,int n)
{
int i,j,A=0,B=0;
int a[4];
format(a,n);
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(p[i]==a[j])
{
if(i==j)
A++;
else
B++;
}
if(A==p[4]&&B==p[5])
return 1;
else
return 0;
}
int matchtable(int a[7][6],int n,int i)
{
int j;
for(j=0;j<i;j++)
if(!matchline(a[j],n))
return 0;
return 1;
}
int guess(int A,int B,int i,int g)
{
static int table[7][6];
int temp;
if(i==0){
format(table[i],123);
printf("%d\n:123",i);
return 123;
}
table[i-1][4]=A;
table[i-1][5]=B;
do{
g=pronum(g);
}while(!matchtable(table,g,i));
printf("%d\n:%d",i,g);
return g;
}
void result(int *A,int *B,int g,int n)
{
int i,j;
int a[4],b[4];
format(a,g);
format(b,n);
*A=0;*B=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(a[i]==b[j])
{
if(i==j)
*A++;
else
*B++;
}
}
编了一天 因为二维数组的指针传递不会 搞的不好 上面这个连编译都有问题
可是对于我这个初学着已经很不容易了 没有想拿奖 只是想让高手们帮我改改
谢谢了
我来回复