我想找到小于或等于n的第k个根的最大整数。我试过了
int(n**(1/k))
但是对于 n=125，k=3，这给出了错误的答案！我碰巧知道 5 立方是 125。
>>> int(125**(1/3))
4
什么是更好的算法？
背景：在2011年，这个失误让我击败了Google Code Jam问题昂贵的晚餐。
一种解决方案首先将 hi 反复乘以 2 直到 n 介于 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
怎么样：
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 .
我被严重烧伤后的谨慎解决方案：
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
为什么不试试这个：
125 ** (1 / float(3))
或
pow(125, 1 / float(3))
它返回 5.0，因此您可以使用 int(( 转换为 int。
这是在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
>>>
我想知道从基于对数的方法开始是否可以帮助确定舍入误差的来源。例如：
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
def nth_root(n, k):
x = n**(1./k)
y = int(x)
return y + 1 if y != x else y
你可以四舍五入到最接近的整数而不是四舍五入/到零(我不知道Python指定了什么(：
def rtn (x):
return int (x + 0.5)
>>> rtn (125 ** (1/3))
5
int(125**(1/3))显然应该是5，即正确答案，所以这一定是标准的计算机舍入误差，即内部结果是4.99999999999，四舍五入为4。 无论您使用哪种算法，都会存在此问题。 一个简单的临时解决方案是添加一个微小的数字，例如 int((125**(1/3)) + 0.00000001)
在完成所有操作之前执行此操作：
from __future__ import division
然后运行上述任何指定的技术以获得结果。
def nthrootofm(a,n):
a= pow(a,(1/n))
return 'rounded:{},'.format(round(a))
a=125
n=3
q=nthrootofm(a,n)
print(q)
只是使用了格式字符串，也许这会有所帮助。