Posts pythonTip 34 密码生成
Post
Cancel

pythonTip 34 密码生成

题目描述:

生活在当代社会,我们要记住很多密码,银行卡,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。

示例:

输入:a = 1 b = 2 x = 1 y = 4

输出:5000

分析:

对于我们的分数转化成小数,有两种情况:

  1. 可以整除
  2. 无限循环小数

基于这个理论,思路就是先找到分数转换成小数时的循环节,然后再利用循环节周期的特点,找到指定的区间的数字。

第一个问题:确定循环节

我们可以自己来简单模拟一下。举一个例子。

1/7 = 0.14285714285714285 循环节 就是 142857

如何确定循环节呢?

使用竖式除法进行一个模拟,当余数在前面已经出现的时候,就可以确定循环节了。下图是一个竖式除法,大家可以自己尝试一下。

竖式除法

如何判断当前余数是否已经出现了呢?

可以使用一个数组mod_s去保存每次除法后得到的余数。

根据上面的一个思路,我们就可以确定循环节了。接下来就是截取指定区间的数字了。

我给出两种情况:如下图

第一种是,起始端点都在一个循环节里面。

第二种是,起始端点不在一个循环节里面。

image-20201209181630429

再回过头分析一下,首先分为是否可以整除。如果可以整除前面一部分不是0,最后都是0。

如果不可以整除,就分为上面的两种情况:起始端点都在一个循环节里面,起始端点不在一个循环节里面。

在一个循环节里面,就是截取一部分就好。如果不在一个循环节里面,就是相当于分成了 3 部分。

第一部分就是 起点到起点所在循环节的终点。

第二部分是 中间包含的循环节。可能有多个,也可能一个也没有。

第三部分是 终点所在的循环节的起点,到终点。

好了,现在分析的差不多了。就可以叠代码。

代码:

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
from math import ceil
a %= b
ta = a

mod_s = []
res_s = []
flag = 1
while True:
    
    if a // b == 0:
        a *= 10
        
    res_s.append(a//b)  
    a = a % b
    if a == 0:
        res_s.append(0)
        break
    if a in mod_s:
        break
    mod_s.append(a)


res_s = "".join([str(s) for s in res_s])
# print(res_s)

if a == 0:
    if len(res_s) < y:
        ans = res_s[x-1:]
        ans += (y-x+1-len(ans)) * "0"
    else:
        ans = res_s[x-1:y]
else:
    res_s = res_s[:-1]
    ans = ceil(y/len(res_s)) * res_s
    ans = ans[x-1:y]

print(ans)
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 33 大幂次运算

pythonTip 35 最大连续子序列

Trending Tags