主页 / 问题 / 1355544
Accepted
Effex
Asked:2022-04-30 14:37:49 +0000 UTC2022-04-30 14:37:49 +0000 UTC

如何解决非整数问题？

  • 772

问题的本质是找出是否有可能从作为输入的数字中得到一对数字：一个整数的整数幂。例如，如果给出数字 81，那么该对将是 [9, 2]，因为 9 squared = 81. 还需要显示这个pair，如果pair > 1，则只允许显示其中一个，如果没有pair，则返回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 次幂）

python

4 个回答

  1. 这就是您在整数中的工作方式 - 检查原始val数字的可分性，范围为sqrt(val)

    如果它是整数，并且只能被val整除（在除法的过程中，我们最终得到了 1），那么你已经找到了你需要的东西。nn

    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
    • 3
  2. Best Answer

    使用整数。并且没有必要搜索数以百万计的所有数字 - 最简单的方法是使用指数，它们的数量更少。这是我的选择：

    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

  3. 关于使用整数的其他答案本质上更正确，但我想向您展示，在 python 中停留在浮点数的空间中也可以获得准确/正确的结果。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]]
    • 2

  4. 该链接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不是某个数字的幂的话。

    可以做得更好。我们将把值从 2 迭代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)。换句话说，运行时间与输入数字的长度成比例（大约）。优秀的结果。

    让我们回到“非强保证”并打破我们新的快速程序。Python 中的 real 类型准确地存储不超过 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
    • 1

相关问题