Как найти целые n-ые корни?

Ответ 1

Одно решение сначала скопирует ответ между 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

Ответ 2

Как насчет:

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.

Ответ 3

Мое осторожное решение после столь плохого горения:

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

Ответ 4

Почему бы не попробовать это:

125 ** (1 / float(3)) 

или

pow(125, 1 / float(3))

Он возвращает 5.0, поэтому вы можете использовать int(), чтобы преобразовать в int.

Ответ 5

Здесь он находится в 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
>>> 

Ответ 6

Интересно, если начать с метода, основанного на логарифмах, может помочь вывести источники ошибок округления. Например:

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

Ответ 7

def nth_root(n, k):
    x = n**(1./k)
    y = int(x)
    return y + 1 if y != x else y

Ответ 8

int(125**(1/3)) должно быть четным, т.е. правильным ответом, поэтому это должна быть стандартная ошибка округления окружения, то есть внутренне результат равен 4.9999999999, который округляется до 4. Эта проблема будет существовать с любым алгоритмом, который вы используете. Одно простое решение - добавить небольшое число, например. int((125**(1/3)) + 0.00000001)

Ответ 9

Вы можете округлить до ближайшего целого числа вместо округления/до нуля (я не знаю, что указывает Python):

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

>>> rtn (125 ** (1/3))
5

Ответ 10

Сделайте это перед всем:

from __future__ import division

а затем запустите любой из указанных выше методов, чтобы получить ваши результаты.