- 实现效果
- 题目
- 思路
- 第一部分素数分解
- 第二部分统计数字出现次数
- 规律算法
- 抽象成排列组合算法
- 规律算法不超时算法代码
- 超时的基础版本代码
- 总结
主要内容是校设课程的习题和课外学习的一些习题。
实现效果欢迎关注 『Python习题』 系列，持续更新中
欢迎关注 『Python习题』 系列，持续更新中
耗时38ms
题目
- 描述
我的微信ID是大写字母WHUT后面的数字是两个素数连在一起，大的在前，小的在后，如果我告诉你两数的乘积是多少，你能计算出我的ID号吗？
如果输入一个[0-9]之间的数字，你能统计出从1开始到我ID中的数字的序列里，一共出现多少次这个数字吗？
- 输入格式
第一行输入ID中两个素数的乘积
第二行输入一个[0-9]之间的数字
- 输出格式
第一行输出ID号
第二行输出数字的次数
- 示例
输入：
196409
3
输出：
WHUT997197
599140
思路 第一部分素数分解
常规的遍历上限优化为开根号+1
我这里还用了列表，把之前找到的素数存储进列表，这样第二次找的时候可以用空间换时间来省一些时间（但其实没有必要，因为主要省时间是第二部分）
第二部分统计数字出现次数- 基础代码思路就是常规的使用
count()函数来统计个数，从0到997197循环遍历，超时的。
- 后来我想的第二种思路，分别统计各个位出现数字的概率，再相加即可。先用一个简单的例子演示：
假设现在是1532找数字4出现的次数：
#数字 1532 找4
#4>2---->个位出现了153次
#4>3---->十位出现了150次
#4<5---->百位出现了200次
#4>1---->千位出现了0次
大家总结一下规律，从一般到特殊：
(int(id[i-1])+1) 前一位数
(int(id[i+1])+1) 后一位数
n=当前位的数值
i=当前第几位数字
id_length 数据总长度
1532 4
xxx 4 个位有4 >n:153 4<=n:153+1 i=3
xx 4 x 十位有4 >n:15*10 4<n:(15+1)*10 4==n:15*10 + i=2
比如说1542 十位有4 比如说1545 十位有4
因为个位的2<4:15*10+0 因为个位的5>=4:15*10+1
x 4 xx 百位有4 >n:(int(id[i-1]))* 10 <n:(int(id[i-1])+1)* 10**(id_length-i-1) i=1
4 xx 千位有4 >=n: 10**(id_length-1) <n:0 i=0
可以把问题抽象，假设是1532，那么就是抽象成abcd的4个盒子（长度为4，四位数）
每个盒子分别可以放置若干个小球：
a:0，1
b:0-5
c:0-3
d:0-2
按照这个思路写也许会更简单（但本质上和前面那个算法是一样的，便于理解吧）
规律算法不超时算法代码
其实可以更精简一点的，但是为了方便理解，所以就把一些功能单独写成函数，方便大家理解。
#196409
ab = int(input())
symbol = int(input())
sushu_list=[]#素数列表，空间换时间
def is_prime(n):
if n in sushu_list:
return True
if n < 2 or n % 2 == 0 or n % 3 == 0:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
else:
sushu_list.append(n)
return True
for i in range(2, int(ab ** 0.5) + 1):
a = max(i, ab // i)
b = min(i, ab // i)
if a * b == ab and is_prime(a) and is_prime(b):
break
print("WHUT{}{}".format(a, b))
id = str(a) + str(b) # 997197
num = 0
id_length=len(id)
#输入id和i,返回得到第i位左边的数
def getLeft(id, i):
if i == 0: # 理论上不应该有i==0，必须要从第1位数开始才会有前面的数，第0位数前面是没有其他数的！
return 0
return int(id[:i - 1 + 1])
'''
输入id和i
返回得到第i位右边的数
'''
def getRight(id, i):
if i == len(id) - 1: # 同上理
return 0
return int(id[i + 1:])
'''
输入id和i
返回得到第i位数
'''
def getI(id, i):
return int(id[i])
for i in range(0, id_length): #
if i == 0:
if int(id[i]) > symbol: # 如果最高位大于本数，那么后面的数可以随便填写
num += 10 ** (id_length - 1)
else: # 最高位小，那么就是0
num += 0
elif i == id_length - 1: # 如果末尾，前面所有均可
num += int(id) // 10
if getI(id, i) >= symbol:
num += 1
else:
if getI(id, i) > symbol:
addition = (getLeft(id, i) + 1) * 10 ** (id_length - i - 1)
elif getI(id, i) == symbol:
addition = (getLeft(id, i)) * 10 ** (id_length - i - 1)+getRight(id, i)+1
else:
addition = (getLeft(id, i)) * 10 ** (id_length - i - 1)
num = num + addition
print(num)
超时的基础版本代码
ab = int(input())
x = input()
sushu_list=[]
def is_prime(n):
if n in sushu_list:
return True
if n < 2 or n % 2 == 0 or n % 3 == 0:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
else:
sushu_list.append(n)
return True
for i in range(2, int(ab ** 0.5) + 1):
a = max(i, ab // i)
b = min(i, ab // i)
if a * b == ab and is_prime(a) and is_prime(b):
break
id = str(a) + str(b) # 997197
num = 0
for i in range(0,int(id)+1):
y=str(i).count(x)
if y == 1 and i % 10 == x: # 末尾是数字 152 3 ---->3出现了152次
num = num + y//10
num = num + y
print("WHUT{}{}".format(a, b))
print(num)
总结
大家喜欢的话，给个👍，点个关注！给大家分享更多有趣好玩的Python习题！
版权声明：
发现你走远了@mzh原创作品，转载必须标注原文链接
Copyright 2022 mzh
Crated：2022-3-1
欢迎关注 『Python习题』 系列，持续更新中
欢迎关注 『Python习题』 系列，持续更新中
【更多内容敬请期待】
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）