一道算法题

看到一道有意思的题目，在这里记录一下：

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

看到这个题目的时候自己思考了一下 然后给出了一种解法，
其实题目中排列可以理解为一层递归，对于1-n，那么开始填数的时候不考虑相隔的那一个位置 第一趟就应该填1 2 3 4…..
但是相隔的那一个位置该怎么填呢，把这个位置出来，其实问题就变成了一个新的子问题，给定有有序序列s~e按照题目的规则填数，然后需要注意一点的就是因为每一趟都会把牌掉转方向一遍 所以在填数的时候要记录每一层填的方向，另外还有一个问题就是当填的方向不是正向的时候并且这一层以及后面的层需要处理偶数个数，那么这里第一次填的数不是自己，看看代码吧：

#include <iostream>
#include<vector>
using namespace std;
class InsertNumber {
public:
    int nowNumber;
    int dir;
    InsertNumber* sub;
    bool isSelf;
    void Init(int s, int e, int _dir)
    {
        if (s>e) {
            sub = NULL;
            return;
        }
        int count = e - s + 1;
        dir = _dir;
        if (dir<0 && (count & 1) == 0)isSelf = false;
        else isSelf = true;
        if (dir == -1)nowNumber = s + (count - 1) / 2;
        else nowNumber = s;
        //isSelf = true;

        sub = new InsertNumber();

        sub->Init(s + (count + 1) / 2, e, -_dir);
    }
    void Insert(vector<int>&arr) {
        if (sub == NULL)return;
        if (isSelf) {
            arr.push_back(nowNumber);
            nowNumber += dir;
        }
        else {
            sub->Insert(arr);
        }

        isSelf = !isSelf;
    }
};

int main() {
    int n = 8;
    InsertNumber num;
    num.Init(1, n, 1);
    vector<int>ans;
    for (int i = 0; i<n; i++)num.Insert(ans);
    for (int i = 0; i<ans.size(); i++)cout << ans[i] << " ";
    return 0;
}

后来在牛客上看到一位微软大佬的回答：

我等膜拜，这个解法确实很巧妙