首页 ›存档› 技术 › 查看内容

Python求解进制问题（阿里巴巴2015笔试题）

2018-3-30 13:00 |来自: 互联网 363 0

摘要: 问题描述：用十进制计算30的阶乘，然后把结果转换成三进制表示，那么该进制表示的结果末尾会有多少个连续0？解析：作为笔试题的话，要想按照题意先把阶乘结果计算出来再转换成三进制最后再数0的个数，时间肯定来不 ...

问题描述：用十进制计算30的阶乘，然后把结果转换成三进制表示，那么该进制表示的结果末尾会有多少个连续0？

解析：作为笔试题的话，要想按照题意先把阶乘结果计算出来再转换成三进制最后再数0的个数，时间肯定来不及。也就是说，应该是有更简单的方法。以我们最熟悉的十进制为例，一个数乘以10相当于左移1位而右边补0；了解二进制计算的朋友们应该知道，对一个二进制数乘以2相当于左移1位而右边补0。恭喜，这对于任意素数进制都是成立的。也就是说，把从1到30的整数简单因数分解一下，看看有多少个3，那么题目中最终计算结果末尾就有多少个0。

下面的代码有4个函数，其中第二个函数调用了第一个函数，使用的是传统笨办法；第四个函数调用了第三个函数，使用的上面描述中的第二个方法。

from functools import reduce
from operator import mul
from random import randrange, choice

def int2base(n, base):
'''把十进制整数n转换成base进制'''
result = []
div = n
#除基取余，逆序排列
while div != 0:
div, mod = divmod(div, base)
result.append(mod)
result.reverse()
result = ''.join(map(str, result))
#变成数字，返回
return eval(result)

def zeros1(n, base):
'''n!转换成base进制后，最后有多少个连续0'''
#计算n!，并转换成base进制
fac_n = str(int2base(reduce(mul, range(1, n 1), 1), base))
#从后往前遍历，查找第一个不是0的位置
length = len(fac_n)
for i in range(length-1, -1, -1):
if fac_n[i] != '0':
return length-i-1

def bases(n, base):
'''计算n分解因数后有几个base相乘'''
num = 0
while n簊e == 0:
num = 1
n = n // base
return num

def zeros2(n, base):
'''从1到n的整数中，所有数字因数分解后共有多少个base，n!转换成base进制后最后就有多少个连续0'''
return sum(bases(i, base) for i in range(1, n 1) if i簊e == 0)

#随机测试，验证结果
for _ in range(300000):
n = randrange(5, 50)
base = choice((2, 3, 5, 7))
if zeros1(n, base) != zeros2(n, base):
print('Error:', n, ':', base)

原题答案为14。

代码看不懂的地方随时可以留言，更欢迎发现和指出代码中可能存在的bug！

本文转载于微信公众号: Python小屋(Python_xiaowu)，更多微信文章请扫描关注公众号:

声明：文章版权归原作者所有部分文章转自互联网如有侵权请联系 [邮箱地址] 删除

路过

雷人

握手

鲜花

鸡蛋

收藏分享邀请

上一篇：宇宙最强 IDE 将迎来新版，Opera 再提速｜软件周刊下一篇：【源码】如何用python轻松破解wifi密码

Python求解进制问题（阿里巴巴2015笔试题）

相关分类