17

我想找到小于或等于 n 的第 k 个根的最大整数。我试过

int(n**(1/k))

但是对于 n=125, k=3 这给出了错误的答案！我碰巧知道 5 的立方是 125。

>>> int(125**(1/3))
4

有什么更好的算法？

背景：在 2011 年，这个失误让我击败了 Google Code Jam 问题昂贵的晚餐。

4

11 回答 11

15

怎么样：

def nth_root(val, n):
    ret = int(val**(1./n))
    return ret + 1 if (ret + 1) ** n == val else ret

print nth_root(124, 3)
print nth_root(125, 3)
print nth_root(126, 3)
print nth_root(1, 100)

在这里，两者val和n都应该是整数和正数。这使得return表达式完全依赖整数运算，消除了任何舍入错误的可能性。

val**(1./n)请注意，只有在相当小的情况下才能保证准确性。一旦该表达式的结果与真实答案的偏差超过1，该方法将不再给出正确答案（它将给出与原始版本相同的近似答案）。

我仍然想知道int(125**(1/3))为什么4

In [1]: '%.20f' % 125**(1./3)
Out[1]: '4.99999999999999911182'

int()将其截断为4.

于 2013-04-12T18:57:00.673 回答
15

一种解决方案首先通过重复将 hi 乘以 2 直到 n 介于 lo 和 hi 之间，将 lo 和 hi 之间的答案括起来，然后使用二进制搜索来计算确切的答案：

def iroot(k, n):
    hi = 1
    while pow(hi, k) < n:
        hi *= 2
    lo = hi // 2
    while hi - lo > 1:
        mid = (lo + hi) // 2
        midToK = pow(mid, k)
        if midToK < n:
            lo = mid
        elif n < midToK:
            hi = mid
        else:
            return mid
    if pow(hi, k) == n:
        return hi
    else:
        return lo

一个不同的解决方案使用牛顿法，它对整数非常有效：

def iroot(k, n):
    u, s = n, n+1
    while u < s:
        s = u
        t = (k-1) * s + n // pow(s, k-1)
        u = t // k
    return s
于 2013-04-12T20:04:46.107 回答
4

我被严重烧伤后的谨慎解决方案：

def nth_root(N,k):
    """Return greatest integer x such that x**k <= N"""
    x = int(N**(1/k))      
    while (x+1)**k <= N:
        x += 1
    while x**k > N:
        x -= 1
    return x
于 2013-04-12T19:27:24.363 回答
3

为什么不试试这个：

125 ** (1 / float(3))

或者

pow(125, 1 / float(3))

它返回 5.0，因此您可以使用 int() 转换为 int。

于 2015-03-30T06:39:11.507 回答
1

这是在 Lua 中使用 Newton-Raphson 方法

> function nthroot (x, n) local r = 1; for i = 1, 16 do r = (((n - 1) * r) + x / (r ^ (n -   1))) / n end return r end
> return nthroot(125,3)
5
>

蟒蛇版本

>>> def nthroot (x, n):
...     r = 1
...     for i in range(16):
...             r = (((n - 1) * r) + x / (r ** (n - 1))) / n
...     return r
... 
>>> nthroot(125,3)
5
>>>
于 2013-04-12T19:14:04.623 回答
1

我想知道从基于对数的方法开始是否可以帮助确定舍入误差的来源。例如：

import math
def power_floor(n, k):
    return int(math.exp(1.0 / k * math.log(n)))

def nth_root(val, n):
    ret = int(val**(1./n))
    return ret + 1 if (ret + 1) ** n == val else ret

cases = [
    (124, 3),
    (125, 3),
    (126, 3),
    (1, 100),
    ]


for n, k in cases:
    print "{0:d} vs {1:d}".format(nth_root(n, k), power_floor(n, k))

打印出来

4 vs 4
5 vs 5
5 vs 5
1 vs 1
于 2013-04-12T19:34:27.313 回答
1 
def nth_root(n, k):
    x = n**(1./k)
    y = int(x)
    return y + 1 if y != x else y
于 2013-04-12T19:59:33.487 回答
0

int(125**(1/3))显然应该是 5，即正确答案，所以这必须是标准的计算机舍入误差，即内部结果是 4.9999999999，它被舍入为 4。无论您使用什么算法，都会存在这个问题。一个简单的临时解决方案是添加一个很小的数字，例如int((125**(1/3)) + 0.00000001)

于 2013-04-12T19:03:31.883 回答
0

您可以四舍五入到最接近的整数，而不是将 / 向下舍入为零（我不知道 Python 指定了什么）：

def rtn (x):
    return int (x + 0.5)

>>> rtn (125 ** (1/3))
5
于 2013-04-12T19:06:29.410 回答
0

在一切之前这样做：

from __future__ import division

然后运行任何上述指定的技术来得到你的结果。

于 2013-04-12T19:19:49.197 回答
0 
def nthrootofm(a,n):
    a= pow(a,(1/n))
    return 'rounded:{},'.format(round(a))
a=125
n=3
q=nthrootofm(a,n)
print(q)

刚刚使用了格式字符串，也许这有帮助。

于 2018-08-01T09:46:47.900 回答