我想找到小于或等于n的k次方根的最大整数。我已经尝试过
int(n**(1/k))
但对于n=125，k=3，这给出了错误的答案！我碰巧知道5的三次方是125。
>>> int(125**(1/3))
4
哪个算法更好？
背景：在2011年，这个小失误让我错失了击败谷歌代码竞赛难题Expensive Dinner的机会。
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。
- NPE
12
也许应该用
<=代替==，因为测试浮点数的相等性通常是很棘手的。 - unutbu3尝试在解释器中输入
125**(1./3)。你应该会得到类似于4.999999999999999的结果，而不是5。使用 int 会将其向下取整为 4。 - unutbu1@EricPostpischil：因为这会在
4 ** (1./3)和许多其他输入上失败，而我答案中的方法不会。 - NPE2小心处理大数：使用此答案中的方法，nth_root((10**20+2)2,2)=1020。 - Peter de Rivaz
我认为最简单且健壮的解决方案是将所有内容推送到“Decimal”并使用“val”的精度来设置“1/n”所需的精度，最终从中获取正确的四舍五入整数。 - DSM
显示剩余7条评论
15
一种解决方案是将答案首先夹在lo和hi之间，通过反复将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
- user448810
8
这能保证找到精确的整数根吗？ - Ben Aaronson
@Ben：是的，两种方法都可以。 - user448810
1为什么会这样？它不可能卡在另一个整数上吗？ - Ben Aaronson
@Ben：你有一个失败的例子吗？ - user448810
不，我只是想要有信心使用它。稍后我可以尝试测试一下，并更新是否发现任何失败的情况。 - Ben Aaronson
显示剩余3条评论
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
- Colonel Panic
4
有时候我发现将这种方法与可变步长一起使用可以加速收敛（仅在使用非常大的数字时才需要！） - Peter de Rivaz
@Peter，第一次猜测真的可以比1错得更多吗？ - Colonel Panic
当然，如果
N太大无法转换为浮点数，则N**(1./k)会导致计算错误。对于足够小的N来说，N**(1./k)是接近准确的，所以调整时间不会太长。如果你对处理大数感兴趣，其中将整数转换为浮点数会损失过多精度，那么进行几步牛顿迭代法可以获得精确结果。 - Daniel Fischer1int(((1040)2)(1.0/2))=1040+303786028427003666890752，因此可能会有很大的误差！ - Peter de Rivaz
3
为什么不试试这个呢：
或者
它返回了5.0，因此您可以使用int（）将其转换为整数。
125 ** (1 / float(3))
或者
pow(125, 1 / float(3))
它返回了5.0，因此您可以使用int（）将其转换为整数。
- Natig Aliyev
1
这是使用牛顿-拉弗森方法的Lua代码：
> 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
>
Python版本
>>> 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
>>>
- Doug Currie
3
nthroot(10**4,4)=32 用这种方法，我本来期望的是10？ - Peter de Rivaz
你需要增加迭代次数以处理更大的数字；对于10**4，
range(32)已经足够了。 - Doug Currie这个方法对我来说似乎极其缓慢。计算nthroot(10**4,4)需要循环21次，而计算nthroot(10**15,15)则需要循环423次。 - Todd Lehman
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
- Escualo
1
def nth_root(n, k):
x = n**(1./k)
y = int(x)
return y + 1 if y != x else y
- ecline6
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)
刚刚使用了格式化字符串，也许这会有所帮助。
- ravi tanwar
0
你可以四舍五入到最接近的整数，而不是向下取整/取零（我不知道Python具体规定）：
def rtn (x):
return int (x + 0.5)
>>> rtn (125 ** (1/3))
5
- Alexandre C.
2
2
rtn(4 ** (1./3)) 是 2，但是 2**3 > 4。 - unutbu@mbomb007：如果x是非负数，似乎它可以工作（需要根据规范进行检查--如果Python中有向零舍入，则需要针对负数进行调整）。但是，非整数幂仅对非负数有明确定义！ - Alexandre C.
0
在开始之前，请先执行以下操作：
from __future__ import division
然后运行上述任何一种技术，以获得您的结果。
- khan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
125**(1/3)->4.999999999999999- wjandrea