<p>
星期天小哼和小哈约在一起玩桌游,他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。游戏的规则是这样的:将一副扑克牌平均分成两份,每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上,然后小哈也拿出手中的第一张扑克牌,并放在小哼刚打出的扑克牌的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即可将两张相同的牌及其中间所夹的牌全部取走,并依次放到自己手中牌的 尾。当任意一人手中的牌全部出完时,游戏结束,对手获胜。
</p>
<p>假如游戏开始时,小哼手中有 6 张牌,顺序为 2 4 1 2 5 6,小哈手中也有 6 张牌,顺序为 3 1 3 5 6 4,最终谁会获胜呢?现在你可以拿出纸牌来试一试。接下来请你写一个程序来自动判断谁将获胜。这里我们做一个约定,小哼和小哈手中牌的牌面只有 1~9。</p>
<p>我们先来分析一下这个游戏有哪几种操作。小哼有两种操作,分别是出牌和赢牌。这恰好对应队列的两个操作,出牌就是出队,赢牌就是入队。小哈的操作和小哼是一样的。而桌子就是一个栈,每打出一张牌放到桌上就相当于入栈。当有人赢牌的时候,依次将牌从桌上拿走,这就相当于出栈。那如何解决赢牌的问题呢?赢牌的规则是:如果某人打出的牌与桌上的某张牌相同,即可将两张牌以及中间所夹的牌全部取走。那如何知道桌上已经有哪些牌了呢?最简单的方法就是枚举桌上的每一张牌,当然也有更好的办法我们待会再说。OK,小结一下,我们需要两个队列、一个栈来模拟整个游戏。</p>
<p>首先我们先来创建一个结构体用来实现队列,如下。</p>
<p>struct queue{ int data[1000]; int head; int tail; }</p>
<p>上面代码中 head 用来存储队头,tail 用来存储队尾。数组 data 用来存储队列中的元素,数组 data 的大小我预设为 1000,其实应该设置得更大一些,以防数组越界。当然对于 题的数据来说 1000 已经足够了。</p>
<p> 再创建一个结构体用来实现栈,如下。</p>
<p>struct stack{ int data[10]; int top; };</p>
<p>其中 top 用来存储栈顶,数组 data 用来存储栈中的元素,大小设置为 10。因为只有 9种不同的牌面,所以桌上最多可能有 9 张牌,因此数组大小设置为 10 就够了。提示一下:为什么不设置为 9 呢?因为 C 语言数组下标是从 0 开始的。</p>
<p>其中 top 用来存储栈顶,数组 data 用来存储栈中的元素,大小设置为 10。因为只有 9种不同的牌面,所以桌上最多可能有 9 张牌,因此数组大小设置为 10 就够了。提示一下:为什么不设置为 9 呢?因为 C 语言数组下标是从 0 开始的。</p>
<p>struct queue q1,q2; struct stack s;</p>
<p> 接下来来初始化一下队列和栈。</p>
<p>//初始化队列q1和q2为空,此时两人手中都还没有牌 q1.head=1; q1.tail=1; q2.head=1; q2.tail=1; //初始化栈s为空,最开始的时候桌上也没有牌 s.top=0;</p>
<p>接下来需要读入小哼和小哈最初时手中的牌,分两次读入,每次读入 6 个数,分别插入q1和q2中。</p>
<p>// 依次像队列中插入6个数 // 小哼手中的牌 printf("请设置小哼手中的牌:\n"); for (i=1; i<=6; i++) { scanf("%d",&q1.data[q1.tail]); q1.tail++; } printf("\n"); printf("请设置小哈手中的牌:\n"); // 小哈手中的牌 for (i=1; i<=6; i++) { scanf("%d",&q2.data[q2.tail]); q2.tail++; } printf("\n");</p>
<p>现在准备工作已经基 上做好了,游戏正式开始,小哼先出牌。</p>
<p>t=q1.data[q1.head]; //小哼先亮出一张牌</p>
<p>小哼打出第一张牌,也就是 q1 的队首,我们将这张牌存放在临时变量 t 中。接下来我们要判断小哼当前打出的牌是否能赢得桌上的牌。也就是判断桌上的牌与 t 有没有相同的,如何实现呢?我们需要枚举桌上的每一张牌与 t 进行比对,具体如下:</p>
<p>flag=0; for(i=1;i<=top;i++) { if(t==s[i]) { flag=1; break; } }</p>
<p>如果 flag 的值为 0 就表明小哼没能赢得桌上的牌,将打出的牌留在桌上</p>
<p>if(flag==0){ //小哼此轮没有赢牌 q1.head++; //小哼已经打出一张牌,所以要把打出的牌出队 s.top++; s.data[s.top]=t; //再把打出的牌放到桌上,即入栈 }</p>
<p>如果 flag 的值为 1 就表明小哼可以赢得桌上的牌,需要将赢得的牌依次放入小哼的手中。</p>
<p>if(flag==1) { //小哼此轮可以赢牌 q1.head++;//小哼已经打出一张牌,所以要把打出的牌出队 q1.data[q1.tail]=t; //因为此轮可以赢牌,所以紧接着把刚才打出的牌又放到手中牌的对尾 q1.tail++; while(s.data[s.top]!=t) //把桌上可以赢得的牌(从当前桌面最顶部一张牌开始取,直至取到与打出的牌相同为止)依次放到手中牌的末尾 { q1.data[q1.tail]=s.data[s.top]; //依次放入队尾 q1.tail++; s.top--; //栈中少了一张牌,所以栈顶要减1 } }</p>
<p>小哼出牌的所有阶段就模拟完了,小哈出牌和小哼出牌是一样的。接下来我们要判断游戏如何结束。即只要两人中有一个人的牌用完了游戏就结束了。因此需要在模拟两人出牌代码的外面加一个 while 循环来判断,如下。</p>
<p>while(q1.head<q1.tail && q2.head<q2.tail ) //当队列q1和q2都不为空的时候执行循环</p>
<p>最后一步,输出谁最终赢得了游戏,以及游戏结束后获胜者手中的牌和桌上的牌。如果
小哼获胜了那么小哈的手中一定没有牌了(队列 q2 为空),即 q2.head==q2.tail,具体输出如下。</p>
<p>if(q2.head==q2.tail){ printf("小哼win\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]); }else printf("\n桌上已经没有牌了");} }</p>
<p>反之,小哈获胜,代码的实现也是差不多的,就不再赘述了。到此,所有的代码实现就都讲完了。</p>
<p>在上面我们讲解的所有实现中,每个人打出一张牌后,判断能否赢牌这一点可以优化。之前我们是通过枚举桌上的每一张牌来实现的,即用了一个 for 循环来依次判断桌上的每一张牌是否与打出的牌相等。其实有更好的办法来解决这个问题,就是用一个数组来记录桌上有哪些牌。因为牌面只有 1~9,因此只需开一个大小为 10 的数组来记录当前桌上已经有哪些牌面就可以了。</p>
<p>int book[10];</p>
<p>这里我再一次使用了 book 这个单词,因为这个单词有记录、登记的意思,而且单词拼写简洁。另外很多国外的算法书籍在处理需要标记问题的时候也都使用 book 这个单词,因此我这里就沿用了。当然你也可以使用 mark 等你自己觉得好理解的单词啦。下面需要将数组 book[1]~book[9]初始化为 0,因为刚开始桌面上一张牌也没有。</p>
<p>for(i=1;i<=9;i++) book[i]=0;</p>
<p>接下来,如果桌面上增加了一张牌面为 2 的牌,那就需要将 book[2]设置为 1,表示牌面为 2 的牌桌上已经有了。当然如果这张牌面为 2 的牌被拿走后,需要及时将 book[2]重新设置为 0,表示桌面上已经没有牌面为 2 的牌了。这样一来,寻找桌上是否有与打出的牌牌面相同的牌,就不需要再循环枚举桌面上的每一张牌了,而只需用一个 if 判断即可。这一点是不是有点像第 1 章第 1 节的桶排序的方法呢?具体如下。</p>
<p>t=q1.data[q1.head]; //小哼先亮出一张牌 if(book[t]==0) // 表明桌上没有牌面为t的牌 { //小哼此轮没有赢牌 q1.head++; //小哼已经打出一张牌,所以要把打出的牌出队 s.top++; s.data[s.top]=t; //再把打出的牌放到桌上,即入栈 book[t]=1; //标记桌上现在已经有牌面为t的牌 }</p>
<p>OK,算法的实现讲完了,下面给出完整的代码,如下:</p>
<p>``
include <stdio.h>
include <string.h>
// 使用结构体 (queue) 来表示小哼和小哈手中的牌
struct queue{
int data[1000]; // 用户手中的牌
int head; // 队首
int tail; // 对尾
};
// 使用结构体 (stack) 来表示桌面上的牌
struct stack{
int data[10]; // 桌面上所有的牌
int top; // 桌面上最上边的牌
};
int main(){
struct queue q1, q2; // 声名小哼, 小哈
struct stack s; // 声名桌面上的牌
int book[10]; // 用来标记桌面上的牌
int i, t;
q1.head = 1; // 初始化小哼
q1.tail = 1;
q2.head = 1; // 初始化小哈
q2.tail = 1;
s.top = 0; // 初始化栈, 桌面上最上边的的牌的索引
// 初始化用来标记的数组, 用来标记哪些牌出现过
for (i=1; i<=9; i++) {
book[i] = 0;
}
// 依次像队列中插入6个数
// 小哼手中的牌
printf("请设置小哼手中的牌:\n");
for (i=1; i<=6; i++) {
scanf("%d",&q1.data[q1.tail]);
q1.tail++;
}
printf("\n");
printf("请设置小哈手中的牌:\n");
// 小哈手中的牌
for (i=1; i<=6; i++) {
scanf("%d",&q2.data[q2.tail]);
q2.tail++;
}
printf("\n");
// 当队列不为空的时候执行循环 (判断小哼小哈手中是否有牌)
while (q1.head < q1.tail && q2.head < q2.tail) {
// 游戏开始
// 小哼先出第一张牌
t = q1.data[q1.head];
// 判断小哼是否能赢牌
if (book[t] == 0) {
// 没有赢牌
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--;
}
}
// 小哈出牌
t = q2.data[q2.head];
// 判断小哈是否能赢牌
if (book[t] == 0) {
// 没有赢牌
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--;
}
}
}
// 判断输赢
if (q2.head == q2.tail) {
printf("小哼 win \n");
printf("小哼当前手中的牌是:");
for (i=q1.head; i<q1.tail; i++) {
printf(" %d",q1.data[i]);
}
if (s.top > 0) { // 如果桌上有牌则依次输出桌上的牌
printf("桌上的牌是:");
for (i=1; i<=s.top; i++) {
printf("%d",s.data[i]);
}
}else{
printf("\n 桌上已经没有牌了 ^º^ ");
}
}else{
printf("小哈 win \n");
printf("小哈当前手中的牌是:");
for (i=q1.head; i<q1.tail; i++) {
printf(" %d",q1.data[i]);
}
if (s.top > 0) { // 如果桌上有牌则依次输出桌上的牌
printf("桌上的牌是:");
for (i=1; i<=s.top; i++) {
printf("%d",s.data[i]);
}
}else{
printf("\n 桌上已经没有牌了 ^º^ ");
}
}
printf("\n");
return 0;
} ``</p>
