1

不等式は、nlogn <= a (n は自然数、log は 10 に基づく) です。質問: n の最大値はいくつですか?

私の解決策は、nlogn > a のポイントに到達するまで、n = 1 を無限大にスキャンすることです (ステップ 1)。返される結果は n - 1 になります

しかし、 a が非常に大きい場合、これは効率的ではないことがわかりました。誰かがそれを解決する方法を知っていますか?

4

4 に答える 4

7

私は、comingstorm のソリューションの代数を適切に実行し、実装を行いました。私のマシンでは、ニュートンの方法は二分探索よりも 4 倍優れていnewton()ます。すべての非負の 32 ビット整数でテストしました。

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <time.h>

static int newton(double a) {
    if (a < 2.0 * log10(2.0)) {
        return 1;
    } else if (a < 3.0 * log10(3.0)) {
        return 2;
    }
    double a_log_10 = a * log(10);
    double x = a / log10(a);
    x = (x + a_log_10) / (1.0 + log(x));
    x = (x + a_log_10) / (1.0 + log(x));
    double n = floor(x);
    if (n * log10(n) > a) {
        n--;
    } else if ((n + 1.0) * log10(n + 1.0) <= a) {
        n++;
    }
    return n;
}

static int binarysearch(double a) {
    double l = floor(a / log10(a));
    double u = floor(a) + 1.0;
    while (1) {
        double m = floor((l + u) / 2.0);
        if (m == l) break;
        if (m * log10(m) > a) {
            u = m;
        } else {
            l = m;
        }
    }
    return l;
}

static void benchmark(const char *name, int (*solve)(double)) {
    clock_t start = clock();
    for (int a = 1 << 22; a >= 10; a--) {
        int n = solve(a);
        assert(n * log10(n) <= a);
        assert((n + 1) * log10(n + 1) > a);
    }
    printf("%s: %.2f\n", name, (clock() - start) / (double)CLOCKS_PER_SEC);
}

int main(int argc, char *argv[]) {
    benchmark("newton", newton);
    benchmark("binarysearch", binarysearch);
}
于 2011-09-17T14:44:15.730 に答える
5

二分探索でやってください。開始間隔は (1,a) または (sqrt(a),a) です。

于 2011-09-17T14:14:13.770 に答える
1

方程式 nlogn = a を解くと、比較を行うたびにその計算を実行する必要がなくなります。方程式は超越方程式であるため、一定時間反復すると、かなり適切な近似である結果が得られます。次に、データに対してバイナリ検索を実行します。

procedure solve_transcendental
   n = 50
   for i = 1 .. 20
      n = a / log(n)
   end
end
于 2011-09-17T14:19:56.710 に答える
0

二分探索は信頼できる良い答えです。このような方程式を解く別の方法は、それらを x=f(x) として書き直してから、f(x)、f(f(x))、f(f(f(x))) などを計算することです。結果が収束することを願っています。|f'(x)|の場合、これには希望があります。< 1. n log n = a を n = a / log n として書き換えると、実際には驚くほどうまく機能するようです。

于 2011-09-17T14:25:21.727 に答える