求一个数列的算法

算法题:
想产生一个数列：T(n) = T(n-1),n,T(n-1)，T(0) = 1
不用递归
比如T(3)是1,2,1,3,1,2,1
T(4)是1,2,1,3,1,2,1,4,1,2,1,3,1,2,1(2^n-1)
------------------------------------------------
我首先分析了一下这个数列，发现
a.T(n)有2^n-1个元素
b.中间的元素值是n，以n为中心，两边的子序列中心元素是n-1，依次类推，最后剩下的都是1
c.下面给出两个方案的c语言伪代码

方案1，对于n不是很大的情况，直接生成整个序列
--------------------内存中要存在的
T(n)=new int[2^n-1];
for(int i=0;i         //i代表值为2^i的值元素,共2^(n-i-1)个,例如i=0代表1的个数，T(3)里面共4个1
        for(int m=0;m<2^(n-i-1);++m){
                T(n)[m*2^i]=2^i;
        }               
}
方案1算法复杂度O(n)*O(2^n)

方案2，对于n比较大的，只能逐个打印元素到屏幕或者一个大文件，因为内存可能不够用
--------------------内存中不存在的
int j=2^n-1;
for(int s=0;s    Tnj=f(s);
   printf(Tnj);
}
int f(int sub){//O(n)
   int i=sub+1;//第i个元素，sub是从0开始的
   if(i>2^n-1)i=(j+1)-i;//对称，所以只考虑前半个序列的规律就可以，后半个序列值对称
   /*
    *分析，如果i最高位是1其他都是0(100)它的值就是n
    *例如T(4)里面第5个元素位置0101，除2不尽，所以值=1
    *    发现1的位置有规律,001，011，101，111，末尾没有0，
    *    2的位置010,110,末尾一个0，3的位置是末尾2个0
    *
    *    位置的个数是n，所以算法复杂度是还是O(2^n)*O(n)
    *    有没有改进的，计算一个整数的2进制表示，后面有几个0
    */
   int return=1;
   while(i%2==0){//这个循环while能否改进?
      ++return;
      i>>1;
   }
}
上述算法的复杂度仍然是O(n)*O(2^n)。我感觉问题主要存在于计算一个整数的2进制表示最后有几个0
->例如第5个元素位置是101，那么末尾是0个0，它的值就是1+0=1
  第6个元素的位置是110,末尾1个0，它的值就是1+1=2

#include <stdio.h>
#include <stdlib.h>

void solve(int n) {
  int s[100], t = 0, i;
  for (i = n; i; s[t++] = i--)
    ;
  while (t) {
    printf("%d ", s[--t]);
    for (i = s[t] - 1; i; s[t++] = i--)
      ;
  }
  printf("\n");
}

int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  solve(n);
  return 0;
}