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

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

解析:作为笔试题的话,要想按照题意先把阶乘结果计算出来再转换成三进制最后再数0的个数,时间肯定来不及。也就是说,应该是有更简单的方法。以我们最熟悉的十进制为例,一个数乘以10相当于左移1位而右边补0;

了解二进制计算的朋友们应该知道,对一个二进制数乘以2相当于左移1位而右边补0。恭喜,这对于任意素数进制都是成立的。也就是说,把从1到30的整数简单因数分解一下,看看有多少个3,那么题目中最终计算结果末尾就有多少个0。

1.(Python实现)下面的代码有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)

2.Java实现第二种方法(第一种方法java实现估计代码太过累赘)

public class test {

public static void main(String[] args) {
        System.out.println(zero2(30,3));
    }

public static int bases(int n,int base){
        int num = 0;
        while(n % base == 0){
            num += 1;
            n = n / base;
        }
        return num;
    }

public static int zero2(int n,int base){
        int num = 0;
        for(int i=1 ; i < n+1 ; i++){
            if(i % base == 0){
                num += bases(i,base);
            }
        }
        return num;
    }
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/8540dbdd360fa219ea36e4880e8998de.html