如何找到整数n次根源是什么？ [英] How to find integer nth roots?

问题描述

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

I want to find the greatest integer less than or equal to the kth root of n. I tried

int(n**(1/k))

不过对于N = 125，K = 3这给出了错误的答案！我碰巧知道，5立方为125。

But for n=125, k=3 this gives the wrong answer! I happen to know that 5 cubed is 125.

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

什么是更好的算法？

What's a better algorithm?

背景：在2011年，这一闪失，花了我击败谷歌code果酱。 <一href="https://$c$c.google.com/$c$cjam/contest/dashboard?c=1150486#s=p2">https://$c$c.google.com/$c$cjam/contest/dashboard?c=1150486#s=p2

Background: In 2011, this slip-up cost me beating Google Code Jam. https://code.google.com/codejam/contest/dashboard?c=1150486#s=p2

推荐答案

一个解决方案首先通过反复2至n为LO之间和喜，然后使用二进制搜索来计算确切的答案乘以喜斗拱低和高的答案

One solution first brackets the answer between lo and hi by repeatedly multiplying hi by 2 until n is between lo and then uses binary search to compute the exact answer:

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

一个不同的解决方案是使用牛顿的方法，它完美的作品以及对整数：

A different solution uses Newton's method, which works perfectly well on integers:

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

这篇关于如何找到整数n次根源是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！