欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-28 19:57:22
简述 本算法摘选自啊哈磊所著的《啊哈!算法》第二章第三节的题目——纸牌游戏小猫钓鱼。文中代码使用C语言编写,但是仔细看了一遍发现原书中有个细节是错误的,也就是说按照算法题目意思,原书中作者的代码是有出入的,具体可以往本篇博文继续看。 博主通过阅读和理解,重新由Java代码实现了一遍,意在深刻理解队列 ......

简述

本算法摘选自啊哈磊所著的《啊哈!算法》第二章第三节的题目——纸牌游戏小猫钓鱼。文中代码使用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、《啊哈!算法》/ 啊哈磊著. 人民邮电出版社