求關於n的階乘結果後面有幾個零?如2016的階乘(網易的筆試選擇題)

NO IMAGE

文章的原地址:http://blog.csdn.net/zyh2525246/article/details/53697136

一、階乘數小的時候可以直接計算。

例如:求10!後面零的個數。很明顯結果為3628800。   0的個數為2個。

    20!結果為2432902008176640000,0的個數為4個。而這個時候已經達到19位數了。

    更大的數,如果再直接去求。顯然太麻煩了。

二、背後的規律

介紹一種求某個數階乘結果後面零的個數的方法。

首先,出現零的情況就是 5 的倍數乘以偶數。

但是出現0的個數就不一定了,2*5=10 出現一個0。4*25=100會出現2個0。8*125=1000出現3個0.依次類推。

大家不難發現規律所在。4*25可以分解成2*5*2*5,8*125可以分解為2*5*2*5*2*5……..

至於10,15,20 這些數 。 分解開,只會出現一個5,也就只會出現1個0。

至於50,75這些25的倍數,分解開,也只會出現2個5,與偶數相乘也只會出現2個0.

下面就是計算0的個數了。

上面也談到了,偶數乘以5會出現一個0,乘以5的平方會出現2個0,乘以5的立方會出現3個0.

那麼怎麼計算階乘裡存在多少個5的倍數,25的倍數,125的倍數呢。而且,有個問題還需要注意,25,125也是5的倍數,125也是25的倍數。

例如 求100!後面0的個數。

由上所說的方法,是5的倍數的數有16(除去25的倍數),是25的倍數的數有4個,結果應該為16*1 4*2=24個0.

我們也可以換一種思維,出現一個5就是一個0,那麼出現一個25就是2個0,如果5的倍數不排除25的倍數的話,每出現一個25的倍數,只加上1個0即可。

換句話說就是,0的個數就等於5的倍數的個數加上25的倍數的個數,即 20 4。

如果是求2016!後面0的個數呢?

同樣按照上面的方法。

5的倍數個數為:
 2016/5 = 403個

25的倍數個數為:
 403/5 = 80個 

125的倍數的個數為:80/5
= 16個

625的倍數的個數為: 16/5 = 3個。

所以可以得出2016!後面0的個數為:403 80 16 3 = 502個.

如何用程式碼又該如何實現呢?

很簡單,用一個簡單的迴圈就能解決,當然遞迴演算法更好。這裡我們就只貼迴圈的程式碼了。

Scanner scanner = new Scanner(System.in);
System.out.print(“請輸入階乘數:”);
int a = scanner.nextInt();
int
count = 0;
for (; 😉 {
a = a/5;
if (a == 0) {
break;
}else {
count = a;
}
}
System.out.println(“階乘結果後面的零的個數為:” count);

結果如下:

請輸入階乘數:2016
階乘結果後面的零的個數為:502

     

當然,重在思想,程式碼沒有什麼好說的。希望大家也學到了這個方法。雖然在在生活中用處不大,但是轉換思想的方法還是挺管用的。