1

不等式是：nlogn <= a（n 是自然数，log 基于 10）。问题：n 可能的最大值是多少？

我的解决方案是将 n = 1 扫描到无穷大（步骤 1），直到到达 nlogn > a 的点。返回的结果将是 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 回答