题目:

一副从1到n的牌,每次从牌堆顶取一张放桌子上,再取一张放牌堆底,直到手里没有牌.最后桌子上的牌是从1到n有序,设计程序,输入n,输出牌堆的顺序数组

这里有介绍两种方式解题
1.第一种方式,通过逆向推倒, 从桌子上拿起排好序的牌.当手里没有牌时,从桌子上拿起第一张牌放到手里.当手里已经有牌之后,拿起桌子上的牌放到手里牌的最上面,将手里最底下的牌放到从上面数的第二张.

for (int i = 0; i < n; i ++) {

    if (i == 0) {
        array[n - 1 ] = n;
    }else{
        // 将新的牌插入到最上面
        array[n - i - 1] = n - i;
        // 记录最后一张牌的值
        int last = array[n - 1];
        // 新牌后面所有的牌向后移动一位
        for (int j = n - 1; j > n - i ; j --) {
            array[j] = array[j - 1];
        }
        // 将原来的最后一张牌放到新牌的后面
        array[n - i] = last;
    }
}

for (int i = 0; i < n; i ++) {
    printf("%d\n",array[i]);
}

2.第二种方式,是先将1...n的牌顺序排列,然后按照题目中描述的步骤重新排列.将得到的牌面上的数字,替换成该数字的索引对应的牌面数字,最终得到的顺序就是题目要求的结果.

for (int i = 0; i < n; i ++) {
    // 将堆顶的牌放到result顶
    result[i] = source[i];
    // 记录第二位的牌
    int second = source[i + 1];
    for (int j = i + 1; j < n - 1; j ++) {
        source[j] = source[j + 1];
    }
    source[n - 1] = second;
}
for (int i = 0; i < n; i ++) {
    printf("%d\n",result[i]);
}
printf("------替换后-----\n");
// 将牌面数字作为map的key,将索引作为value,将key顺序排列,
//得到的value的序列就是要求的结果
//这里直接用循环来查找了
for (int i = 1; i <= n; i ++) {
    for (int j = 0; j < n; j ++) {
        if (result[j] == i) {
            printf("%d\n",j + 1);
            break;
        }
    }
}

第一种逆向推到的方法略去不表,只看第二种正序推到后,再按索引替换,为什么得到的就是想要的结果呢?
假设n=6,按照题目描述的步骤排序后得到的顺序是135264
但是题目上说的是放到桌子上之后的顺序是123456,而现在牌面顺序是135264.现在假设牌的背面都写上的目前对应的索引.

现在我们不管最初牌堆里的123456是怎么排成现在的156342的,只是把牌的正面重新排列成123456.然后把牌背面朝上,看到的背面的顺序就是我们要求的结果.

第二种方式的好处是,完全可逆,不用倒着推.换成更复杂的步骤,这样替换索引仍然是可行的.
此文题目和解题思路源自https://www.jianshu.com/p/fa3abe4e2531