由于下面3个序列存在一一对应的关系
1.{{}(空集), { 1 }, { 3 }, { 1, 3 }, { 9 }, { 1, 9 }, { 3, 9 }, { 1, 3, 9 }, ...}
2.{{}(空集), { 1 }, { 2 }, { 1, 2 }, { 4 }, { 1, 4 }, { 2, 4 }, { 1, 2, 4 }, ...}
3.{   0,       1,     2,       3,      4,       5,        6          7       ...}

且第2个序列中每个集合的元素和等于第3个序列中相对应的元素

所以只需将n减去1然后再转成2进制，然后再把2换成3就能得到相对应的集合

先转成16进制，然后使用数组做对应；

typedef long long INT64；
    
void HeroNeedThree( INT64* subset, unsigned int n )
{
    int i, j;
    int stack[8];//存放3的次数的栈
    static int cishu[16][5] = {{0, 0, 0, 0, 0}, {1, 0, 0, 0, 0}, {1, 1, 0, 0, 0}, 
        {2, 1, 0, 0, 0}, {1, 2, 0, 0, 0}, {2, 2, 0, 0, 0}, {2, 2, 1, 0, 0}, 
        {3, 2, 1, 0, 0}, {1, 3, 0, 0, 0}, {2, 3, 0, 0, 0}, {2, 3, 1, 0, 0}, 
        {3, 3, 1, 0, 0}, {2, 3, 2, 0, 0}, {3, 3, 2, 0, 0}, {3, 3, 2, 1, 0}, 
        {4, 3, 2, 1, 0}};//这个2维数组把0到15转换成相对应的2的次数，
                         //每个1维数组的首元素为存储的次数的个数

    static INT64 mi_3[32] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 
        59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 
        387420489, 1162261467, 3486784401, 10460353203LL, 31381059609LL, 94143178827LL, 
        282429536481LL, 847288609443LL, 2541865828329LL, 7625597484987LL, 
        22876792454961LL, 68630377364883LL, 205891132094649LL, 617673396283947LL};
    //存放3的幂
    
    for ( i = 0, --n; n != 0; ++i )
    {
        stack[i] = n & 15;
        n >>= 4;
    }//入栈
    for ( --i, subset[0] = 0; i >= 0; --i )
    {
        for ( j = 1; j <= cishu[stack[i]][0]; ++j )
        {
            subset[++subset[0]] = mi_3[cishu[stack[i]][j] + 4 * i];
        }
    }//出栈并通过数组mi_3将次数转换为对应的数值
    return;
}

昨天上网刚看到题目，这几天忙着备课与教学评估，累啊，觉得是概率与统计的应用，没时间写了，来凑个热闹，增添点人气（虽然人气已十分旺盛）。

//dev-c++编译
#define TMAX 32                    //3的最大指数为32 
typedef long long INT64;

static unsigned int S[TMAX+1];    
static INT64 BASE[TMAX+1];        //{1,3,9....}
static int initialized=0;

int indexsearch(unsigned int n)
{
    for(int i=1; i<=TMAX; i++)
    {
        if(n<=S[i])
            return i;    
    }
    return 0;
}

int initial()
{
    BASE[0]=0LL;
    BASE[1]=1LL;
    S[0]=0UL;
    S[1]=1UL;
    for(int i=1; i<=TMAX-1; i++)
    {
        BASE[i+1]=BASE[i]*3;
        S[i+1]=S[i]*2+1;    
    }    
    return 1;
}

void HeroNeedThree(INT64 *subset, unsigned int n)
{
    int current=0;
    unsigned int num=n-1;
    subset[0]=0LL;
    
    if(!initialized)
        initialized=initial();
    
    if(n>1)
    {
        int index=indexsearch(num);
        subset[++current]=BASE[index];
        subset[0]++;
        while(1)
        {
            num=num-S[index-1]-1;
            if(!num)    break;
            index=indexsearch(num);
            subset[++current]=BASE[index];
            subset[0]++;        
        }
    }    
}

如果每个数都往前错一位的话 那么 2的N次方个 必定是一个独数~~
所以说第N个 必定是N 减去离N最近的一个 2的幂 本想用递归的  
typedef long long INT64;
inline int power(int,unsigned int);
int power(int x,unsigned int n)
{
    if(n==0)
    return 1;
    else if(n%2==0)
    return power(x*x,n/2);
    else
    return x*power(x*x,n/2);
}
void HeroNeedThree(INT64* subset, unsigned int n)
{

 assert(n>0);
 if(n==1)
  {subset[0]=0;}
 n=n-1;
 int i=1;
 int d=0;
 int result=0;
 unsigned int c=0;
while((n-result)==0)
c=int(log(n)/log(2));
if(n==power(2,c))
  {
   d=power(3,c);
   subset[i]=d;
   ++i;
  }
int a=0;
for(int b=power(2,a);b<=n;a++){}
result=power(3,a);
subset[i]=result;
++i;
subset[0]=i;

}

#include<Cmath>

void HeroNeedThree(INT64 * subset, unsigned int n){
    int i=30;
    int k=0;
    do{
        if(n<(1<<i))
            i--;
        else if(n>(1<<i)){
            subset[++k]=pow(3,i);
            n=n-(1<<i);
            i--;
        }
        else{
            if(n!=1){
                for(int j=i-1;j>=0;j--){
                    subset[++k]=pow(3,j);
                }
            }
            break;
        }
    }while(n!=0);
    subset[0]=k;
}

#include <stdio.h>

void HeroNeedThree(__int64 *subset, unsigned long n)
{
    register int count = 0;
    __int64 sum = 1;

    while (n)
    {
        if (n % 2)
        {
            subset[count++] = sum;
        }
        n /= 2;
        sum *= 3;
    }
    printf("{");
    while (count--)
    {
        if (count)
            printf(" %I64d,", subset[count]);
        else
            printf(" %I64d", subset[count]);
    }
    printf(" }\n");
}

int main(void)
{
    __int64 subset[64];
    unsigned long n;

    while (scanf("%d", &n) , n < 1);
    HeroNeedThree(subset, n - 1);
    return 0;
}

/*
The ternary form of any sum is composed of digits 0 and 1 only. By assuming radix 2 for the ternary form, a one-to-one correspondence from each sum to its ordinal number can be constructed. There comes the solution.
*/

void HeroNeedThree(INT64* subset, unsigned int n)
{
    INT64 x = 1;
    int c = 0, i, j;
    while(n != 0)
    {
        if(n & 1)
        {
            subset[++c] = x;
        }
        x *= 3;
        n >>= 1;
    }
    subset[0] = c;
    for(i = 1, j = c; i < j; i++, j--)
    {
        INT64 t = subset[i];
        subset[i] = subset[j];
        subset[j] = t;
    }
};