問題描述:用十進制計算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;
}
}