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

程序员的算法趣题Q35: 0和7的回文数

时间:12-29来源:作者:点击数:37

1. 问题描述

问题:求位于1~50的所有满足以上条件的n。

这道题目是典型的“批着羊皮的狼”,一看似乎很简单,然而陷阱重重的那种。

2解法1—暴力搜索

2.1 解题分析

第一感是,暴力搜索搞一搞就可以了吧。反正我的习惯也是从最傻(naive)的方法着手。。。

算法流程如下:

以上流程之所以成立是因为如上所述“已知对于任意整数n,一定存在n的正整数倍的仅由0和7构成的数”,否则的话,以上流程就有可能陷入无限循环。

实际上仅由0和7构成的数再加上要构成回文数,则必然首尾都是7,因此可以排除掉偶数以及5的倍数,这样可以将搜索范围缩小一半。

[2021-09-21]以上流程其实有缺陷,在最后(也即最内层)的判断后,如果判断不是回文数的话,则该数就不满足题设条件,因此可以跳到下一个n的检测了(即此处应该加一条break语句)

2.2 代码及测试

以上流程虽然简单易懂,然而写出代码一运行,就会让你怀疑人生。如果没有以上一定存在的保证,你会怀疑它是不是陷入了死循环;知道了有一定存在的保证,你就只能怀疑程序是不是写错了。

  • # -*- coding: utf-8 -*-
  • """
  • Created on Mon Sep 20 09:12:48 2021
  • @author: chenxy
  • """
  • import sys
  • import time
  • import datetime
  • import math
  • import random
  • from typing import List
  • # from queue import Queue
  • from collections import deque
  • import itertools as it
  • from math import sqrt, floor, ceil
  • import numpy as np
  • def palindrome(k:int)->bool:
  • k_decstr = str(k)
  • return k_decstr == k_decstr[::-1]
  • # Brute-Force
  • def check_0_7(k)->bool:
  • k_str = str(k)
  • return set(k_str) == {'0','7'}
  • # return set(k_str).issubset({'0','7'})
  • ans = []
  • t1 = time.perf_counter()
  • ok_dict = dict()
  • ng_dict = dict()
  • for n in range(1,50,2):
  • if n%5==0:
  • continue
  • # print(n)
  • m = 1
  • while 1:
  • k = m*n
  • # print(n,m,k)
  • if check_0_7(k):
  • # print(n,m,k)
  • if palindrome(k):
  • ok_dict[n] = (m,k)
  • else:
  • ng_dict[n] = (m,k)
  • break
  • m += 1
  • tCost = time.perf_counter() - t1
  • print('Number of ok_dict = {0}, tCost = {1}'.format(len(ok_dict),tCost))
  • for key in ok_dict:
  • print('\t',key, ok_dict[key])

2.3 运行结果及分析

单单针对9这个数字,在我的机器上跑了80多秒才跑出来。

仔细思考一下会发现,在以上正向循环中,针对m的遍历中,所得到的k=m*n绝大多数根本就不满足后面的“仅由0和7构成”以及“构成回文数”的条件,换句话说,绝大多数的遍历计算都是无效的。如果换一个方向,先筛选能满足“仅由0和7构成”以及“构成回文数”的条件的数再来判断是否能被n整除的话,就可以避免绝大多数无效的搜索了。

3. 解法2--逆向思考

3.1 解题分析

逆向思考的关键是先按照不同的位数,(1) 构成满足“仅由0和7构成(或仅由7构成)”的条件的数; (2) 用这些数去试能不能被待检查对象n(1~50之间奇数且不能被5整除)整除; (3) 如果能的话,再判断是否回文数,如果是的话,则这个n满足条件是答案之一;否则,这个n不满足条件应被排除。

针对以上流程遍历位数m即可。直到1~50间的数要么被判断满足条件要么不满足条件全部判断完毕就结束。

需要注意的一个坑是:题目要求的是n的倍数中第一个“仅由0和7构成(或仅由7构成)”的条件的数、同时又是回文数。n的倍数中可能有很多个满足“仅由0和7构成(或仅由7构成)”的条件的数,而且其中也可能有多个还满足回文数的条件。但是只有第一个(即最小的那个)满足“仅由0和7构成(或仅由7构成)”的条件的数同时又是回文数的n才符合题目的要求。这就是为什么是以上(1)—(2)—(3)的顺序,而不是(1)—(3)—(2)了。有兴趣的读者可以细想一下为什么(1)—(3)—(2)不行。

3.2 代码及测试

  • check_list = list(range(1,51,2))
  • ok_dict = dict()
  • ng_dict = dict()
  • t1 = time.perf_counter()
  • m = 1 # 'm': set the number of digits
  • while 1:
  • aSet = set() # Use set to remove repetition
  • for item in it.product(['0','7'], repeat=m):
  • # print(item)
  • if item[0]=='0' or ('0' not in item):
  • # if item[0]=='0':
  • continue
  • # print(''.join(list(each)))
  • aDec = int(''.join(list(item)))
  • for k in check_list:
  • if k in ok_dict or k in ng_dict:
  • continue
  • if aDec % k == 0:
  • if palindrome(aDec):
  • ok_dict[k] = (aDec//k,aDec)
  • else:
  • ng_dict[k] = (aDec//k,aDec)
  • if len(ok_dict)+len(ng_dict) == len(check_list):
  • break
  • m = m+1
  • tCost = time.perf_counter() - t1
  • print('Number of ok_dict = {0}, tCost = {1:6.3f}'.format(len(ok_dict),tCost))
  • for key in ok_dict:
  • print('\t',key, ok_dict[key])

其中如果需要“仅由0和7构成”或“仅由7构成”之前进行切换的话,只需要切换以下两条语句即可。

3.3 运行结果:

运行速度比前面的暴力搜索快5个数量级!

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