扑克牌的问题

问题描述:

     假设有A和B来两个人玩牌。游戏的规则是这样的:将一副牌均分成两份,每人拿一份。A先拿出手中的第一张扑克牌,放在桌上,然后B也拿出手中的第一张扑克牌,放在A刚打出来的扑克牌的上面,就这样两人交替出牌。出牌时,如果某人打出的牌与桌上的某张牌的牌面相同,即可将两种牌以及其中间的所有牌全部取走,并按照从上到下的顺序依次放到自己手中牌的末尾。当任意一人手中的牌全部取完时,游戏结束,对手获胜。 先假设A手上有牌,按顺序依次为:2 4 1 2 5 6,B手上有牌顺序为:3 1 3 5 6 4。写程序判断谁会赢。

这个问题其实就是考察对栈和队列两种数据结构的应用。代码如下:

  1 package com.rampage.algorithm.base;
  2 
  3 import java.util.ArrayList;
  4 import java.util.List;
  5 import java.util.Stack;
  6 
  7 /**
  8  * 
  9  * @author zyq
 10  *
 11  */
 12 public class PokerGame1 {
 13 
 14     public static void main(String[] args) {
 15         
 16         int[] arr1 = { 2, 4, 1, 2, 5, 6 }; int[] arr2 = { 3, 1, 3, 5, 6, 4 };
 17          
 18 
 19         // 这个是一个永远不会结束的循环
 20         /*int[] arr1 = { 1, 1, 1 };
 21         int[] arr2 = { 1, 2, 1 };*/
 22         PokerGame1 game = new PokerGame1();
 23         game.play(arr1, arr2);
 24     }
 25 
 26     /**
 27      * 
 28      * @param arr1
 29      * @param arr2
 30      */
 31     private void play(int[] arr1, int[] arr2) {
 32         if (arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0 || arr1.length != arr2.length) {
 33             System.out.println("Illegal card array for game!");
 34             return;
 35         }
 36 
 37         /**
 38          * 其实这道题的考查重点就在于栈和列表两种数据结构的考查,我们用栈来表示桌面上的牌(因为桌面上的牌放上去和取走的时候符合栈的特性)。用队列(queue,java中用List即可)来表示
 39          * 存储每个人手中的牌。
 40          */
 41         List<Integer> list1 = new ArrayList<Integer>(arr1.length);
 42         List<Integer> list2 = new ArrayList<Integer>(arr2.length);
 43         Stack<Integer> stack = new Stack<Integer>(); // 存储桌面上的牌
 44 
 45         // 首先将数组中的牌入列表
 46         for (int i = 0; i < arr1.length; i++) {
 47             list1.add(arr1[i]);
 48             list2.add(arr2[i]);
 49         }
 50 
 51         int turnCount = 0;
 52         // 当两个人手上的牌都不为空的时候,模拟出牌过程
 53 
 54         // 还有一种可能就是会无限循环下去,对于这种情况其实发现到后面就是两者之间的牌会又回到最初的状态。
 55         // 所以这里给两个列表来存储最开始时的牌的状态,如果后续发现又变成一样,则证明会出现无限循环。
 56         List<Integer> originalList1 = new ArrayList<Integer>(list1);
 57         List<Integer> originalList2 = new ArrayList<Integer>(list2);
 58 
 59         while (list1.size() > 0 && list2.size() > 0) {
 60             // 首先A出牌
 61             int element = list1.remove(0);
 62 
 63             // 如果栈中已经有可收回的牌,则收回栈中的牌并且放到A中牌的末尾
 64             if (stack.contains(element)) {
 65                 list1.add(element);
 66                 int popOne;
 67                 while ((popOne = stack.pop()) != element) {
 68                     list1.add(popOne);
 69                 }
 70                 list1.add(popOne);
 71             } else {
 72                 stack.push(element);
 73                 // 如果没有可以收回的牌,则判断当前A中的牌是否为空。
 74                 if (list1.size() == 0) {
 75                     break;
 76                 }
 77             }
 78 
 79             // 然后B出牌
 80             element = list2.remove(0);
 81 
 82             // 如果栈中已经有可收回的牌,则收回栈中的牌并且放到B中牌的末尾
 83             if (stack.contains(element)) {
 84                 list2.add(element);
 85                 int popOne;
 86                 while ((popOne = stack.pop()) != element) {
 87                     list2.add(popOne);
 88                 }
 89                 list2.add(popOne);
 90             } else {
 91                 stack.push(element);
 92                 // 如果没有可以收回的牌,则判断当前B中的牌是否为空。
 93                 if (list2.size() == 0) {
 94                     break;
 95                 }
 96             }
 97 
 98             System.out.println("Turn " + (++turnCount) + " result:");
 99             System.out.print("Player A:");
100             for (int one : list1) {
101                 System.out.print(one + ", ");
102             }
103             System.out.print("\nPlayer B:");
104             for (int one : list2) {
105                 System.out.print(one + ", ");
106             }
107             System.out.print("\nDesk:");
108             for (int i = stack.size() - 1; i >= 0; i--) {
109                 System.out.print(stack.elementAt(i) + ", ");
110             }
111             System.out.println("\n");
112 
113             // 当桌上没牌的时候,判断牌的状态是否又回到最初。
114             if (stack.isEmpty()) {
115                 if ((originalList1.size() == list1.size() && originalList1.containsAll(list1)
116                         && originalList2.size() == list2.size() && originalList2.containsAll(list2))
117                         || (originalList1.size() == list2.size() && originalList1.containsAll(list2)
118                                 && originalList2.size() == list1.size() && originalList2.containsAll(list1))) {
119                     System.out.println("Player A and Player B tie!");
120                     return;
121                 }
122             }
123         }
124 
125         // 根据最后谁手上的牌为空,输出结果
126         if (list1.size() == 0) {
127             System.out.println("Player B win.The cards in player B are:");
128             for (Integer one : list2) {
129                 System.out.print(one + ", ");
130             }
131         } else {
132             System.out.println("Player A win.The cards in player A are:");
133             for (Integer one : list1) {
134                 System.out.print(one + ", ");
135             }
136         }
137 
138         System.out.println("\nThe cards in the desk are:");
139         while (stack.size() > 0) {
140             System.out.print(stack.pop() + ", ");
141         }
142 
143     }
144 }

 输出结果为:

  1 Turn 1 result:
  2 Player A:4, 1, 2, 5, 6, 
  3 Player B:1, 3, 5, 6, 4, 
  4 Desk:3, 2, 
  5 
  6 Turn 2 result:
  7 Player A:1, 2, 5, 6, 
  8 Player B:3, 5, 6, 4, 
  9 Desk:1, 4, 3, 2, 
 10 
 11 Turn 3 result:
 12 Player A:2, 5, 6, 1, 1, 
 13 Player B:5, 6, 4, 3, 4, 3, 
 14 Desk:2, 
 15 
 16 Turn 4 result:
 17 Player A:5, 6, 1, 1, 2, 2, 
 18 Player B:6, 4, 3, 4, 3, 
 19 Desk:5, 
 20 
 21 Turn 5 result:
 22 Player A:6, 1, 1, 2, 2, 5, 5, 
 23 Player B:4, 3, 4, 3, 
 24 Desk:6, 
 25 
 26 Turn 6 result:
 27 Player A:1, 1, 2, 2, 5, 5, 6, 6, 
 28 Player B:3, 4, 3, 
 29 Desk:4, 
 30 
 31 Turn 7 result:
 32 Player A:1, 2, 2, 5, 5, 6, 6, 
 33 Player B:4, 3, 
 34 Desk:3, 1, 4, 
 35 
 36 Turn 8 result:
 37 Player A:2, 2, 5, 5, 6, 6, 1, 3, 1, 
 38 Player B:3, 4, 4, 
 39 Desk:
 40 
 41 Turn 9 result:
 42 Player A:2, 5, 5, 6, 6, 1, 3, 1, 
 43 Player B:4, 4, 
 44 Desk:3, 2, 
 45 
 46 Turn 10 result:
 47 Player A:5, 5, 6, 6, 1, 3, 1, 2, 3, 2, 
 48 Player B:4, 
 49 Desk:4, 
 50 
 51 Turn 11 result:
 52 Player A:5, 6, 6, 1, 3, 1, 2, 3, 2, 
 53 Player B:4, 5, 4, 
 54 Desk:
 55 
 56 Turn 12 result:
 57 Player A:6, 6, 1, 3, 1, 2, 3, 2, 
 58 Player B:5, 4, 
 59 Desk:4, 5, 
 60 
 61 Turn 13 result:
 62 Player A:6, 1, 3, 1, 2, 3, 2, 
 63 Player B:4, 5, 6, 4, 5, 
 64 Desk:
 65 
 66 Turn 14 result:
 67 Player A:1, 3, 1, 2, 3, 2, 
 68 Player B:5, 6, 4, 5, 
 69 Desk:4, 6, 
 70 
 71 Turn 15 result:
 72 Player A:3, 1, 2, 3, 2, 
 73 Player B:6, 4, 5, 
 74 Desk:5, 1, 4, 6, 
 75 
 76 Turn 16 result:
 77 Player A:1, 2, 3, 2, 
 78 Player B:4, 5, 6, 3, 5, 1, 4, 6, 
 79 Desk:
 80 
 81 Turn 17 result:
 82 Player A:2, 3, 2, 
 83 Player B:5, 6, 3, 5, 1, 4, 6, 
 84 Desk:4, 1, 
 85 
 86 Turn 18 result:
 87 Player A:3, 2, 
 88 Player B:6, 3, 5, 1, 4, 6, 
 89 Desk:5, 2, 4, 1, 
 90 
 91 Turn 19 result:
 92 Player A:2, 
 93 Player B:3, 5, 1, 4, 6, 
 94 Desk:6, 3, 5, 2, 4, 1, 
 95 
 96 Turn 20 result:
 97 Player A:2, 6, 3, 5, 2, 
 98 Player B:5, 1, 4, 6, 
 99 Desk:3, 4, 1, 
100 
101 Turn 21 result:
102 Player A:6, 3, 5, 2, 
103 Player B:1, 4, 6, 
104 Desk:5, 2, 3, 4, 1, 
105 
106 Turn 22 result:
107 Player A:3, 5, 2, 
108 Player B:4, 6, 1, 6, 5, 2, 3, 4, 1, 
109 Desk:
110 
111 Turn 23 result:
112 Player A:5, 2, 
113 Player B:6, 1, 6, 5, 2, 3, 4, 1, 
114 Desk:4, 3, 
115 
116 Turn 24 result:
117 Player A:2, 
118 Player B:1, 6, 5, 2, 3, 4, 1, 
119 Desk:6, 5, 4, 3, 
120 
121 Player B win.The cards in player B are:
122 1, 6, 5, 2, 3, 4, 1, 
123 The cards in the desk are:
124 2, 6, 5, 4, 3, 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P3959 宝藏(模拟退火乱搞)

872
来自专栏FD的专栏

Effective Testing with RSpec 3 (英文版)(序言)

Early praise for Effective Testing with RSpec 3

1464
来自专栏智能计算时代

deepstream 2.0 outperforms socket.io by more than x 1000

By Wolfram Hempel November 21st 2016 Realtime is growing fast. From collaborativ...

2114
来自专栏数据结构与算法

cf914D. Bash and a Tough Math Puzzle(线段树)

可以这么想,如果能成功的话,我们可以把那个数改成$1$,这样比$x$大的数就不会对答案产生影响了。

521
来自专栏小樱的经验随笔

Code forces 719A Vitya in the Countryside

A. Vitya in the Countryside time limit per test:1 second memory limit per test:2...

3206
来自专栏数据结构与算法

BZOJ 2654: tree(二分 最小生成树)

1380
来自专栏androidBlog

快速排序的相关算法题(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

711
来自专栏数据结构与算法

洛谷P3128 [USACO15DEC]最大流Max Flow(树上差分)

边差分就是对边进行操作,我们在$u, v$除加上$val$,同时在$lca$处减去$2 * val$

653
来自专栏搜云库

《十大经典排序算法》简介

十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的...

1826
来自专栏图形学与OpenGL

Avoiding UpdateData(ZZ)

Microsoft does not adequately document the correct way to work ...

462

扫码关注云+社区