主题：第40次编程比赛第2题题目
neverPE [专家分：1620] 发布于 2006-09-01 02:28:00
取石子游戏的变种：有两堆石子，两个人轮流对这些石子进行操作。在每一次操作中，操作者需要拿走其中一堆石子，并且把另一堆石子分成两堆（可以不相等）留给对方操作。游戏如此进行下去，石子数会越来越少，最后必将出现这样一种情况：某人拿走一堆石子后发现另一堆里只剩1个石子不能再分了。游戏规定此时该操作者取胜。
这个游戏是不公平的。对于任意一种初始状态，总有一方有必胜策略。所谓有必胜策略是指，无论对方如何操作，自己总有办法取胜。现在给出两堆石子的数量，要求计算先操作的人是否存在必胜策略。
函数原型 bool Stone(char* a,char* b);
a，b是两堆数字的数目，用字符串保存。字符串长度不大于30，并且没有非法字符，没有前导0。
返回值：如果先操作的人存在必胜策略，返回true，否则返回false
内存限制：256M
时间限制：10S
样例：
a="1" b="1" true
a="100" b="1" true
a="2" b="1" true
a="2" b="3" false
a="5" b="2" true
提示：不要想太复杂了。
回复列表 （共17个回复）
11 楼
hwjian [专家分：0] 发布于 2006-09-02 10:36:00
#include<iostream>
#include<math.h>
using namespace std;
long long pow(int a)
{
long long b(1);
while(a--)
b*=10;
return b;
}
bool Stone(char* a,char* b)
{
int la=strlen(a);
int lb=strlen(b);
long long aa(0),bb(0);
for(int i=0;i<la;i++)
aa+=(long long)(a[i]-'0')*pow(la-i-1);
for(int i=0;i<lb;i++)
bb+=(long long)(b[i]-'0')*pow(lb-i-1);
bool flag_a(false),flag_b(false);
int remainder_a=aa%5, remainder_b=bb%5;
if(remainder_a==2||remainder_a==3)
flag_a=true;
if(remainder_b==2||remainder_b==3)
flag_b=true;
if(flag_a&&flag_b)
return false;
else
return true;
}
12 楼
magicalking [专家分：150] 发布于 2006-09-02 10:51:00
函数实现如下,没有测试程序
#include <iostream>
#include <stdlib.h>
using namespace std;
bool Stone(char* a,char* b){
long n1=atol(a),n2=atol(b);
for(int i=1,j=1;;){
if((i<=n1&&j>=n1)||(i<=n2&&j>=n2))return 1;
else if(i>n1&&i>n2)return 0;
else{
i=i*4;
j=(j+1)*4;
}
}
}
13 楼
liangbch [专家分：1270] 发布于 2006-09-02 11:23:00
int str2int(char *str)
{
int r=0;
while (*str!=0)
{
r=r*10 + (*str -'0');
str++;
}
return r;
}
bool judge(int a,int b)
{
int b1,b2;
if ( a==1)
return true;
if (a==2 || a==3)
{
if (b==2 || b==3)
return false;
b1=2; //拆分b为b1,b2
b2=b-b1;
while (b1<=b2)
{
if (!judge(b1,b2)) //对方失败
return true;
b1++; b2--;
}
return false;
}
else
{
int i;
for (i=0;i<2;i++)
{
b1=2; //拆分b为b1,b2
if (i==0) b2=b-b1;
else b2=a-b1;
while (b1<=b2)
{
if (!judge(b1,b2)) //对方失败
return true;
b1++; b2--;
}
}
return false;
}
}
bool Stone(char* a,char* b)
{
int n1,n2;
n1=str2int(a);
n2=str2int(b);
if (n1<=n2)
return judge(n1,n2);
else
return judge(n2,n1);
}
14 楼
nwpuzhl [专家分：0] 发布于 2006-09-02 14:15:00
题目最好是自己出，不要去ＣＯＰＹ以前的题目，网上都要现成的ＲＥＰＯＲＴ，而且我认为搞ＡＣＭ的来这好象不是很合适，
15 楼
forjane [专家分：5670] 发布于 2006-09-02 14:34:00
bool Stone(char* a,char* b)
{
char *p=a,*q=b;
for(;*p!=0;p++);
for(;*q!=0;q++);
p--;
q--;
return !(*p=='2' || *p=='3' || *p=='7' || *p=='8') || !(*q=='2' || *q=='3' || *q=='7' || *q=='8');
}
16 楼
feixia [专家分：0] 发布于 2006-09-02 20:48:00
[em9]简单!!
a="1" b="2" true
a="2" b="1" false
17 楼
xyhx [专家分：0] 发布于 2006-09-02 22:52:00
观察以下数字序列，（分为两行），若开始时两堆石子的数目为第一行的任意两个数字时，则先操作的人必输；若包含一个或一个以上的第二行的数字时，则一定能赢。
--------------------------------------------------------------
第一行： 2 3 7 8 12 13 17 18 22 23
第二行：1 4 5 6 9 10 11 14 15 16 19 20 21 24 25 26
--------------------------------------------------------------
第一行：27 28 32 33 37 38 42 43
第二行： 29 30 31 34 35 36 39 40 41 44 45 46
--------------------------------------------------------------
再仔细观察第一行数字的特征，发现该行的数字的末尾数字为'2','3','7','8',所以只要检查字符串a，b的末尾数字就行了。
//判断数字是否为2,3,7,8
int Judge(char *a)
{
switch(*a)
{
case '2':
case '3':
case '7':
case '8':return 1;
default: return 0;
}
}
bool Stone(char* a,char* b)
{
int tag=0;
for(;*a!='\0';a++)
;
tag+=Judge(--a);
for(;*b!='\0';b++)
;
tag+=Judge(--b);
if(tag==2)
return false;
else
return true;
}
我来回复
您所在位置：