这道好像是高考题

晚上在群里有人发这道题：

(50.15 KB)

2012-8-14 22:14

印象中是高考题，而且是当时我想选上我那贴子里玩结果玩不来的然后就过了，刚才重新想了下，还是不会……

话说上图这排版真差，好难看，有空找找原版图片。

为了看得更清楚，我还是把题目重新打打。

设 $N=2^n$（$n\in\mathbb N^+$，$n\geqslant2$），将 $N$ 个数 $x_1, x_2, \ldots, x_n$ 依次放入编号为 $1, 2, \ldots, N$ 的 $N$ 个位置，得到排列 $P_0=x_1x_2\cdots x_n$。将该排列中分别位于奇数与偶数位置的数取出，并按原顺序依次放入对应的前 $\frac N2$ 和后 $\frac N2$ 个位置，得到排列 $P_1=x_1x_3\cdots x_{N-1}x_2x_4\cdots x_N$， 将此操作称为 $C$ 变换。将 $P_1$ 分成两段，每段 $\frac N2$ 个数，并对每段作 $C$ 变换，得到 $P_2$；当 $2\leqslant i\leqslant n-2$ 时，将 $P_i$ 分成 $2^i$ 段，每段 $\frac N{2^i}$ 个数，并对每对作 $C$ 变换，得到 $P_{i+1}$。例如，当 $N=8$ 时，$P_2=x_1x_5x_3x_7x_2x_6x_4x_8$，此时 $x_7$ 位于 $P_2$ 中的第 4 个位置。
（1）当 $N=16$ 时，$x_7$ 位于 $P_2$ 中的第________个位置；
（2）当 $N=2^n$（$n\geqslant8$）时，$x_{173}$ 位于 $P_4$ 中的第________个位置。

这个用二进制应该可以搞定

3# 海盗船长


比如判断$7$的位置
把$7$写为二进制：$(111)_{2}$，然后不断将个位抹掉，分组结果就是：第一次左$3$ 第二次右$2$ 。

4# 海盗船长


抹去的哪一位$0$或$1$交替代表分组左还是右，剩下的数代表分组后的排位。

看不懂，明天有心思再理解一下……

皮蛋说：

皮蛋(2770*****)  0:45:52
那个P1，P2啥的
分割一次P1
就是把被2除余1的数都搞到左边一堆（1,3,5，……），右边是是偶数（2,4,6，……）
再分割一次P2，
左1为4m-3（1,5,9，……），左2为4m-1（3,7,11,……）
P3，P4类似
173被4除余1，被8除余5,16除余3
貌似在P4的左3第11个数
皮蛋(2770*****)  0:48:00
是左4的第11个数
在纸上画的，不知道扔哪里去了

我也是用二进制来理解的，还好以前学过点编程