2025年3月15日 星期六 甲辰(龙)年 月十四 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q01: 回文十进制数

时间:12-19来源:作者:点击数:32

1. 问题描述

如果把某个数的各个数字按相反的顺序排列,得到的数和原数相同,则称这个数为“回文数”。比如123454321是一个回文数。

求用十进制、二进制、八进制表达都是回文数的所有数字,大于十进制10的最小值。

2. 解题分析

本题使用暴力搜索即可。

但是通过分析数的结构可以合理地减少有效搜索范围。

由于数的首位(最高位)的数字不能为0,因此要构成回文数,最低位的数字也不能为0。这个约束条件规则应用到十进制数就意味着该数不能被10整除,同理,该数也不能被8整除,也不能被2整除。

3. 代码和运行结果

  • # -*- coding: utf-8 -*-
  • """
  • Created on Thu Aug 19 08:55:36 2021
  • @author: chenxy
  • """
  • import time
  • import random
  • class Solution:
  • def palindrome(self, N: int) -> int:
  • """
  • :N: The number of the smallest palindrome to be searched for
  • :
  • :ret: return the palindrome list
  • """
  • count = 0
  • rslt = []
  • k = 11
  • while (1):
  • if not (k%8==0 or k%10==0):
  • if k%1001 == 0: # cannot use 'k%1000' as print condition!
  • print('k = {0}'.format(k))
  • k_decstr = str(k)
  • if k_decstr == k_decstr[::-1]: # aStr[::-1] return the reverse of the original one
  • k_binstr = bin(k)[2:] # bin(k) will return '0bxxxx'
  • if k_binstr == k_binstr[::-1]:
  • k_octstr = oct(k)[2:] # oct(k) will return '0oxxxx'
  • if k_octstr == k_octstr[::-1]:
  • rslt.append(k)
  • count += 1
  • print('Found: k = {0}, count = {1}'.format(k, count))
  • if count == N:
  • break
  • k += 2 # Skip the even number
  • return rslt

以上代码比原题稍微延申了一点,改为寻找前N个三重回文数(即题目要求的十进制表示、二进制表示、八进制表示都是回文数)。测试运行结果如下:

  • if __name__ == '__main__':
  • sln = Solution()
  • N = 2
  • t1 = time.monotonic()
  • rslt = sln.palindrome(N)
  • t2 = time.monotonic()
  • print('N = {0}, rslt = {1}, tCost = {2}'.format(N,rslt,(t2-t1)))

搜索前两个三重回文数,结果非常出乎意料!

Found: k = 585, count = 1

Found: k = 719848917, count = 2

N = 2, rslt = [585, 719848917], tCost = 152.375

第2个三重回文数竟然是一个如此大的数,而且耗时长达152.375! 以这个速度没有勇气再进一步搜索第3个三重回文数了。需要对以上代码进行进一步优化。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门