只要意识到递归关系:后n位含5 当且仅当 倒数第n位是5 或 后n-1位含5
实现就异常elegant(Python3.3+)
def gen5 (n):
""" Generate all k-digit (1<=k<=n) decimals with digit 5 in ascending
order. """
if n>=1:
POW = 10**(n-1)
yield from (x * POW + y for x in range(5) for y in gen5(n-1))
yield from (5 * POW + y for y in range(POW))
yield from (x * POW + y for x in range(6,10) for y in gen5(n-1))
如果你只是要顺序输出打印“所有含5的N位十进制数”,简单地
>>> list(gen5(0))
[]
>>> list(gen5(1))
[5]
>>> list(gen5(2))
[5, 15, 25, 35, 45, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 65, 75, 85, 95]
如果是设一个上限,再判断一下即可
def gen5_upto (maxnum):
import math
N = math.ceil(math.log10(n))
for n5 in gen5(N):
if n5 > maxnum: break
yield n5
>>> list(gen5_upto(3))
[]
>>> list(gen5_upto(53))
[5, 15, 25, 35, 45, 50, 51, 52, 53]
>>> len(list(gen5_upto(8888)))
3148