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、結論
共有兩種放置方案，
感謝各位提供方案和觀點的同學，感謝聰明的妹妹，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256874.html
標籤：其他