PythonTip提供了一个不错的学习算法平台，大学毕业前挑战进入了前几名pythonwood解题数量。

当时有些未攻克的题目，比如密码生成题目，如今积累工作经验之后从新挑战，成功了。把过程记录分享下。

描述:

生活在当代社会，我们要记住很多密码，银行卡，qq，人人，微博，邮箱等等。小P经过一番思索之后，发明了下面这种生成密码方法：给定两个正整数a和b, 利用a / b我们会得到一个长度无限的小数(若a / b不是无限小数，比如1/2=0.5,我们认为0.5是0.5000000…，同样将其看做无限长的小数），小P将该小数点后第x位到第y位的数字当做密码，这样，无论密码有多长，小P只要记住a,b,x,y四个数字就可以了，牢记密码再也不是那么困难的事情了。现在告诉你a,b,x,y（0 < a,b <= 20132013, 0 < x <= y < 100000000000),请你输出密码。例如：a = 1, b = 2, x = 1, y = 4, 则 a / b = 0.5000000…, 输出小数点后第1到4位数字，即5000

分析：

计算机浮点计算有精度问题，所以直接除法得结果的思路不通。这次我想到小学的列竖式除法算法本身是可以解无穷除法的。于是，这道题就是把我们小学早已学过的算法，用代码表示出来。

下面包含几个算法， 都比较简介，比较pythonic（在网上看到是算法代码普遍臃肿）。只有最后的循环记录法是在规定时间内通过的。

Python代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#! /usr/bin/env python
#coding: utf8

# 返回a除以b的商的小数部分的第x位到第y位
a = 22; b = 300003; x = 1; y = 50

################################################################################
print "F: 不能引入sys 模拟手工除法"
################################################################################
import sys

t = a % b

for c in range(y):
    t *= 10
    if c+1 >= x:
        sys.stdout.write( str(t//b) )
    t %= b
print

################################################################################
print "F: 时间复杂度不足 同上"
################################################################################
code = ""
t = a % b

for c in range(y):
    t *= 10
    if c+1 >= x:
        code += str(t//b) 
    t %= b
print code


################################################################################
print "F: 时间复杂度不足 变除为乘补零难"
################################################################################
t = a % b
lzero = ""
_t = t * 10
while _t < b:
    lzero += "0"
    _t *= 10
print lzero + str(t * 10 ** y // b)[x-1:]


################################################################################
print "F: 时间复杂度不足 同上"
################################################################################
t = a % b
lzero = ""
_t = t * 10
while _t < b:
    lzero += "0"
    _t *= 10
print lzero + str(int( str(t) + '0' * y ) // b)[x-1:]


################################################################################
print "T: 挑战成功 循环小数记录法"
################################################################################

code = "" # 遇见循环即止
rep = ""  # 循环体
left = [] # 余数池
t = a % b

for c in xrange(y):
    if t in left:
        rep = code[left.index(t):]
        break
    else:
        left.append(t)
    t *= 10
    code += str(t//b) 
    t %= b
else:
    print code[x-1:]

print ( code + rep * ( (y - len(code))/len(rep) ) + rep[: ( (y - len(code))%len(rep) ) ] )[x-1:]


原文出自发表的https://blog.pythonwood.com/2017/12/Python解无穷大数除法算法——挑战PythonTip/



扩展阅读