抽牌游戏的分析

• 问题描述：

有十三张牌, 将最上面的抽出来放在最下面,之后将最上面的牌抽走, 若抽走的顺序是 1 2 3 4 5 6 7 8 9 10 11 12 13 问原始的顺序是什么?

• 分析：

本问题有两种解题思路：

（1）从生成结果数列的特征进行分析： 不易发现得到的结果数列在刚开始时是原数列的偶数位置上的子序列，也就是说每隔一个数取一个数。如，原数列为X 1 Y 2 Z 3 ...，那么得到的数列的前面几个数是1 2 3 ...。 于是，想到的解题方法基本思想是逐步插入结果序列到原序列中（初始为空），从而生成原序列。插入方法为：从插入位置应该从第二个空们开始，然后每隔一个空 位插入一个数字。具体实现时，若用数组存储，则这个问题相当于把一个序列插入到一个同维的数组中，插入方法是：从数组中第二个位置开始插入，然后每隔一个 空位插入一次；当遇到数组尾时折回到数组首。如此进行下去，直到把结果序列依次都插入到数组中（算法关键在寻找插入点上，有多种实现方法，后面程序中用到 一种）。

（2）从执行动作的特征进行分析： 把由原数列生成结果数列的过程进行逆运算，即可找到由结果数列还原到原数列的方法。具体而言，就是把结果数列的元素从后往前依次插入到生成数列中，最后得 到原数列。设初始生成序列为空，然后重复如下过程，直到把结果序列中的所有元素以逆序（从后往前）插入到生成序列中，其中插入规则如下： > 把当前要插入的元素插入到生成序列的最前面，然后把生成序列的最后一个元素放到生成序列的最前面（其实就是原过程的逆过程）。 在具体实现时，若用数组存放，则第一个插入点应选在倒数第二个位置，这样，当插入结束时，得到的数组刚好就把原数列（原因在于，生成序列的最后一个元素的 位置每次都将向前移动一个位置，所以要使其最后一次移动后的位置在数组的最后一个位置，应使其初始位置在倒数第二个位置）。

• 扩展：

本问题抽象成一般的问题，可以得到两类子问题：

（1）由一个数列通过一定抽取规则得到新的数列（如原题和解法二），这种题用队列来解就非常直观，能直接反映抽取过程；

（2）将一个数列按照一定规则依次插入一个数组中（可以是其它数据结构），如解法一（其规则是：从第二位置开始，每隔一个空位插入一个元素；当遇到数组尾时折回到数组首，直到把所有元素都插入到所有空位中）。

• 用C++实现如下：

#include <iostream>
#include <ctime>

using namespace std;

bool GetSeq1(int X[], int Y[], int num)
{
if (num < 0)
return false;
else if (num == 1) {
Y[0] = X[0];
return true;
}

// num >= 2
int curPos = (num - 3 + num) % num; //指向当前可插入点
int last = (num - 2 + num) % num; //指向当前生成序列的最后一个元素
Y[num - 2] = X[num - 1]; //初始生成序列为{Xn}
for (int i = num - 2; i >= 0; --i) {
Y[curPos] = X[i]; //插入
curPos = (curPos -1 + num) % num;
Y[curPos] = Y[last]; //调整
curPos = (curPos -1 + num) % num;
last = (last -1 + num) % num;
}

return true;
}

bool GetSeq2(int X[], int Y[], int num)
{
if (num < 0)
return false;
else if (num == 1) {
Y[0] = X[0];
return true;
}

// num >= 2
int curPos = 1; //指向当前可插入点
int first = 0; //指向当前数组中第一个空位
int step = 2; //步长
for (int i = 0; i < num; ++i) {
Y[curPos] = X[i]; //插入
//查找下一个位置
curPos += step; //步进
if (curPos > num - 1) { //越界
curPos -= num;
if (first + step > num - 1) //只剩下一个元素
curPos = first; //唯一空位
else if (curPos > first)
curPos = first + step;
else { //true: curPos <= first
curPos = first;
first += step;
}
step *= 2;
}//if
}//for


return true;
}

int main()
{
const int NUM = 5000;
int X[NUM]; //结果序列
int i;
for (i = 0; i < NUM; ++i)
X[i] = i + 1;

int Y[NUM]; // 原序列
int Z[NUM]; // 原序列

clock_t startTime = clock();
for (int size = 4; size <= NUM; ++size) {
GetSeq1(X, Y, size);
GetSeq2(X, Z, size);
// compare Y and Z
for (i = 0; i < size; ++i) {
if (Y[i] != Z[i]) {
cout<<"Error: size = "<<size<<endl;
return 1;
}
}
}
clock_t endTime = clock();

cout<<"Time elapsed: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" seconds"<<endl;

return 0;
}