歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

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;
    }
}

Copyright © Linux教程網 All Rights Reserved