一道趣题

---

    一道趣题
    作者：tyc611.cublog.cn，2008-10-03

---

【问题描述】
写一个函数，传入一个参数n，输出序列seq(n) = seq(n-1),n,seq(n-1)。例如，当n=3时，输出：1,2,1,3,1,2,1。

【问题分析】
最直接最简单的解答显然是递归实现，但考虑到函数调用栈深受系统限制，因此可以采用模拟栈的方式。空间复杂度为O(n)，时间复杂度为O(2^n)。

下面介绍一种更有趣的解答。
这个解法最多只能算n = 31，不然就要溢出了。时间复杂度为O(2^n)*O(logn)，空间复杂度为O(1)。

对于输出序列，如果按输出顺序对每个输出的数依次编号（1，2，3，……），那么对于第k个元素：一定能够找到一个m，使得2^m - 1 < k <= 2^(m+1) - 1（注：2^m - 1为n=m的输出元素个数）。如果刚好有k = 2^m，那么输出m+1即可；否则，令k -= 2^m，继续寻找新的m。

用数的二进制表示来考虑此过程，相当于要找数k的最右1位的位置，比如k = 5 = 101B，那么最右1位的位置为1，则输出1，又如k = 16 = 10000B，则输出5

实现代码如下：
#include

int Pow2(int n)
{
    /* return k = 2 ^ n */
    int k = 1;
    for (; n > 0; --n)
        k *= 2;
    return k;
}

int Log2(int n)
{
    /* n = 2 ^ k, return k */
    int k = 0;
    for (; n > 1; n >>= 1)
        ++k;
    return k;
}

void PrintSeq(int n)
{
    int i, k;
   
    if (n >= sizeof(int) * 8) {
        printf("overflow\n");
        return;
    }
   
    k = Pow2(n) - 1;
    for (i = 1; i <= k; ++i)
        printf("%d ", Log2(i & (-i)) + 1);
}

int main ()
{
    PrintSeq(6);
   
    return 0;
}

程序运行结果：
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

---