0

我有数字 A（从数字 0、1、2、3 构建）。我想找到最小的 x 和 y，如果我这样做 x^yi 得到的最大数字小于 A

x^y <= A x^y 是最大的

加 x 和 y 不能是十进制数，只能是“整数”

例如：

A = 7 => x^y = 2^2
A = 28 => x^y = 3^3
A = 33 => x^y = 2^5

ETC

编辑： 正如 izomorphius 在评论中建议的那样，它总是有 x = A 和 y = 1 的解决方案。但这不是理想的结果。我希望 x 和 y 尽可能接近数字。

4

2 回答 2

2

一个天真的解决方案可能是：

a^y通过做一些常数，与 A 的“最接近但不更高”的数字a是：

afloor(log_a(A))[哪里log_a(A)是底的对数a，A可以像log(A)/log(a)大多数编程语言一样计算]

通过迭代a范围内的所有 s，[2,A)您可以找到这个数字。

这个解决方案是你的 pow/log 复杂性O(A * f(A))在哪里f(A)

PS如果您希望您y的[2,sqrt(A)]指数O(sqrt(A) * f(A))（

于 2012-11-14T13:10:05.437 回答
1

目前尚不清楚您在问什么，但我会尝试猜测。

我们首先求解z^z = a一个实数的方程z。让u和v分别z向下和向上四舍五入。在这三个候选(u,u)中(v,u)，(u,v)我们选择最大的不超过一个a。

示例：考虑案例a = 2000。我们z^z = 2000通过数值方法（见下文）求解以获得近似解z = 4.8278228255818725。我们向下取整以获得u = 4和v = 5。我们现在有三个候选人4^4 = 256，4^5 = 1023和5^4 = 625。它们都小于2000，因此我们采用给出最大答案的那个，即x = 4，y = 5。

这是Python代码。该功能solve_approx可以满足您的需求。它适用于a >= 3. 我相信您可以独自应对这些a = 1案件a = 2。

import math

def solve(a):
    """"Solve the equation x^x = a using Newton's method"""
    x = math.log(a) / math.log(math.log(a)) # Initial estimate
    while abs (x ** x - a) > 0.1:
        x = x - (x ** x - a) / (x ** x * (1 + math.log(x)))
    return x

def solve_approx(a):
    """"Find two integer numbers x and y such that x^y is smaller than
    a but as close to it as possible, and try to make x and y as equal
    as possible."""
    # First we solve exactly to find z such that z^z = a
    z = solve(a)
    # We round z up and down
    u = math.floor(z)
    v = math.ceil(z)
    # We now have three possible candidates to choose from:
    # u ** zdwon, v ** u, u ** v
    candidates = [(u, u), (v, u), (u, v)]
    # We filter out those that are too big:
    candidates = [(x,y) for (x,y) in candidates if x ** y <= a]
    # And we select the one that gives the largest result
    candidates.sort(key=(lambda key: key[0] ** key[1]))
    return candidates[-1]

这是一个小演示：

 >>> solve_approx(5)
 solve_approx(5)
 (2, 2)
 >>> solve_approx(100)
 solve_approx(100)
 (3, 4)
 >>> solve_approx(200)
 solve_approx(200)
 (3, 4)
 >>> solve_approx(1000)
 solve_approx(1000)
 (5, 4)
 >>> solve_approx(1000000)
 solve_approx(1000000)
 (7, 7)
于 2012-11-14T13:56:03.040 回答