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構成”之前進行切換的話，只需要切換以下兩條陳述句即可，