8张扑克牌问题

02/06 11:42
阅读数 84

8张扑克牌问题

1、问题描述

有8张扑克牌,两张1,两张2,两张3,两张4。现在需要排序成一排,要求每张牌号为1的牌中间间隔1张牌,每张牌号为2的牌间隔2张牌,每张牌号为3的牌间隔3张牌,每张牌号为4的牌间隔4张牌,请问有几种放置方案?

例如如下排列不符合规范,因为位置6和位置7放置的两张4中间没有间隔4张牌。

位置1 位置2 位置3 位置4 位置5 位置6 位置7 位置8
1 2 1 3 2 4 4 3

2、分析与陈述

该问题实际想问如何将8个数字进行排列,从而满足特性的间隔要求。

问题输入为8个数字,输出为8个已经排序的数组,操作环节只有排序。

3、问题分解方案1–穷举法

观点:只需按要求将前四个位置,按照牌的摆放要求填满前4位,则如果8个位置都是满的,则符合题目要求。

复杂度:第一个位置可能性8,第二个位置可能性7,则遍历方全部案需要8 * 7 * 6 * 5 ,复杂度为n!,典型NP问题。类似于算法中的TSP 旅行推销商问题

结论:放弃。

4、问题分解方案2–贪心算法

观点:题目可以分解为如何放置4对牌可以填满8个问题。即共有4个子问题:两张1的放置,两张2的放置……。类似于零钱兑换问题。

第一次选择放置两张4,因为4的确定性最高,后续选择可能性也就越少,共有3种放置方案。

第二次放置两张3,每种都是两种放置方案。

……

选择次数:3 * 2 * 2。

结论:41312432、23421314

5、类比

类比观点:每对牌有固定间隔,类似于三维世界的体积;占满8个位置类似于填满固定空间。那么类比于如何将鸡蛋、大枣、沙子和水填满玻璃瓶?

类比方案解法:先放鸡蛋,再放……。方案数量无穷多,因为我可以只旋转杯子。

对应问题观点:方案数量肯定为偶数,因为我可以旋转数组!即方案中4放在位置1和位置3其实没有什么不同。可以对方案进行剪枝。

选择次数:2 * 2 + 2

结论:41312432、23421314

6、结论

共有两种放置方案。

感谢各位提供方案和观点的同学,感谢聪明的妹妹。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部