每日一题——Python实现PAT乙级1019 数字黑洞（举一反三+思想解读+逐步优化）

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

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

Python-3.12.0文档解读

目录

我的写法

点评代码的优缺点：

时间复杂度：

空间复杂度：

改进点：

我要更强

哲学和编程思想

举一反三

我的写法

import sys  # 导入sys模块，以便使用sys.exit()函数来退出程序

N=input()  # 从标准输入获取一个字符串
N=[int(i) for i in N.zfill(4)]  # 将输入的字符串填充至少4位，不足的部分用0填充，然后将每个字符转换为整数并存入列表N

l=int("".join(map(str,sorted(N,reverse=True))))  # 将列表N从大到小排序，转换成字符串然后转换成整数，赋值给l
r=int("".join(map(str,sorted(N))))  # 将列表N从小到大排序，转换成字符串然后转换成整数，赋值给r

if l==r:  # 如果l和r相等，表示所有位数都相同
    print(f"{l} - {l} = 0000")  # 输出结果，并且结果为0000
    sys.exit(0)  # 退出程序

while (l-r)!=6174:  # 当l和r的差不等于6174时，进入循环
    new=l-r  # 计算l和r的差，赋值给new
    print("%04d - %04d = %04d" % (l,r,new))  # 格式化输出l、r和他们的差
    new=[int(i) for i in str(new).zfill(4)]  # 将new填充至至少4位，转换成字符串，每个字符转换为整数并存入列表new
    l=int("".join(map(str,sorted(new,reverse=True))))  # 将new列表从大到小排序，转换成字符串然后转换成整数，赋值给l
    r=int("".join(map(str,sorted(new))))  # 将new列表从小到大排序，转换成字符串然后转换成整数，赋值给r

else:  # 当while循环退出时（当l-r等于6174）
    new=l-r  # 计算最后一次的l和r的差
    print("%04d - %04d = %04d" % (l,r,new))  # 格式化输出最后一次的l、r和他们的差

这段代码是为了解决卡普雷卡尔常数（Kaprekar's constant）问题，即通过不断对一个四位数进行排序和相减，来演示如何最终达到6174这个固定值（对于至少包含两个不同数字的四位数）。

点评代码的优缺点：

优点：

1. 代码逻辑清晰，步骤分明，易于阅读和理解。
2. 代码处理了输入数字不足四位的情况，通过使用zfill(4)来确保运算始终在四位数上进行。
3. 格式化输出结果，易于用户查看每步的计算过程。

缺点：

1. 缺乏输入验证，没有检查用户输入是否为合法的四位数字。
2. 使用了sys.exit()来退出循环，这在某些情况下可能不是最好的实践。一般而言，应该避免在循环中使用退出函数，因为它会导致整个程序的退出，而不是仅仅跳出循环。可以考虑将循环放在一个函数中，并通过return来退出函数。
3. 在每次循环中都进行了字符串和整数之间的相互转换，这增加了不必要的计算量和复杂性。

时间复杂度：

代码中的while循环最多会执行多少次不是固定的，它取决于初始数字到达6174需要的迭代次数。但对于任何至少包含两个不同数字的四位数，这个过程最多会迭代7次。因此，可以认为时间复杂度是O(1)，即常数时间复杂度，与输入大小无关。

空间复杂度：

空间复杂度也是O(1)，因为不管输入如何，代码中使用的变量数量保持不变，不会随着输入的增加而增加。

改进点：

对于该代码，可以考虑以下改进：

• 添加对输入的验证，确保它是一个四位数，并且至少包含两个不同的数字。
• 将重复的排序和转换操作封装为函数，减少代码的重复性并提高可读性。

考虑用更优雅的方式替代sys.exit()退出循环。

我要更强

为了优化时间复杂度和空间复杂度，我们可以考虑以下几点：

1. 避免不必要的字符串和整数之间的转换。
2. 使用更高效的数据结构和算法。
3. 减少重复计算，例如，可以只对新产生的数字进行排序和转换，而不是每次都重新排序和转换。

下面是一个优化后的代码示例：

def kaprekar_process(num):
    # 确保输入是一个四位数
    if not (1000 <= num <= 9999) or len(set(str(num))) == 1:
        return "输入必须是一个至少包含两个不同数字的四位数"

    # 定义一个函数来计算Kaprekar过程的下一步
    def next_step(n):
        # 将数字转换为列表，方便排序
        digits = sorted([int(d) for d in str(n)])
        # 生成最大和最小可能的数字
        l = int(''.join(map(str, digits[::-1])))
        r = int(''.join(map(str, digits)))
        return l - r

    # 执行Kaprekar过程，直到结果为6174
    steps = 0
    while num != 6174:
        num = next_step(num)
        # 格式化输出
        print(f"{l:04d} - {r:04d} = {num:04d}")
        steps += 1

    return steps

# 测试代码
num = int(input("请输入一个四位数："))
steps = kaprekar_process(num)
print(f"完成Kaprekar过程，共执行了{steps}步。")

在这个优化后的代码中，我们定义了一个内部函数next_step来计算Kaprekar过程的下一步，这样可以避免重复的代码。我们还添加了输入验证，确保输入是一个有效的四位数。此外，我们只对新产生的数字进行排序和转换，而不是每次都重新排序和转换，这样可以减少计算量。

时间复杂度：

由于我们只对新产生的数字进行排序和转换，时间复杂度仍然是O(1)，因为对于任何有效的四位数，Kaprekar过程最多执行7次。

空间复杂度：

空间复杂度也是O(1)，因为我们使用的变量数量是固定的，不会随着输入的增加而增加。

这个代码示例已经尽可能地优化了时间复杂度和空间复杂度，同时保持了代码的可读性和可维护性。

哲学和编程思想

优化这段代码涉及到的哲学和编程思想主要包括：

1. 抽象化（Abstraction）： 通过定义内部函数next_step，我们将计算Kaprekar过程的下一步的逻辑抽象出来，使得主函数更加简洁，易于理解和维护。这种抽象化的思想是编程中的一个基本原则，它允许我们将复杂的系统分解为更小、更易于管理的部分。

2. 模块化（Modularity）： 将功能分解为独立的模块或函数，每个模块负责一个特定的任务。这不仅提高了代码的可读性，还使得代码更容易测试和重用。在这个例子中，next_step函数就是一个模块，它负责计算Kaprekar过程的下一步。

3. 优化（Optimization）： 在编程中，优化通常指的是通过改进算法或数据结构来提高程序的性能。在这个例子中，我们避免了不必要的字符串和整数之间的转换，减少了计算量，从而优化了时间复杂度。

4. DRY原则（Don't Repeat Yourself）： 这个原则鼓励开发者避免代码重复。通过将重复的逻辑封装在next_step函数中，我们遵循了DRY原则，使得代码更加简洁和可维护。

5. 输入验证（Input Validation）： 在处理用户输入时，确保输入的有效性是至关重要的。这不仅有助于防止错误，还可以提高程序的健壮性。在这个例子中，我们添加了输入验证，确保输入是一个有效的四位数。

6. 迭代（Iteration）： 迭代是编程中的一个基本概念，它允许我们重复执行一组操作，直到满足某个条件。在这个例子中，我们使用了一个while循环来迭代执行Kaprekar过程，直到结果为6174。

7. 格式化输出（Formatted Output）： 格式化输出是一种编程实践，它使得输出更加清晰和易于理解。在这个例子中，我们使用了格式化字符串来确保输出始终是四位数，并且易于阅读。

这些哲学和编程思想是软件开发中的核心原则，它们有助于提高代码的质量、可维护性和性能。通过应用这些原则，可以创建出更加健壮、高效和易于理解的程序。

举一反三

以下是一些基于前面提到的哲学和编程思想的技巧，可以帮助在不同的编程场景中应用这些原则：

1. 追求干净、可读的代码(DRY原则):

   • 标识重复的代码块并将它们抽象成函数或方法。
   • 使用循环和递归来处理重复的逻辑，而不是手动拷贝和粘贴代码。
   • 创建通用的代码模块，用于执行频繁使用的任务。

2. 优化性能:

   • 分析代码，找出瓶颈，例如使用性能分析工具。
   • 选择合适的数据结构和算法来解决问题，例如使用哈希表来快速查找数据，而不是列表。
   • 避免在循环内部进行不必要的计算，将可以在循环外计算的表达式提出来。

3. 简化复杂性(Abstraction):

   • 封装复杂的操作，提供简单的接口。
   • 避免过度工程，从最简单的解决方案开始，然后根据需要迭代和改进。
   • 使用设计模式来处理常见的设计问题。

4. 提高代码的模块化(Modularity):

   • 设计独立的模块，每个模块执行一个单一的任务。
   • 使用接口或抽象类来定义模块之间的互动。
   • 尽量减少模块之间的依赖关系。

5. 输入验证(Input Validation):

   • 总是检查外部输入，不要假定它们是有效的。
   • 使用异常处理来管理预期外的情况。
   • 对用户输入执行合理性检查，如数据类型、格式和范围。

6. 迭代(Iteration):

   • 采用迭代的方法来逐步改进程序。
   • 使用版本控制系统来管理代码的变化，这样你可以安全地探索不同的解决方案。
   • 测试你的代码在每一次改进后的表现。

7. 格式化输出(Formatted Output):

   • 使用字符串格式化来创建清晰、可读的输出。
   • 确保输出数据的格式符合用户的期望和行业标准。
   • 为输出的数据提供合适的上下文，使其对用户有意义。

这些技巧不仅限于特定的语言或框架；它们是普遍适用的编程实践，可以帮助编写更优质的代码。在实际应用中，应该根据具体的情况和需求灵活运用它们。