二分查找问题求解我写了一个tle掉了

#2

rjsp2020-11-11 16:48

这个数值好大呀

x^x>10^(n-1)
log(x^x) > n-1
x*log(x) > n-1
能用这种方式把数据缩小吗？

#3

rjsp2020-11-11 16:56

如果可以的话，x 最大值为 123579654，可以二分，或者求导（ x^x的导数 = x^x * (ln(x)+1) )

#4

xiaohuo662020-11-11 17:09

回复 2楼 rjsp

好像就是缩小后二分或者求导,但我tle
掉了

#5

rjsp2020-11-12 10:30

程序代码：

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

unsigned foo( unsigned n )
{
    // x*ln(x) > (n-1)*ln(10)
    // x*ln(x) 的导数是 1 + ln(x)

    double rhs = (n-1)*log(10.);

    unsigned a=1, b=123579654;
    for( ; a+1!=b; )
    {
        unsigned m = (a+b)/2;
        if( m*log(m+0.) > rhs )
            b = m;
        else
            a = m;
    }
    return b;
}

#include <assert.h>

int main( void )
{
    assert( foo(1) == 2 );
    assert( foo(2) == 3 );
    assert( foo(3) == 4 );
    assert( foo(4) == 5 );
    assert( foo(5) == 6 );
    assert( foo(6) == 7 );
    assert( foo(7) == 8 );
    assert( foo(8) == 8 );
    assert( foo(9) == 9 );
    assert( foo(10) == 10 );
    assert( foo(11) == 11 );
    assert( foo(12) == 11 );
    assert( foo(13) == 12 );
    assert( foo(14) == 13 );
    assert( foo(15) == 13 );
    assert( foo(16) == 14 );
    assert( foo(17) == 14 );
    assert( foo(18) == 15 );

    assert( foo(1000000000) == 123579654 );
}

#6

rjsp2020-11-13 09:28

如果用切线法，可以比二分法更快。（n从2到123579654，实测二分法共耗时 157 时间单位, 切线法共耗时 96 时间单位）

程序代码：

unsigned foo( unsigned n )
{
    // x*ln(x) > (n-1)*ln(10)
    // x*ln(x) 的导数是 1 + ln(x)

    const double rhs = (n-1)*log(10.);

    for( unsigned x=1; ; )
    {
        double y = x*log(x+0.) - rhs;

        if( y <= 0 )
        {
            double y2 = (x+1)*log(x+1.) - rhs;
            if( y2 > 0 )
                return x+1;
            x = (unsigned)floor( x+1 - y2/(1+log(x+1.)) );
        }
        else
        {
            double y2 = (x-1)*log(x-1.) - rhs;
            if( y2 <= 0 )
                return x;
            x = (unsigned)floor( x-1 - y2/(1+log(x-1.)) );
        }
    }
    return 0;
}

二分查找问题求解 我写了一个tle掉了