R阶差数列

这题源自ULM 1997吧，算法应该是DFS，让我想想，稍后给出代码～～～

[quote]
题目是前天 省加试赛的题(没办法, 省里人太多了OTL)

某数列a, a(1)=1, 对于任意一个n, 都能找到i, j使得a(i)+a(j)=a(n).[color=red] (1<=i<=j<=n)[/color]
已知a(n)的值, 请构造一个数列, 使n的值尽量小.(实际输出时只须输出n)
[/quote]
貌似题目有点问题,这里的[color=red]1<=i<=j<=n[/color]应该改成[color=green]1<=i<=j<n[/color]吧.

#include <stdio.h>
#include <math.h>

unsigned int func( unsigned int x )
{
    x = ( x & 0x55555555UL ) + ( ( x >> 1) & 0x55555555UL );
    x = ( x & 0x33333333UL ) + ( ( x >> 2 ) & 0x33333333UL );
    x = ( x & 0x0f0f0f0fUL ) + ( ( x >> 4 ) & 0x0f0f0f0fUL );
    x = ( x & 0x00ff00ffUL ) + ( ( x >> 8 ) & 0x00ff00ffUL );
    x = ( x & 0x0000ffffUL ) + ( ( x >> 16 ) & 0x0000ffffUL );
    return x;
}

int main( void )
{
    unsigned int x;
    while ( EOF != scanf( "%u", &x ) )
    {
        printf( "%u\n", ( unsigned int )log2( x ) + func( x ) );
    }
    return 0;
}

楼上的有问题,比如15,楼上的要7次,事实上6次就足够了:
1   2   3   6   12   15

哦,对,再想想

#include<stdio.h>
int main()
{
    int a,n;
    while(scanf("%d",&a)!=EOF)
    {
        n=1;
        while(a!=1)
        {
            if(a&1)
            {
                if(a%3) a/=2,n+=2;
                else a/=3,n+=2;
            }
            else n++,a/=2;
        }
        printf("%d\n",n);
    }
    return 0;
}

如果是个偶数,应该多一个元素,如果是个奇数就必须多两个元素.但是两种情况下都只要扩展一个元素就可以了.
LZ看看我上面的对不