啊哈算法之纸牌游戏小猫钓鱼

2019-06-14 08:03:27来源：博客园阅读 ()

简述

本算法摘选自啊哈磊所著的《啊哈！算法》第二章第三节的题目——纸牌游戏小猫钓鱼。文中代码使用C语言编写，但是仔细看了一遍发现原书中有个细节是错误的，也就是说按照算法题目意思，原书中作者的代码是有出入的，具体可以往本篇博文继续看。

博主通过阅读和理解，重新由Java代码实现了一遍，意在深刻理解队列和栈这两种数据结构的特性和操作方法，并希望能够在这种数据结构的帮助之下，解决其他的类似的能够用队列和栈来解决的问题。（哈哈，偷懒了，引用这类简述屡试不爽^_^）

纸牌游戏

“小猫钓鱼”的游戏规则是这样的：将一副扑克牌平均分成两份，每人拿一份。玩家U1先拿出手中的第一张扑克牌放在桌上，然后玩家U2也拿出手中的第一张扑克牌，并放在玩家U1刚打出的扑克牌的上面，就像这样两个玩家交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一个人手中的牌全部出完时，游戏结束，对手获胜。

现在要求你写一个算法来模拟这场游戏，并判断出谁最后获胜，获胜的同事打印出获胜者手中的牌以及桌上可能剩余的牌。

在写程序开始前，我们暂且先做一个约定，玩家U1和U2手中牌的牌面值只有1~9。

解法思路

我们可以先分析一下这个游戏存在哪几种操作。玩家U1有两种操作，分别是出牌和赢牌，出牌时将手中的牌打出去，赢牌的时候将桌上的牌放到手中牌的末尾，这恰好对应了队列的两个操作，出牌就是队列出队，赢牌就是队列入队。玩家U1和玩家U2的操作是一样的。而桌子很明显就可以看作是一个栈，玩家没打出一站牌就放到桌上，相当于入栈，因为顺序是往后的，当有人赢牌的时候，依次将牌从桌上拿走，这就相当于出栈。那如何判断是否赢牌呢？赢牌的判断就是：如果某人打出的牌与桌上的某张牌相同，即可将两张牌及其中间的所夹得牌全部取走。那如何直到桌上现在有哪些牌呢，很容易想到的就是每次打出牌之后遍历一遍桌上已有的牌然后比对，存在相同的牌则算赢牌。这是简单而且粗暴一点的方法，其实有更好的方法，那就是用桶来解决这个问题，牌面值只有1-9，我们可以设置一个大小为10的数组作为桶，每打出一张牌，就以此牌的牌面值作为下标找到数组对应位置，如果该位置存在值，则说明桌上有存在的牌，如果没有值，则说明桌上没有相同的牌，同时在通上做标记，即数组该下标位置设置为1。那如果赢牌了，桌上的牌拿走了桶应该怎么办呢？也很简单，出栈的时候依次按照牌面值清空桶就行了。最终怎么判断哪个玩家获得最终胜利呢，获得最终胜利的标准就是对方手上已经没牌了，如果从队列角度看，那就是头指针和尾指针相等了。

从上面的思路分析可以看出，为了模拟这场游戏，我们需要准备两个队列、一个栈和一个桶，分别表示玩家U1U2手中的牌、桌上的牌以及桌上牌的牌面值。下面我们写具体的代码，为了方便阅读，关键代码上面我都给出非常详细的注释。

代码实现

  1 /**
  2  * @Project: dailypro
  3  * @PackageName: com.captainad.algorithm
  4  * @Author: Captain&D
  5  * @Website: https://www.cnblogs.com/captainad/
  6  * @DateTime: 2019/6/12 21:07.
  7  * @Description:
  8  */
  9 public class KittenFishingGame {
 10 
 11     /**
 12      * 自定义队列
 13      */
 14     static class MyQueue {
 15         /**
 16          * 数据列表
 17          */
 18         int[] data = new int[64];
 19         /**
 20          * 头指针
 21          */
 22         int head;
 23         /**
 24          * 尾指针
 25          */
 26         int tail;
 27 
 28         public MyQueue() {}
 29 
 30         public MyQueue(int head, int tail) {
 31             this.head = head;
 32             this.tail = tail;
 33         }
 34     }
 35 
 36     /**
 37      * 自定义栈
 38      */
 39     static class MyStack {
 40         /**
 41          * 数据列表
 42          */
 43         int[] data = new int[64];
 44         /**
 45          * 栈顶指针
 46          */
 47         int top;
 48 
 49         public MyStack() {}
 50 
 51         public MyStack(int top) {
 52             this.top = top;
 53         }
 54     }
 55 
 56     public static void main(String[] args) {
 57         // Step 1.初始化队列和栈
 58 
 59         // 两人手中都没有牌，初始化两个空的队列
 60         MyQueue q1 = new MyQueue(0, 0);
 61         MyQueue q2 = new MyQueue(0, 0);
 62 
 63         // 初始情况下桌上也没有牌，初始化一个空的栈
 64         MyStack desktop = new MyStack(0);
 65 
 66         // 依次读入两人最初时手中的牌，假设两个人有相同张数，每张牌的大小为1~9
 67         int[] u1 = {2, 4, 1, 2, 5, 6};
 68         int[] u2 = {3, 1, 3, 5, 6, 4};
 69         int len = u1.length;
 70 
 71         // 同时插入两个用户数据，队列尾指针往后移动
 72         for(int i = 0; i < len; i++) {
 73             q1.data[i] = u1[i];
 74             q1.tail++;
 75 
 76             q2.data[i] = u2[i];
 77             q2.tail++;
 78         }
 79 
 80         // Step 2.初始化一个桶，用来记录栈中数据
 81 
 82         // 判断桌上是否存在相同的牌，可以往栈里面遍历，也可以巧妙地使用桶的方式来处理，
 83         // 用牌值作为数组下标找到桶的位置，出牌入栈时就设置为1，如果下次出牌遇到桶里这个位置存在值，
 84         // 则说明牌值重复，可以赢得之前这张牌之间的所有牌，桶用完之后，出栈时需要把桶同步清理
 85         int[] book = new int[10];
 86 
 87         // Step 3.开始游戏，双方发牌并判断是否赢牌
 88 
 89         // 准备工作完成，游戏开始，u1先出牌
 90         // 当两个人手上都有牌时，继续游戏，即当队列不为空时，继续循环
 91         while(q1.head < q1.tail && q2.head < q2.tail) {
 92             // u1出牌
 93             play(q1, desktop, book);
 94             if(q1.head >= q1.tail) {
 95                 break;
 96             }
 97 
 98             // u1出牌结束后，轮到u2开始出牌，逻辑步骤和u1是一样的
 99             play(q2, desktop, book);
100 
101         }
102 
103         // Step 4.游戏结束，看谁手上没牌，没牌则对方获胜
104 
105         // 谁手上先没牌，则表示对方赢牌，没牌的标准就是该队列首尾指针相等
106         if(q1.head == q1.tail) {
107             win("u2", q2, desktop);
108         }else {
109             win("u1", q1, desktop);
110         }
111     }
112 
113     /**
114      * 赢得胜利的打印输出方法
115      * https://www.cnblogs.com/captainad/
116      * @param user 打牌的用户
117      * @param q 打牌用户手中的牌，即表示手中牌的队列
118      * @param desktop 打牌放牌的桌子，即栈
119      */
120     private static void win(String user, MyQueue q, MyStack desktop) {
121         System.out.println(user + " win. the card in the " + user + "'s hand is: ");
122         for(int k = q.head; k < q.tail; k++) {
123             System.out.print(q.data[k] + " ");
124         }
125         // 桌上是否还有牌，有牌则打印出来
126         if(desktop.top > 0) {
127             System.out.println("\nThe card in the desktop is: ");
128             for(int k = 0; k < desktop.top; k++) {
129                 System.out.print(desktop.data[k] + " ");
130             }
131         }
132     }
133 
134     /**
135      * 开始打牌的方法，谁打牌，谁就会调用这个方法
136      * https://www.cnblogs.com/captainad/
137      * @param q 打牌用户手中的牌，即表示手中牌的队列，谁打牌就是谁的队列
138      * @param desktop 打牌放牌的桌子，即栈
139      * @param book 记录桌子上已有牌的记录本，即数据桶
140      */
141     private static void play(MyQueue q, MyStack desktop, int[] book) {
142         // u出一张牌，从q队列中出队一个值
143         int t = q.data[q.head];
144 
145         // 判断当前打出的牌能否赢牌，即看桶中是否存在相同的值
146         // 如果桶中不存在，则表示桌面上没有相同的牌，u1没有赢，出队的牌入栈
147         if(book[t] == 0) {
148             // 出队
149             q.head++;
150             // 入栈，指针上移
151             desktop.data[desktop.top++] = t;
152             // 桶记录
153             book[t] = 1;
154         }else {
155             // 桶中存在相同值，u1赢牌
156             // u1出牌，所以出队
157             q.head++;
158             // 将u1出的牌放到自己末尾，同时能够拿桌上剩下的牌
159             q.data[q.tail++] = t;
160             // 桌上出栈的临时值
161             int n;
162             // 逐步拿起桌上的牌进行比对，比对到和刚刚放下去的那张牌相同为止，拿牌之后放在自己牌的末尾。
163             // 逐步将出栈的值与刚刚出队的值比对，出栈的同时下移指针，两个值不相同则继续循环
164             do {
165                 // 拿起的牌放到当前牌的后面，即将出栈的值放到队列末尾，同时后移尾指针
166                 n = desktop.data[--desktop.top];
167                 q.data[q.tail++] = n;
168                 // 因为栈中的牌拿走了，所以将桶清理干净
169                 book[n] = 0;
170             } while(n != t);
171             /* 啊哈算法书中，啊哈磊用的是while循环，这将导致桌上最后比对相同的那张牌不拿走，
172             这是和题面有出入的地方，这里用do-while循环能够解决这个问题 */
173         }
174     }
175 }

博主在原书代码的基础之上做了重构优化，应该还是能很清晰的阅读。

我声明了两个内部类分别是队列和栈，并在方法中使用数组book[]来充当桶的角色。

因为玩家U1和U2在出牌和赢牌的操作上是一致的，所以我抽取出了一个公共方法。在赢牌的环节中，为了能够让玩家拿起赢得桌上的所有牌，包括比对到的最后相同的那张牌，我用了一个do-while循环来处理，因为在原书中作者使用了一个while循环没能把最后该拿起的那张牌拿走，所以从题目上看来这点估计作者没有考虑到，我们在此就不深究了。

因为打完牌之后如果谁手上先没牌，对方就获胜了，所以在出牌的循环里面，玩家U1打完牌之后我立马判断了他手上有没有牌了，因为没有牌可能就会判断玩家U2获胜，这在原文中是没有的，但是赶紧这个细节不太重要，可有可无吧，也不过多纠结了。