學算法有錘子用? 請問億的階乘末尾幾個零?

如果有人問你, 計算機的能力已經這樣強了,算法有啥用?

你可以問他,一個億的階乘後面有幾個零? 這個問題不是正常計算能解決的,即使交給計算機也要花好長時間...

階乘

階乘是一種特殊的運算,随着數的增大, 計算量陡增

5! = 5 * 4 * 3 * 2 * 1 = 120

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800

15! = 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1307674368000

對于某數階乘 末尾有幾個零的問題, 稍加分析就會發現, 其實結果後面有幾個零,取決于因數能分解出多少個10, 而10的個數取決于分解出的因數5和因數2的個數,而因數2的個數遠多于因數5的個數,是以有多少個因數5, 就有多少個零!

• 5! 有一個因數5;
• 10! 有兩個因數5;
• 15! 有三個因數5;
• 20 ! 有四個因數5;
• 25 ! 有六個因數5;(25 可以分出兩個因數5);

把0的個數轉化為因數5的個數, 問題就簡單了很多, 求100000000!中因數5的個數,交給計算機能在毫秒級完成! 總共有24999999個零

一個億的階乘末尾有幾個零

class Solution {
    public static long trailingZeros(long n) {
    
        // 本質是求一共有多少個因數5
        
        // 記錄5的個數
        long count = 0L;
        
        /*
        temp的兩大作用:
        第一: 臨時存儲"5"的個數(随着每次的循環更新,會越變越少)
        第二: 控制循環(當temp降為0時, 終止循環)
        */ 
        long temp = n / 5;
        
        // 當temp耗盡時, 停止循環
        while (0 != temp){
            
            // 累加上次記錄的"5"的個數    
            count += temp;
            // 獲得第N 次擷取5的個數
            temp = temp / 5;
            
        }
        
        return count;
        
    }
};

class ZeroNum{
    
    public static void main (String[] args) {

        Solution sol = new Solution();
        // 求1億的階乘尾部用多少個零 100000000!
        long result = sol.trailingZeros(100000000);

        System.out.println("一億的階乘尾部有"+result+"個零");
    }
}

           

有了很厲害的算法，還需要計算機麼？當然需要！如果沒有計算機，即便給出階乘的結果，誰能保證一次就把零的個數，準确無誤的數出來？（正确答案是24999999個零）