Python求解进制问题(阿里巴巴2015笔试题)

问题描述:用十进制计算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%base == 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%base == 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)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-02-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

字符串展开(递归)- HDU 1274

常用纱线的品种一般不会超过25种,分别可以用小写字母表示不同的纱线,例如:abc表示三根纱线的排列;重复可以用数字和括号表示,例如:2(abc)表示abcabc...

10520
来自专栏小樱的经验随笔

KMP算法学习(详解)

kmp算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。不过由于其难以理解,所以在很长的一段时间内一直没有搞懂。虽然网上有很多资料,但是鲜见好的博客能简...

34050
来自专栏人工智能LeadAI

为什么算法容易忘记之插入排序

在学习常用的排序算法时,常有这样的感觉,一看就懂,过眼就忘。原因在于没有将排序的基本思想与代码中各个循环控制变量的意义联系起来进行理解记忆。 插入排序 首先,我...

36650
来自专栏小古哥的博客园

秒懂JS对象、构造器函数和原型对象之间的关系

学习JS的过程中,想要掌握面向对象的程序设计风格,对象模型(原型和继承)是其中的重点和难点,拜读了各类经典书籍和各位前辈的技术文章,感觉都太过高深,花费了不少时...

34470
来自专栏编程

一起学Python:迭代器

迭代器 迭代是访问集合元素的一种方式。迭代器是一个可以记住遍历的位置的对象。迭代器对象从集合的第一个元素开始访问,直到所有的元素被访问完结束。迭代器只能往前不会...

23990
来自专栏Java与Android技术栈

借助Java 8实现柯里化借助Java 8实现柯里化柯里化的好处总结

在函数式编程中,函数的概念跟数学中函数的概念是一样的,类似于“映射”。高阶函数和柯里化是函数式编程的特性。

20020
来自专栏程序员互动联盟

【面试宝典】static 关键字

面试官:static关键字你了解吗?说一下你的认识。 小白:啊.....有点晕呀,这么宽泛的问题,我该从哪回答呢?头脑一片空白。让我想想...... 面试官:没...

37560
来自专栏前端进阶之路

JavaScript数据结构01 - 数组

PS:原始值是指固定而简单的值,存放在栈中的简单数据段,它们的值直接存储在变量访问的位置。

16030
来自专栏云霄雨霁

排序----归并排序

16000
来自专栏老九学堂

一分钟掌握C语言结构体常见方法

把结构体名称去掉,这样更简洁,不过也不能定义其他同结构体变量了——至少我现在没掌握这种方法。

20220

扫码关注云+社区

领取腾讯云代金券