主页 / 问题 / 1427030
Accepted
Alexander_K
Asked:2022-09-06 13:06:05 +0000 UTC2022-09-06 13:06:05 +0000 UTC

检查数字是否是整数的平方

  • 772

给定一个整数，判断它是否为平方数：

在数学中，平方数或完全平方是整数，它是整数的平方；换句话说，它是某个整数倍本身的乘积。

例子：-1: False, 0: True, 25 True | CodeWars

第一个解决方案通过了所有测试，但没有及时通过：

if n ==0:
    return True
else:
    for i in range(0,n):
        if i*i==n:
            return True
    else:
        return False

第二个选项未通过 3 次测试（对于 3、26 和秘密）：

if n == 0:
    return True
elif n<0:
    return False
else:
    if n ** 0.5 == 1: return False
    else: return True

为什么第二个选项无法通过这些测试？

我们需要一个花费很少时间的选项（不属于错误Execution Timed Out (12000 ms)，并且不使用库。

python

4 个回答

  1. Best Answer

    循环直到 没有意义n。平均而言，这大约是 100,500 次额外操作。如果n它等于 10001，那么您将获得 9900 次额外的迭代，因为任何大于 100 的数字的平方已经大于 10000，所以为什么要检查它们。你需要循环到平方根n

    if n == 0:
    return True
else:
    for i in range(n + 1):
        i2 = i * i # квадрат очередного числа
        if i2 == n:
            return True
        elif i2 > n: # если квадрат больше n, то нет смысла проверять дальше
            break
return False # тут я убрал else и перенес строчку на уровень выше. Разницы никакой нет, а читаемость улучшилась.

    添加 1 允许您删除第一次检查 0。所以我们最好用检查负数替换此检查：

    if n < 0:
    return False
else:
    for i in range(n + 1):
        i2 = i * i
        if i2 == n:
            return True
        elif i2 > n:
            break
return False
    • 3

  2. 对于任何整数，最简单的快速解决方案是二分查找，以获取平方根的整数部分，并直接检查其平方是否等于原始数字：

    def isqrt(n):
    low = 0
    high = n + 1 # + 1 to process 0, 1 properly
    
    while low < high - 1:
        mid = (low + high) // 2
        if n < mid ** 2:
            high = mid
        else:
            low = mid

    return low


def is_square(n):
    return n >= 0 and isqrt(n) ** 2 == n
    • 3

  3. 我会给出它作为答案，因为我自己在任务中经常遇到这种情况，但我在评论中没有看到这种特殊方法。虽然，如果您有一个专门用于简单求幂的案例，那么下面的选项在这里将无济于事。但在许多类似的情况下，这将是必要的。感谢@CrazyElf 对第一个答案的非常有价值的评论。

    使用求幂**和取模运算符%（例如，它们经常在散列中一起使用）对于大数来说通常很耗时。在这种情况下，最好使用内置函数pow。

    例如，在将三位数提高到三位数幂的情况下**，它仍然比 快pow，但对于四位数，它是相反的。请参阅下面的示例，该示例是在我的（远非最新的）笔记本电脑上制作的。

    import timeit
import math

print(timeit.timeit ('pow(5362, 2445)')) # 142 секунды
print(timeit.timeit ('5362**2445'))      # 147 секунд

print(timeit.timeit ('(526 ** 252) % 10145')) # 2.87 секунды
print(timeit.timeit ('pow(526, 252, 10145)')) # 0.90 секунд

    这对于程序中各种求幂的多种应用尤其重要，包括递归的等，即 有大量这样的操作。

    这里有一篇关于这个主题的有趣文章：https ://blog.finxter.com/a-guide-to-pythons-pow-function/

    注意：pow图书馆里也math有，但有一些奇怪的地方。例如，pow(53, 244)它被认为没有错误，并且 math.pow(53, 244) 产生OverflowError: math range error. 所以我在这里看不到。

    • 0 
  4. for i in range(0,n):

    这样的检查是在 O(n) 中获得的。

    1. 您可以使用条件进行循环i*i <= n，然后它变为 O(sqrt(n))
    2. 您可以使用 binsearch 并获得 O(lb(n))
    3. 如果值的范围允许（结果不是无穷大），那么你可以提取平方根，得到一个实数，计算下一个和前一个数字相差多少（对于大值它不会是1） ，然后对结果范围进行循环或 bin 搜索。
    4. 您可以自己实现按列计算平方根的算法。即使输入数字应该非常大，这也将起作用。
    • 0

相关问题