每日一题——Python实现PAT甲级1015 Reversible Primes（举一反三+思想解读+逐步优化）

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

我的写法

is_prime函数分析：

decimal_to_base函数分析：

主循环分析：

我要更强

is_prime函数优化

decimal_to_base函数优化

完整代码及注释

优化解释

总结

哲学和编程思想

举一反三

题目链接

我的写法

# 定义函数is_prime用来检测一个数n是否为质数
def is_prime(n):
    # 如果n小于等于1，则它不是质数
    if n <= 1:
        return False
    # 如果n小于等于3，则它是质数
    if n <= 3:
        return True
    # 如果n能被2或3整除，则它不是质数
    if n % 2 == 0 or n % 3 == 0:
        return False
    # 初始化变量i为5
    i = 5
    # 循环，检测5及以上的数是否能整除n
    while i * i <= n:
        # 如果n能被i或i+2整除，则它不是质数
        if n % i == 0 or n % (i + 2) == 0:
            return False
        # 将i增加6后继续循环（6k±1的优化）
        i += 6
    # 如果上述条件都不满足，则n是质数
    return True

# 定义函数decimal_to_base，将十进制数转换为给定的base进制
def decimal_to_base(decimal_num, base):
    # 如果base不在2到36之间，则返回错误信息
    if base < 2 or base > 36:
        return "Base must be between 2 and 36."
    # 定义一个字符串包含了可能在进制转换中用到的所有字符
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    # 如果decimal_num小于base，直接返回对应的字符
    if decimal_num < base:
        return digits[decimal_num]
    # 否则进行递归调用，计算decimal_num除以base的商，并将余数对应的字符附加在后面
    else:
        return decimal_to_base(decimal_num // base, base) + digits[decimal_num % base]

# 主循环
while True:
    # 通过输入接收一行，然后分割字符串
    tmp=input().split()
    # 如果输入的长度小于2（即没有输入两个值），则退出循环
    if len(tmp)<2:
        break
    # 将输入的两个值转换为整数
    N,base=map(int,tmp)
    # 检查N是否为质数，以及N转换为指定进制后，翻转字符串并转换回十进制是否也为质数
    if is_prime(N) and is_prime(int(decimal_to_base(N,base)[::-1],base)):
        # 如果都是质数，则输出"Yes"
        print("Yes")
    else:
        # 否则输出"No"
        print("No")

这段代码包含两个主要的功能：一个是判断给定的整数是否为质数（is_prime函数），另一个是将十进制数转换为给定基数的表达形式（decimal_to_base函数）。最后，这两个功能在一个主循环中结合起来，以判断一个数及其在给定基数下的反转是否都是质数。

is_prime函数分析：

正确性：
- 此函数正确地实现了质数的判断，首先排除了不可能是质数的情况：小于等于1以及能够被2或3整除的数。其次利用了一个数学事实，即如果一个数n不是质数，那么它必定有一个因数小于或等于sqrt(n)。所以函数只检查到i*i <= n即可。
- 6k±1规则被用来减少需要检查的可能因子，因为所有质数（除了2和3）都能表示成6k±1的形式。
时间复杂度：
- 在最坏的情况下（n是一个质数或者只能被另一个质数整除），这个算法的时间复杂度是O(sqrt(n))，因为它最多需要检查sqrt(n)个数字。
空间复杂度：

该函数使用了常数空间，除了输入值n和循环变量i之外，没有使用额外的存储空间。

decimal_to_base函数分析：

正确性：
- 函数正确地实现了基数转换，使用了递归方法。它也考虑了边界情况，即基数需要在2到36之间。
时间复杂度：
- 这个函数的时间复杂度是O(log_base(n))，因为每次递归调用都将数字n除以基数base。
空间复杂度：

由于使用了递归，空间复杂度也是O(log_base(n))。每次递归调用都会在调用栈中添加一层，直到达到基准情况。

主循环分析：

主循环不断从用户那里接收输入，直到接收到的输入长度小于2。对于每一对输入，它会判断N是否为质数，以及N转换为指定进制后翻转字符串再转换回十进制是否也为质数。
时间复杂度：
- 主循环的时间复杂度依赖于输入的数N和基数base。质数检测有O(sqrt(N))的时间复杂度，而基数转换和反转字符串有O(log_base(N))的时间复杂度。
- 质数检测会被执行两次，一次对原始数N，一次对翻转后的数。如果这两个数的大小相近，总的时间复杂度大约是O(sqrt(N) + log_base(N))。
空间复杂度：

主循环使用的空间主要取决于is_prime和decimal_to_base函数的空间复杂度，分别是O(1)和O(log_base(N))。因此，主循环的总空间复杂度大约是O(log_base(N))。

总的来说，该代码是高效和有效的，特别是在判断质数和基数转换方面使用了一些优化的方法。不过，递归可能在非常大的数字和/或基数非常高时导致栈溢出，所以在这种情况下可能需要迭代的方法来代替递归实现基数转换。

我要更强

针对前述代码，我们可以考虑一些优化策略，以提高算法的效率和减少内存使用。优化主要集中在两个方面：is_prime函数和decimal_to_base函数的改进。

is_prime函数优化

对于is_prime函数，我们已经使用了6k±1规则来减少必要的检查次数，这是一个很好的优化。进一步的优化可能不会显著减少时间复杂度，因为它本质上已经是O(sqrt(n))，这是检查质数的较快方法之一。

decimal_to_base函数优化

对于decimal_to_base函数，我们可以避免递归以减少空间复杂度。通过使用循环而不是递归，我们可以将空间复杂度降低到O(1)。

完整代码及注释

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def decimal_to_base(decimal_num, base):
    if base < 2 or base > 36:
        return "Base must be between 2 and 36."
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    result = ""
    while decimal_num > 0:
        result = digits[decimal_num % base] + result
        decimal_num //= base
    return result or "0"

while True:
    tmp = input().split()
    if len(tmp) < 2:
        break
    N, base = map(int, tmp)
    if is_prime(N) and is_prime(int(decimal_to_base(N, base)[::-1], base)):
        print("Yes")
    else:
        print("No")

优化解释

is_prime函数保持不变，因为其时间复杂度已经是针对其操作相对较优的了。
decimal_to_base函数已改为使用循环而非递归。这种方法相比递归，减少了额外的函数调用开销和调用栈空间使用，从而将空间复杂度降低到O(1)。循环简单地将数字按基数转换，并每次迭代将余数添加到结果字符串的前面，达到了逆序的效果。

总结

这些优化帮助减少了内存使用（尤其是在decimal_to_base函数中避免了递归），而is_prime函数的优化主要集中在减少不必要的迭代上。然而，值得注意的是，在某些情况下，优化可能带来的性能提升是有限的，尤其是当输入值非常大时。此外，代码的可读性和维护性也是在进行优化时需要考虑的因素之一。

哲学和编程思想

在优化上述代码的过程中，我们实际上应用了几个编程和软件设计的哲学和思想：

KISS原则（Keep It Simple, Stupid）：此原则主张尽可能保持简单，避免不必要的复杂性。在优化decimal_to_base函数时，我们采用了一个简单的循环代替了递归，这使得函数实现更为直观且易于理解。
DRY原则（Don't Repeat Yourself）：这个原则鼓励减少重复，无论是数据还是逻辑。虽然在这里的优化中没有直接体现，但保持函数的单一职责（如is_prime只检查质数）和避免在代码中重复相同的逻辑是这个原则的体现。
分治思想：分治方法是一种将问题分解为更小部分来解决，然后合并结果以获得最终解决方案的方法。在原始代码中，decimal_to_base通过递归将大问题分解为小问题。优化后，虽然不再使用递归，但仍然通过循环逐步构建最终结果，可以看作是分治思想的一种变形应用。
时间和空间权衡：在计算机科学中，经常需要在时间复杂度和空间复杂度之间做出权衡。例如，在递归和迭代之间选择，就需要权衡它们在时间和空间上的消耗。在这里，我们优化decimal_to_base函数，将空间复杂度降低到O(1)，而保持时间复杂度不变，体现了对资源利用的权衡。
最小惊讶原则：这个原则表明代码应该如何预期般行事，避免混淆使用者。优化后的代码更加直白和易于理解，符合这一原则。
可维护性和可读性：优化代码的另一个考虑是确保代码的可维护性和可读性。在上述代码中，尽管我们进行了优化，但仍然保持了代码的清晰性和可读性，使得未来的维护更加容易。
渐进增强：这是一种逐步改进代码的方法，首先实现一个简单的版本，然后逐渐增加优化和改进。例如，我们首先定义了is_prime和decimal_to_base的基本版本，然后在后续版本中对其进行了优化。
代码重构：代码重构是改进现有代码结构而不改变其外部行为的过程。在优化decimal_to_base函数中，我们进行了重构，通过替换递归为迭代，来优化性能而不改变函数的功能。

这些哲学和思想都是编程实践中常常被采用的，目的是为了写出高效、易于维护和理解的代码。实现这些通常需要在代码的性能和其他因素（如可读性、可维护性）之间进行仔细的权衡。