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

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

新老客户大回馈,云服务器低至5折

简述

本算法摘选自啊哈磊所著的《啊哈!算法》第二章第三节的题目——纸牌游戏小猫钓鱼。文中代码使用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获胜,这在原文中是没有的,但是赶紧这个细节不太重要,可有可无吧,也不过多纠结了。

学习总结

上面这个游戏解法,让我对队列、栈的操作以及桶的使用深有体会,熟练掌握了这些数据结构的定义以及特征,并且能够有意识的使用这些数据结构来解决一些类似的算法问题,收益颇丰。

参考资料

1、《啊哈!算法》/ 啊哈磊著. 人民邮电出版社


原文链接:https://www.cnblogs.com/captainad/p/11018987.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:JAVA 统计字符串中中文,英文,数字,空格,特殊字符的个数

下一篇:Java复习一