【蓝桥杯】【啊哈！算法】纸牌游戏——小猫钓鱼（队列和栈的应用）

水深无声 2022-11-17 05:25 193阅读 0赞

## [【啊哈！算法】系列文章目录][Link 1] ##

--------------------

### 目录 ###

*   *  【啊哈！算法】系列文章目录
     *   *  需求介绍
         *  思路分析
         *  C语言代码
         *  存在的问题
         *  C++ 代码

--------------------

### 需求介绍 ###

星期天小哼和小哈约在一起玩桌游，他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。**游戏的规则**是这样的：将一副扑克牌平均分成两份，每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上，然后小哈也拿出手中的第一张扑克牌，并放在小哼刚打出的扑克牌的上面，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时，游戏结束，对手获胜。（牌面为1~9）

**数据输入：** 第一行分别为为小哼、小哈手中牌的数目，第二行是小哼手中的牌，第三行是小哈手中的牌，不同牌之间用空格隔开。  
**数据输出：** 第一行是胜利者，如小哼胜，则为“小哼win”；如小哈胜，则为“小哈win”；  
      第二行是胜利者手中的牌，中间用空格隔开；  
      第三行是桌上的牌，中间用空格隔开。

--------------------

### 思路分析 ###

我们先来分析一下这个游戏有哪几种操作。小哼有两种操作，分别是出牌和赢牌。这恰好对应**队列**的两个操作，出牌就是出队，赢牌就是入队。小哈的操作和小哼是一样的。而桌子就是一个**栈**，每打出一张牌放到桌上就相当于入栈。当有人赢牌的时候，依次将牌从桌上拿走，这就相当于出栈。那如何解决赢牌的问题呢？**赢牌的规则**是：如果某人打出的牌与桌上的某张牌相同，即可将两张牌以及中间所夹的牌全部取走。那如何知道桌上已经有哪些牌了呢？最简单的方法就是**枚举**桌上的每一张牌，当然也有**更好的办法**，就是用一个数组来记录桌上有哪些牌。因为牌面只有 1~9，因此只需开一个大小为 10 的数组来记录当前桌上已经有哪些牌面就可以了。

OK，小结一下，我们需要**两个队列、一个栈**来模拟整个游戏。

### C语言代码 ###

#include <stdio.h>
    
    struct queue { 
    	int data[1000];
    	int head;
    	int tail;
    };
    
    struct stack { 
    	int data[20];
    	int top;
    };
    
    int book[20];
    
    void chupai(struct queue *q, struct stack *s) { 
    	int t;
    	t = q->data[q->head]; //小哼出一张牌
    	q->head++;
    	// 判断小哼当前打出的牌是否能赢得桌上的牌
    	if(book[t]==0) {  //表明桌上没有牌面为t的牌
    		//小哼此轮没有赢牌
    		s->top++;
    		s->data[s->top] = t;  //再把打出的牌放到桌上，即入栈
    		book[t] = 1;  //标记桌上现在已经有牌面为t的牌
    	}
    	else { 
    		//小哼此轮可以赢牌
    		q->data[q->tail] = t; //因为此轮可以赢牌，所以紧接着把刚才打出的牌又放到手中牌的末尾
    		q->tail++;
    		while(s->data[s->top]!=t) {   //把桌上可以赢得的牌（从当前桌面最顶部一张牌开始取，直至取到与打出的牌相同为止）依次放到手中牌的末尾
    			book[s->data[s->top]]=0; //取消标记
    			q->data[q->tail] = s->data[s->top]; ///依次放入队尾
    			q->tail++;
    			s->top--;  //栈中少了一张牌，所以栈顶要减1
    		}
    		
    		//收起最后一张一样的牌，并将标志置0 
    		book[s->data[s->top]]=0; //取消标记
    		q->data[q->tail] = s->data[s->top]; ///依次放入队尾
    		q->tail++;
    		s->top--;  //栈中少了一张牌，所以栈顶要减1
    	}
    }
    
    
    int main() { 
    	struct queue quene1, quene2;
    	struct stack stack1;
    	struct queue *q1,*q2;
    	struct stack *s;
    	q1=&quene1; q2=&quene2;
    	s=&stack1;
    	int i,t;
    	int hengN, haN;
    	//初始化队列q1和q2为空，此时两人手中都还没有牌
    	q1->head=0; q1->tail=0;
    	q2->head=0; q2->tail=0;
    	//初始化栈s为空，最开始的时候桌上也没有牌
    	s->top=0;
    	//初始化用来标记的数组，用来标记哪些牌已经在桌上
    	for(i=0;i<20;i++) { 
    		book[i] = 0;
    	}
    	
    	// 获取小哼和小哈手中牌的初始数目 
    	scanf("%d %d",&hengN, &haN);
    	
    	// 获取小哼初始牌面
    	for(i=0;i<hengN;i++) { 
    		scanf("%d",&q1->data[i]); //读入一个数到队尾
    		q1->tail++; //队尾往后挪一位
    	}
    	// 获取小哈初始牌面
    	for(i=0;i<haN;i++) { 
    		scanf("%d",&q2->data[i]); //读入一个数到队尾
    		q2->tail++; //队尾往后挪一位
    	}
    	
    	//现在准备工作已经基本上做好了，游戏正式开始，小哼先出牌。
    	while(1) //当队列不为空的时候执行循环
    	{ 
    		chupai(q1, s);  //小哼出牌
    		if(q1->head==q1->tail) 
    		{ 
    			printf("小哈win\n");
    			printf("小哈当前手中的牌是");
    			for(i=q2->head;i<q2->tail;i++) 
    			{ 
    				printf(" %d",q2->data[i]);
    			}
    			break;
    		}
    		chupai(q2, s);  //小哈出牌
    		if(q2->head==q2->tail) 
    		{ 
    			printf("小哼win\n");
    			printf("小哼当前手中的牌是");
    			for(i=q1->head;i<q1->tail;i++) 
    			{ 
    				printf(" %d",q1->data[i]);
    			}
    			break;
    		}
    	}
    		
    	if(s->top>0) //如果桌上有牌则依次输出桌上的牌
    	{ 
    		printf("\n桌上的牌是");
    		for(i=1;i<=s->top;i++) {  
    			printf(" %d",s->data[i]);
    		} 
    	}
    	else {  
    		printf("\n桌上已经没有牌了");
    	} 
    	
    	return 0;
    }

> **注：**
> 
>  *  书中的代码在收牌时并没有将桌上相同的那张牌收回，此处已收回，故结果与书中不同
>  *  书中代码如果小哼手中没牌了，小哈还会再多下一步，此处改为小哼手中没牌了，就直接结束游戏。

可以输入以下数据进行验证：

> 6 6  
> 2 4 1 2 5 6  
> 3 1 3 5 6 4

运行结果是：

> 小哈win  
> 小哈当前手中的牌是 1 6 5 2 3 4 1  
> 桌上的牌是 3 4 5 6 2

### 存在的问题 ###

你需要自己设计一些测试数据来检验你的程序。在设计测试数据的时候你要考虑各种情况，包括各种极端情况。通过设计测试数据来检测我们的程序是否“健壮”是非常重要的，如果你的程序可以通过任何一组测试数据，才表示你的程序是完全正确的。  
  如果你设计一些测试数据来验证的话，会发现我们刚才的代码其实还是有问题的。比如**游戏可能无法结束**。就是小哼和小哈可以永远玩下去，谁都无法赢得对方所有的牌。请你自己想一想如何解决游戏无法结束的问题。

### C++ 代码 ###

#include <iostream>
    #include <stack> 
    #include <queue> 
    #include <string>
    using namespace std;
    
    queue<int> q1, q2;
    stack<int> s;
    int book[14] = {  0 };
    int HengWin = 0, HaWin = 0;
    
    void DataInit(void);
    void PlayGame(queue<int>& q);
    void printResult(void);
    
    int main()
    { 
    	// 给小哼和小哈发牌 
    	DataInit();
    
    	while (1)
    	{ 
    		// 小哼出牌
    		PlayGame(q1);
    		if (q1.empty())		//判断是否游戏结束
    		{ 
    			HaWin = 1;
    			break;
    		}
    
    		// 小哈出牌
    		PlayGame(q2);
    		if (q2.empty())		//判断是否游戏结束
    		{ 
    			HengWin = 1;
    			break;
    		}
    	}
    
    	// 输出游戏结果
    	printResult();
    
    	return 0;
    }
    
    
    void DataInit(void)
    { 
    	int hengN, haN;
    	int iTemp;
    
    	// 获取小哼和小哈手中牌的初始数目 
    	cin >> hengN >> haN;
    
    	// 获取小哼初始牌面 
    	for (char i = 0; i < hengN; i++)
    	{ 
    		cin >> iTemp;
    		q1.push(iTemp);
    	}
    
    	// 获取小哈初始牌面 
    	for (char i = 0; i < haN; i++)
    	{ 
    		cin >> iTemp;
    		q2.push(iTemp);
    	}
    }
    
    
    void PlayGame(queue<int>& q)
    { 
    	//获取需要打出的牌 
    	int NowData = q.front();
    
    	//如果桌面不是空的，并且桌面上存在需要打出的牌 
    	if (!s.empty() && book[NowData] != 0)
    	{ 
    		//将牌打出，然后收起放到队尾 
    		q.pop();
    		q.push(NowData);
    
    		//开始收牌，直到需要收的牌与刚打出的牌面一样（不一样就一直收） 
    		while (NowData != s.top())
    		{ 
    			book[s.top()] = 0;		//桌面上已不存在将要收起的牌，标志置0 
    			q.push(s.top());
    			s.pop();
    		}
    
    		//收起最后一张一样的牌，并将标志置0 
    		book[NowData] = 0;
    		q.push(s.top());
    		s.pop();
    		return;	//出牌结束 
    	}
    
    	//否则，将手中牌打出
    	q.pop();
    	s.push(NowData);
    	book[NowData] = 1;
    }
    
    void printResult(void)
    { 
    	if (HaWin)
    	{ 
    		cout << "小哈Win！" << endl;
    		cout << "小哈手中的牌为：";
    		while (!q2.empty())
    		{ 
    			cout << q2.front() << " ";
    			q2.pop();
    		}
    	}
    
    	if (HengWin)
    	{ 
    		cout << "小哼Win！" << endl;
    		cout << "小哼手中的牌为：";
    		while (!q1.empty())
    		{ 
    			cout << q1.front() << " ";
    			q1.pop();
    		}
    	}
    
    	if (s.empty())
    	{ 
    		cout << endl << "桌上已经没有牌了";
    	}
    	else
    	{ 
    #if 0
    		//方式1：从栈顶 到 栈底 输出
    		cout << endl << "桌面上的牌为： ";
    		while (!s.empty())
    		{ 
    			cout << s.top() << " ";
    			s.pop();
    		}
    #else
    		//方式2：从栈底 到 栈顶 输出
    		stack<int> s_temp;
    		while (!s.empty())
    		{ 
    			s_temp.push(s.top());
    			s.pop();
    		}
    
    		cout << endl << "桌面上的牌为： ";
    		while (!s_temp.empty())
    		{ 
    			cout << s_temp.top() << " ";
    			s_temp.pop();
    		}
    #endif
    	}
    }

可以输入以下数据进行验证：

> 6 6  
> 2 4 1 2 5 6  
> 3 1 3 5 6 4

运行结果是：

> 小哈Win！  
> 小哈手中的牌为：1 6 5 2 3 4 1  
> 桌面上的牌为： 3 4 5 6 2

[Link 1]: https://blog.csdn.net/weixin_43964993/article/details/115446128