问题描述:
游戏的规则是这样的:将一副扑克牌平均分成两份,每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上,然后小哈也拿出手中的第一张扑克牌,并放在小哼刚打出的扑克牌的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即可将两张相同的牌及其中间所夹的牌全部取走,并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时,游戏结束,对手获胜。
假如游戏开始时,小哼手中有6 张牌,顺序为2 4 1 2 5 6,小哈手中也有6 张牌,顺序为3 1 3 5 6 4,最终谁会获胜呢?现在你可以拿出纸牌来试一试。接下来请你写一个程序来自动判断谁将获胜。这里我们做一个约定,小哼和小哈手中牌的牌面只有1~9。
分析:
小哼或小哈 对应的两个操作------出牌和赢牌,其中出牌对应于出队,赢牌对应于入队
桌子相当于 栈,每打出一张牌就相当于入栈,当有人赢牌时,一次将牌从桌子上拿走,相当于出栈
赢牌规则:如果某人打出的牌与桌子上的某张牌相同,即可将两张牌及中间的牌全部取走
获胜规则:当任意一人手中的牌全部出完时,游戏结束,对手获胜
首先创建一个结构体用来实现队列:
typedef structqueue{
ElementType data[MaxSize];inthead;inttail;
}Queue;
接着创建栈:
typedef structstack{
ElementType data[N];inttop;
}Stack;
注:这里的N,定义的是10 ,因为桌子上最多有9章不同的牌(一旦有重复的牌就会出栈抽走),又因桌子上的数子为1~9(数组下标为0的不用),故有定义N为10 足够
接下来定义两个队列变量q1和q2, q1用来模拟小哼手中的牌,q2用来模拟小哈手中的牌,定义一个栈变量s模拟桌子上的牌
Queue q1,q2;
Stack s;
再接着初始化队列和栈
//初始化队列q1和q2为空,此时两人手里都没有牌
q1.head = 1;
q1.tail= 1;
q2.head= 1;
q2.tail= 1;//初始化栈s为空,最开始桌上没有牌
s.top= 0;
接下来读入小哼和小哈最初手上的牌,分两次读入,每次读入六个数,分别插入q1和q2中
//先读入六张牌,分别放在小哼和小哈手上
for(i=1;i<=6;++i)
{
scanf("%d",&q1.data[q1.tail++]); //读入一个数到队列
}for(i=1;i<=6;++i)
{
scanf("%d",&q2.data[q2.tail++]); //读入一个数到队列
}
再判断,小哼和小哈打出来的牌是否可以赢牌(即打出的牌跟桌子上的牌有没有重复的),这里需要注意的事用book[N]来标记桌子上的牌数
例如先判断小哼(或者小哈)的出牌,若小哼的这张牌在桌子上有,那么就将这张牌出队,并放在队尾,最后将桌子上的与此纸牌数相同的 出栈,放到小哼的队尾,否则,小哼的出队,放入桌子上(即入栈),并标记此纸牌。具体的代码如下所示:
while(q1.head
{
t= q1.data[q1.head]; //小哼先出牌
if(book[t]==0) //表明桌上没有牌面为t的牌
{//小哼此轮没有赢牌
q1.head++; //小哼已经打出一张牌,所以要把打出的牌出队
s.top++; //进栈
s.data[s.top]=t; //再把打出的牌放到桌上,即入栈
book[t]=1; //标记桌上现在已经有牌面为t的牌
}else{//小哼此轮可以赢牌
q1.head++;//小哼已经打出一张牌,所以要把打出的牌出队
q1.data[q1.tail]=t;//紧接着把打出的牌放到手中牌的末尾
q1.tail++;while(s.data[s.top]!=t) //把桌上可以赢得的牌依次放到手中牌的末尾
{
book[s.data[s.top]]=0;//取消标记
q1.data[q1.tail]=s.data[s.top];//依次放入队尾
q1.tail++;
s.top--; //栈中少了一张牌,所以栈顶要减1
}
}
t=q2.data[q2.head]; //小哈出一张牌//判断小哈当前打出的牌是否能赢牌
if(book[t]==0) //表明桌上没有牌面为t的牌
{//小哈此轮没有赢牌
q2.head++; //小哈已经打出一张牌,所以要把打出的牌出队
s.top++;
s.data[s.top]=t; //再把打出的牌放到桌上,即入栈
book[t]=1; //标记桌上现在已经有牌面为t的牌
}else{//小哈此轮可以赢牌
q2.head++;//小哈已经打出一张牌,所以要把打出的牌出队
q2.data[q2.tail]=t;//紧接着把打出的牌放到手中牌的末尾
q2.tail++;while(s.data[s.top]!=t) //把桌上可以赢得的牌依次放到手中牌的末尾
{
book[s.data[s.top]]=0;//取消标记
q2.data[q2.tail]=s.data[s.top];//依次放入队尾
q2.tail++;
s.top--;
}
}
}
最后一步,输出谁最终赢得了游戏,以及游戏结束后获胜者手中的牌和桌上的牌。如果小哼获胜了那么小哈的手中一定没有牌了(队列q2 为空),即q2.head==q2.tail,具体输出如下。
if(q2.head==q2.tail) //当任意一人手中的牌全部出完时,游戏结束,对手获胜
{
printf("小哼获胜\n");
printf("小哼当前手中的牌是");for(i=q1.head;i<=q1.tail-1;i++)
printf("%d",q1.data[i]);if(s.top>0) //如果桌上有牌则依次输出桌上的牌
{
printf("\n桌上的牌是");for(i=1;i<=s.top;i++)
printf("%d",s.data[i]);
printf("\n");
}elseprintf("\n桌上已经没有牌了");
}else{
printf("小哈获胜\n");
printf("小哈当前手中的牌是");for(i=q2.head;i<=q2.tail-1;i++)
printf("%d",q2.data[i]);if(s.top>0) //如果桌上有牌则依次输出桌上的牌
{
printf("\n桌上的牌是");for(i=1;i<=s.top;i++)
printf("%d",s.data[i]);
printf("\n");
}elseprintf("\n桌上已经没有牌了\n");
}
OK,每个过程分析完了,一下看看详细代码:
1 #include
2 #define MaxSize 1001
3 #define N 10
4 #define ElementType int
5
6
7 /*
8 * brief:小猫钓鱼问题, 转化为栈和队列的操作来求解9 * input:分别输入两组数字,每组数字6个 大小限制在1~9之间10 * output:获胜一方,和桌子上剩余的纸牌11 * example:12 * input: 2 4 1 2 5 613 * 3 1 3 5 6 414 * output: 小哼win15 * 小哼当前手中的牌是 5 6 2 3 1 4 6 516 * 桌上的牌是 2 1 3 417 */
18
19 //定义一个队列用来模拟小哼小哈的操作
20 typedef structqueue{21 ElementType data[MaxSize];22 inthead;23 inttail;24 }Queue;25
26 //定义栈用来模拟桌子的操作
27 typedef structstack{28 ElementType data[N];29 inttop;30 }Stack;31
32
33 intmain()34 {35 Queue q1,q2; //q1,q2分别模拟小哼和小哈手中的牌
36 Stack s; //模拟桌子上的牌
37 inti,t;38 int book[N]; //用来标记桌子上出牌的数字(1~9)39
40 //初始化队列q1和q2为空,此时两人手里都没有牌
41 q1.head = 1; q1.tail = 1;42 q2.head = 1; q2.tail = 1;43 //初始化栈s为空,最开始桌上没有牌
44 s.top= 0;45 //初始化用来标记的数组,用来标记哪些牌在桌子上了
46 for(i=1;i<=9;i++)47 book[i] = 0;48
49 //先读入六张牌,分别放在小哼和小哈手上
50 for(i=1;i<=6;++i)51 {52 scanf("%d",&q1.data[q1.tail++]); //读入一个数到队列
53 }54 for(i=1;i<=6;++i)55 {56 scanf("%d",&q2.data[q2.tail++]); //读入一个数到队列
57 }58
59 while(q1.head
62 if(book[t]==0) //表明桌上没有牌面为t的牌
63 {64 //小哼此轮没有赢牌
65 q1.head++; //小哼已经打出一张牌,所以要把打出的牌出队
66 s.top++; //进栈
67 s.data[s.top]=t; //再把打出的牌放到桌上,即入栈
68 book[t]=1; //标记桌上现在已经有牌面为t的牌
69 }70 else
71 {72 //小哼此轮可以赢牌
73 q1.head++;//小哼已经打出一张牌,所以要把打出的牌出队
74 q1.data[q1.tail]=t;//紧接着把打出的牌放到手中牌的末尾
75 q1.tail++;76 while(s.data[s.top]!=t) //把桌上可以赢得的牌依次放到手中牌的末尾
77 {78 book[s.data[s.top]]=0;//取消标记
79 q1.data[q1.tail]=s.data[s.top];//依次放入队尾
80 q1.tail++;81 s.top--; //栈中少了一张牌,所以栈顶要减1
82 }83 }84 t=q2.data[q2.head]; //小哈出一张牌85 //判断小哈当前打出的牌是否能赢牌
86 if(book[t]==0) //表明桌上没有牌面为t的牌
87 {88 //小哈此轮没有赢牌
89 q2.head++; //小哈已经打出一张牌,所以要把打出的牌出队
90 s.top++;91 s.data[s.top]=t; //再把打出的牌放到桌上,即入栈
92 book[t]=1; //标记桌上现在已经有牌面为t的牌
93 }94 else
95 {96 //小哈此轮可以赢牌
97 q2.head++;//小哈已经打出一张牌,所以要把打出的牌出队
98 q2.data[q2.tail]=t;//紧接着把打出的牌放到手中牌的末尾
99 q2.tail++;100 while(s.data[s.top]!=t) //把桌上可以赢得的牌依次放到手中牌的末尾
101 {102 book[s.data[s.top]]=0;//取消标记
103 q2.data[q2.tail]=s.data[s.top];//依次放入队尾
104 q2.tail++;105 s.top--;106 }107 }108 }109
110 if(q2.head==q2.tail) //当任意一人手中的牌全部出完时,游戏结束,对手获胜
111 {112 printf("小哼获胜\n");113 printf("小哼当前手中的牌是");114 for(i=q1.head;i<=q1.tail-1;i++)115 printf("%d",q1.data[i]);116 if(s.top>0) //如果桌上有牌则依次输出桌上的牌
117 {118 printf("\n桌上的牌是");119 for(i=1;i<=s.top;i++)120 printf("%d",s.data[i]);121 printf("\n");122 }123 else
124 printf("\n桌上已经没有牌了");125 }126 else
127 {128 printf("小哈获胜\n");129 printf("小哈当前手中的牌是");130 for(i=q2.head;i<=q2.tail-1;i++)131 printf("%d",q2.data[i]);132 if(s.top>0) //如果桌上有牌则依次输出桌上的牌
133 {134 printf("\n桌上的牌是");135 for(i=1;i<=s.top;i++)136 printf("%d",s.data[i]);137 printf("\n");138 }139 else
140 printf("\n桌上已经没有牌了\n");141 }142 return 0;143 }
为了程序的鲁棒性,需要进一步的测试,优化,暂时先不完善了(提示:需要设置一定的条件)