2

Суть задачи в том, чтобы узнать можно ли из числа, которое дано на вход получить пару чисел: целое число возведенное в целочисленную степень. Например если дано число 81, то пара будет [9, 2], т.к. 9 в квадрате = 81. Также необходимо эту пару вывести, если пар > 1, то допускается вывести только одну из них, а если пар нет, то вернуть None. Я написал следующий код:

from math import log


def degree(val):
    for x in range(2, 1000000):
        lg = log(val, x)
        if int(lg) == lg and lg >= 2:
            return [x, int(log(val, x))]

    return None


print(degree(59049))

Проблема заключается в том, что в некоторых случаях я получаю вместо целого числа подобное: 3.0000000000000004, 4.999999999999999 и тд.

Округлять эти числа скорее всего не самое верное решение, так как алгоритм вычисления завязан на сравнении округленного и не округленного числа. Заранее спасибо за какую либо помощь.

PS: проблемы начинаются с числа 125, т.е. (5 в 3 степени)

4 ответа 4

3

Так вы работайте в целых числах - проверяйте делимость исходного val на числа в диапазоне до sqrt(val)

Если val целочисленно делится на n, и только на n (в процессе деления в конце концов получили 1), то вы нашли то, что нужно.

def degree(val):
    n = 2
    while n * n <= val:
        t = val
        p = 0
        while t % n == 0:
            t //= n
            p += 1
        if t == 1:
            return n, p
        n += 1
    return None
2

Работать с целыми числами. И незачем перерывать все числа до миллионов — проще всего работать с показателями степени, их меньше. Вот мой вариант:

from math import log

def Degree(n):
    for b in range(2, int(log(n)/log(2))+1):
        a = int(n**(1/b)+0.5)
        if a**b == n:
            return [a, b]

    return None
2

Другие ответы про работу с целыми числами более правильные по сути, но я хочу вам показать, что и оставаясь в пространстве чисел с плавающей точкой в питоне тоже можно получать точные/правильные результаты. Python, как и многие другие языки, поддерживает точный формат чисел с плавающей запятой decimal. И я тут использую формулу для вычисления логарифма с любым основанием через натуральный логарифм: log(a, b) = log(a)/log(b), потому что в модуле decimal есть только натуральный логарифм и логарифм с основанием 10. И ещё я вывожу все ответы, а не только первый:

from decimal import Decimal

def degree(val):
    log_val = Decimal(val).ln();
    for x in range(2, int(val ** 0.5) + 1):
        lg = log_val / Decimal(x).ln() 
        if int(lg) == lg and lg >= 2:
            yield [x, int(lg)]
    return None

print(list(degree(59049)))

Вывод:

[[3, 10], [9, 5], [243, 2]]
3
  • 2
    Decimal - формат с настраиваемой точностью, но он не абсолютно точный. Проблемы начнутся уже на degree(8). Чтобы улучшить результат, можно в проверке использовать x ** round(lg) == val. И в выводе int на round, соответственно. Это и с float поможет, хоть и в меньшей степени.
    – extrn
    30 ноя 2021 в 7:41
  • Спасибо за доп информацию, полезно
    – Effex
    30 ноя 2021 в 7:52
  • 1
    @extrn Ну тогда лучше всё-таки в целых числах всё считать. Но про decimal иметь представление полезно )
    – CrazyElf
    30 ноя 2021 в 7:54
1

Связка lg = log(val, x), int(lg) == lg будет работать только если логарифм считается точно (в тех случаях когда он может быть посчитан точно). Это, к сожалению, не так. Точность логарифма не гарантирована.

Мы можем можем использовать логарифм чтобы получить приближенное значение, но проверять его надо с помощью точной арифметики. Например: lg = round(log(val, x)), x ** lg == val. В первой части приведение к целому заменено на округление (чтобы небольшую неточность не превращать в катастрофу, как это делает int). Проверка заменена на точную, которая вычисляется в целых числах.

Может ли новый код ошибаться? Хотя гарантий достаточной точности вычисления логарифма у нас по-прежнему нет, можно убедится что логарифм считается достаточно точно чтобы погрешность результата никогда не превышала 0.5.

Вторая ошибка - верхняя граница x. Для val = 1000002000001 (= 1000001^2) программа ничего не вернёт. Границу надо увеличить до sqrt(val):

Вот это будет работать...

from math import log, isqrt


def degree(val):
    for x in range(2, isqrt(val) + 1):
        lg = round(log(val, x))
        if x ** lg == val and lg >= 2:
            return [x, lg]

    return None


print(degree(int(input())))

... но медленно. Сложность алгоритма примерно sqrt(val) - столько различных значений x мы пробуем если val не степень какого-нибудь числа.

Можно сделать лучше. Будем перебирать заначения lg от двух до чего-то там и вычислять по ним подходящий x. Затем снова точная проверка в целых числах:

def degree(val):
    lg = 2
    while True:
        x = round(val ** (1 / lg))
        if x == 1:
            break
        if x ** lg == val:
            return [x, lg]
        lg += 1

    return None


print(degree(int(input())))

Выражение val ** (1 / lg) вычисляет корень степени lg из val. Примерно, конечно, но, кажется, работает. Без строгих гарантий.

Скорость стала значительно лучше. Количество итераций цикла не больше log(val, 1.5). Другими словами время работы пропорционально (примерно) длине вводимого числа. Отличный результат.

Вернёмся к "не строгим гарантиям" и сломаем нашу новую быструю программу. Вещественный тип в Питоне точно хранит не более 16 десятичных знаков. Подадим на вход число (10^16 + 1)^2 (= 100000000000000020000000000000001) и она ничего не найдет, так как не может извлечь корень квадратный достаточно точно.

Шутки в сторону - простые приближенные методы или работают медленно или быстро начинают врать. К счастью, извлечь корень из целого числа можно двоичным поиском точно. Новая программа будет медленее двух кандидатов на небольших числах, но её рабочий диапазон ограничен только памятью вашего компьютера и вашим свободным временем. И что значит "медленнее"? Новая программа обрабатывает числа из десятков тысяч цифр за доли секунды, не так уж и медленно:

def bsearch(pred, low, high):
    assert not pred(low) and pred(high)
    while low < high - 1:
        mid = (low + high) // 2
        assert low < mid < high
        if pred(mid):
            high = mid
        else:
            low = mid
        assert not pred(low) and pred(high)
    assert low + 1 == high

    return low


def iroot(n, e):

    def pred(b):
        return n < b ** e

    high = 1
    while not pred(high):
        high *= 2
    
    return bsearch(pred, 0, high)


def any_iroot(n):
    e = 2
    while True:
        r = iroot(n, e)
        if r ** e == n:
            return r, e
        if r == 1:
            return None
        e += 1


print(any_iroot(int(input())))
$ time echo 100000000000000020000000000000001 | python any_iroot_int.py
(10000000000000001, 2)

real  0m0.033s
user  0m0.024s
sys   0m0.004s

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.