Python算法例27 对称数

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 一般不会太大，因此该算法是有效的。