有道理。。。

尝试非暴力求解，但不太满意，先抛砖引玉吧。（用的是C++语言）

#include <stdio.h>

struct foo
{
    bool scale[37]; // 从0到36，是否有刻度
   

    foo()
    {
        // 一开始时第0和第36是等效于有刻度的
        scale[0] = 1;
        for(size_t i=1; i<36; ++i) scale[i]=0;
        scale[36] = 1;
    }

    size_t get_last_cannot() const // 返回最大的那个不能被度量的长度
    {
        bool flags[37] = { 0 };

        for( size_t i=0; i<37; ++i )
        {
            if( scale[i] == 0 )
                continue;

            for( size_t j=i+1; j<37; ++j )
            {
                if( scale[j] == 0 )
                    continue;

                flags[j-i] = true;
            }
        }

        size_t ret;
        for( ret=36; flags[ret]; --ret );
        return ret;
    }
};

void bar( struct foo f, size_t time )
{
    size_t len = f.get_last_cannot();
    if( len == 0 ) // 全部完成
    {
        for( size_t i=1; i<36; ++i )
        {
            if( f.scale[i] )
                printf( "%d ", (int)i );
        }
        printf( "\n" );
        return;
    }
    if( time == 0 ) // 8个刻度用完，失败
        return;

    for( size_t i=0; i<37; ++i )
    {
        if( !f.scale[i] )
            continue;

        if( i+len <= 36 ) // 可以在第i个刻度右侧距离len处增加一个新刻度
        {
            f.scale[ i+len ] = true;
            bar( f, time-1 );
            f.scale[ i+len ] = false;
        }
        if( i >= len ) // 可以在第i个刻度左侧距离len处增加一个新刻度
        {
            f.scale[ i-len ] = true;
            bar( f, time-1 );
            f.scale[ i-len ] = false;
        }
    }
}

int main()
{
    bar( foo(), 8 );
    //1 5 9 16 23 30 33 35 (35 1 33 5 30 9 23 16 )
    //1 3 6 13 20 27 31 35 (35 1 3 31 6 27 13 20 )
    //1 5 9 16 23 30 33 35 (1 35 33 5 30 9 23 16 )
    //1 3 6 13 20 27 31 35 (1 35 3 31 6 27 13 20 )

    return 0;
}

输出有重复，因为一开始可以 先定1再定35，也可以先定35再定1，……

---------------------------------------------------------------

将代码优化一下（算法没变）

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

struct foo
{
    unsigned char scales[10];
    size_t scales_length;
    unsigned long long lens;

    foo()
    {
        scales[0] = 0;
        scales[1] = 36;
        scales_length = 2;

        lens = 1ull<<36;
    }

    foo AppendScale( signed char scale ) const
    {
        foo r = *this;
        r.scales[r.scales_length] = scale;
        for( size_t i=0; i<r.scales_length; ++i )
            r.lens |= 1ull<<abs(r.scales[i]-scale);
        ++r.scales_length;
        return r;
    }

    size_t get_last_cannot_length() const
    {
        size_t len;
        for( len=35; lens&(1ull<<len); --len );
        return len;
    }
};

void bar( struct foo f )
{
    size_t len = f.get_last_cannot_length();
    if( len == 0 )
    {
        for( size_t i=2; i<10; ++i )
            printf( "%d ", (int)f.scales[i] );
        printf( "\n" );
        return;
    }
    if( f.scales_length == 10 )
        return;

    for( size_t i=0; i<f.scales_length; ++i )
    {
        if( f.scales[i]+len <= 36 ) // 可以在第i个刻度右侧距离len处增加一个新刻度
            bar( f.AppendScale(f.scales[i]+len) );

        if( f.scales[i] >= len ) // 可以在第i个刻度左侧距离len处增加一个新刻度
            bar( f.AppendScale(f.scales[i]-len) );
    }
}

int main()
{
    bar( foo() );
    //1 5 9 16 23 30 33 35 (35 1 33 5 30 9 23 16 )
    //1 3 6 13 20 27 31 35 (35 1 3 31 6 27 13 20 )
    //1 5 9 16 23 30 33 35 (1 35 33 5 30 9 23 16 )
    //1 3 6 13 20 27 31 35 (1 35 3 31 6 27 13 20 )

    return 0;
}

[ 本帖最后由 rjsp 于 2013-10-18 15:08 编辑 ]