目录
1. 问题描述
2 解法1—暴力搜索
2.1 解题分析
2.2 代码及测试
2.3 运行结果及分析
3. 解法2--逆向思考
3.1 解题分析
3.2 代码及测试
3.3 运行结果：
1. 问题描述
问题：求位于1~50的所有满足以上条件的n。
这道题目是典型的“批着羊皮的狼”，一看似乎很简单，然而陷阱重重的那种。
2 解法1—暴力搜索
2.1 解题分析
第一感是，暴力搜索搞一搞就可以了吧。反正我的习惯也是从最傻（naive）的方法着手。。。
算法流程如下：
以上流程之所以成立是因为如上所述“已知对于任意整数n，一定存在n的正整数倍的仅由0和7构成的数”，否则的话，以上流程就有可能陷入无限循环。
实际上仅由0和7构成的数再加上要构成回文数，则必然首尾都是7，因此可以排除掉偶数以及5的倍数，这样可以将搜索范围缩小一半。
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个数量级！
上一篇：Q34: 会有几次命中注定的相遇
下一篇：
本系列总目录参见：程序员的算法趣题：详细分析和Python全解