找到最大的x^y小于数字

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

X ^Ÿ< = A X^Y小的最大数量是最大

加X和Y不能是十进制数，只有 “整数”

例如：

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

等

编辑： 由于izomorphius在评论中提出，它将始终解决x = A和y = 1的问题。但那不是理想的结果。我希望x和y尽可能地接近数字，因为它可以。

来源

2012-11-14 Martin Perry

请添加更多的语句。很显然，如果y = 1，您总是有选项x = A和y = 1。 –

另外，“最小的x和y”是什么意思？这不是一个数学表述。 – Jon

x和y是整数，还是可以浮动？ –

幼稚解决方案可以是：

做a^y对于某一常数a“最接近但不高于”编号，以A为：

a^{floor(log_a(A))} [其中log_a(A)是用碱A的a对数，在大多数编程语言中可以计算为log(A)/log(a)]

通过遍历范围[2,A)中的所有a s，您可以找到该数字。

该解决方案是O(A * f(A))其中f(A)是你的POW /日志复杂

附：如果你希望你的指数（y）更大然后1，你可以简单地重复范围内[2,sqrt(A)] - 它的时间复杂度降低到O(sqrt(A) * f(A)) - 并让你只用数字的指数更大然后1.

来源

2012-11-14 13:10:05 amit

谢谢......多数民众赞成在为我工作后，一些调整:) –

这种解决方案是非常天真。 –

这是不清楚你在问什么，但我会尝试猜测。

我们首先为实数z解出方程z^z = a。令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-14 13:56:03

但是，这不符合'A = 33 => x^y = 2^5'。然而，如何解决最大化'x^y'和最小化'| x - y |'之间的可能冲突并未被指定。 –

事实上，它没有被指定，并且由于我无法读懂头脑，所以我做了这样的事情，以便“x”和“y”之间的差别总是最大为1.我相信还有其他的解读。 –

找到最大的x^y小于数字

回答

相关问题