魔术师发牌问题的常规解法和倒序解法（C++）

问题描述：

魔术师手中有A、2、3……J、Q、K十三张黑桃扑克牌。在表演魔术前，魔术师已经将他们按照一定的顺序叠放好（有花色的一面朝下）。魔术表演过程为：一开始，魔术师数1，然后把最上面的那张牌翻过来，是黑桃A；然后将其放到桌面上；第二次,魔术师数1、2；将第一张牌放到这些牌的最下面，将第二张牌翻转过来，正好是黑桃2；第三次，魔术师数1、2、3；将第1、2张牌依次放到这些牌的最下面，将第三张牌翻过来正好是黑桃3；……直到将所有的牌都翻出来为止。问原来牌的顺序是如何的。

常规解法：

先构造一个循环链表，将数据全部置为0，然后填数。当某个位置被填过后，就变成了非0数，因此在每次填数前增加一个判断，如果非零，就跳过。

#include<iostream> using namespace std; struct poke { int num; struct poke *next; }; int main() { struct poke *head = new struct poke; struct poke *op = head; // 制作全为0的循环链表 for (int i = 0; i < 13; i++) { op->num = 0; if (i == 12) { op->next = head; } else { op->next = new struct poke; op = op->next; } } // 循环结束以后，此时指针位于最后一个链表的位置 for (int i = 1; i <= 13; i++) { for (int j = 0; j < i; j++) { op = op->next; if (op->num != 0) { j--; } } op->num = i; } op = head; for (int i = 0; i < 13; i++) { cout << op->num << " "; op = op->next; } cout << endl; // 释放堆区 op = head; struct poke *temp = NULL; for (int i = 0; i < 13; i++) { temp = op; op = op->next; delete temp; } return 0; }

运行结果

倒序解法：

本人在思考这个问题时最先想到的就是倒序解法。其本质就是把问题反过来解决，可以描述为：手里没有牌，然后增加K，经过12次把牌底的牌放到牌顶，在牌顶增加Q；经过11次把牌底的牌放到牌顶，在牌顶增加J……经过1次把牌底的牌放到牌顶，在牌顶增加1。

#include<iostream> using namespace std; struct poke { int num; struct poke *last; }; int main() { struct poke *tail = new struct poke; // 首尾相接形成循环链表 tail->last = tail; tail->num = 13; struct poke *op = tail; struct poke *temp = NULL; for (int i = 12; i > 0; i--){ temp = op->last; op->last = new struct poke; op->last->num = i; op->last->last = temp; // 指针指向牌顶 op = op->last; for (int j = 0; j < (i - 1); j++){ op = op->last; } } op = op->last; // 由于链表是倒序的，也需要倒序打印 for (int i = 0; i < 13; i++){ for (int j = 0; j < 12; j++) { op = op->last; } cout << op->num << " "; } cout << endl; // 释放堆区 op = tail; temp = NULL; for (int i = 0; i < 13; i++) { temp = op; op = op->last; delete temp; } return 0; }

运行结果