Python算法例27 对称数

发布时间:2023年12月24日

1. 问题描述

对称数是一个旋转180°后(倒过来)看起来与原数相同的数,找到所有长度为n的对称数。

2. 问题示例

给出n=2,返回["11","69","88","96"]。

3. 代码实现

采用递归生成对称数的方法实现

具体步骤如下:

  1. 对于长度为 0 的对称数,返回空列表 [];
  2. 对于长度为 1 的对称数,返回 ['0', '1', '8'];
  3. 对于长度大于 1 的对称数,可以通过递归地生成长度为 n-2 的对称数,然后在两侧加上合适的数字来得到长度为 n 的对称数。
    在两侧加上合适的数字可以使用循环遍历来实现,需要注意开头不能是'0'。
def find_symmetric_numbers(n):
    if n == 0:
        return []
    elif n == 1:
        return ['0', '1', '8']
    elif n == 2:
        return ['11', '69', '88', '96']
    else:
        result = []
        symmetric_nums = find_symmetric_numbers(n-2)
        for num in symmetric_nums:
            result.append('0' + num + '0')
            result.append('1' + num + '1')
            result.append('6' + num + '9')
            result.append('8' + num + '8')
            result.append('9' + num + '6')
        return result

n = int(input("请输入对称数的长度:"))
result = find_symmetric_numbers(n)
print("长度为", n, "的对称数是:", result)

这个算法使用了递归生成对称数,时间复杂度取决于生成的对称数个数,可以表示为 O(k^n),其中 k 是每个位置可能的数字个数(这里是5,因为可以是'0', '1', '6', '8', '9'),n 是对称数的长度。在实际应用中,n 一般不会太大,因此该算法是有效的。

文章来源:https://blog.csdn.net/m0_62110645/article/details/135172168
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。