求九连环的解法

百度百科上有：
http://baike.baidu.com/view/27263.htm
其实很简单的。

道理都是一样的。卸9个环和卸5个环方法一样。只是步数多了而已。每增加一个环，步数增加1倍。

九连环步骤计算
九连环是中国民间玩具。规定环在杆上用1表示，环在下面用0表示。规定最左边的环是可以任意上下的那一环，输出数据中最右边必须是1，也就是说，010100要写成0101。
现在是X连环,由于“输出数据中最右边必须是1” ，所以X可以理解为无限大，右边多余的0在输出时都省略。初始化各环都是0，以下是前9步的情况：
1 1
2 11
3 01
4 011
5 111
6 101
7 001
8 0011
9 1011
问在X连环装上过程中，第n步完成后，具体情况是怎么样的。

答案：将n转化为二进制，求其格雷码。将二进制的格雷码逆序输出，即得具体情况。
注意：这个算法揭示了传统的九连环与现代的格雷码的重要关系！

程序实现（C语言）：
#include<stdio.h>
main()
{ __int64 n;
int a[70]=,num=0,i;
scanf("%I64d",&n);
if(n==0)
{ printf("0");
return 0;
}
while(n>0)
{ a[num++]=n%2;
n/=2;
}
for(i=0;i<num;i++)
a=a^a[i+1];
while(a[num]==0)
num--;
for(i=0;i<=num;i++)
printf("%d