n的階乘後面有多少個零?

2021-03-01 最簡信息學

階乘是基斯頓·卡曼（Christian Kramp，1760～1826）於 1808 年發明的運算符號。

 

一個正整數的階乘（factorial）是所有小於及等於該數的正整數的積，規定0的階乘為1。自然數n的階乘寫作n!。

 

即n!=1×2×3×...×(n-1)×n。階乘亦可以遞歸方式定義：0!=1，n!=(n-1)!×n。

 

給你一個非負整數n，要你計算階乘n!的結果末尾有幾個 0。比如說輸入n = 5，因為5! = 120，末尾有一個 0。

 

我們先來分析一下末尾的 0 從哪裡來的？

 

首先，兩個數相乘結果末尾有 0，一定是因為兩個數中有因子2 和 5，因為 10 = 2x 5。

 

這樣，問題就轉化成：n!可以分解出多少個因子2 和 5？

 

比如說n = 25，那麼25!最多可以分解出幾個 2 和 5 相乘？這個要看分解出幾個因子5，因為每個偶數都能分解出因子 2，因子 2 肯定比因子 5 多，2足夠用。

 

現在，問題轉化為：n!最多能分解出多少個因子5？

下面直接給出計算機算法，你也可以完全用筆算。

 

int how_many_zeros(int n)

{

  int d= 5;

  int ans = 0;

  while (d < n) {

    ans += n / d;

    d *= 5;

  }

  return ans;

}

 

不難吧，大家分析一下時間複雜度吧。

相關焦點

  • 在數學中,零的階乘為什麼等於1?
    對階乘進行解析延拓後，就能得到著名的伽馬函數，我們根據伽馬函數，就可以得到"0！=1"。階乘階乘是指所有小於以及等於某個數的正整數之積，記為：n！=1×2×3×……×n；在排列組合中我們經常遇到階乘運算，比如5個人按照順序進行排隊的話，就有「5！=120種」排列方法。按照階乘的定義，我們很容易得出這麼一個結論：（n+1）!=(n+1)*n!，其中n≥1且為整數；至於n=0的情況，超出了階乘的定義範圍，但是我們為了讓上面式子繼續成立，我們強行把n=0帶進去有：（0+1）！
  • Python編程案例:計算自然數n的階乘
    阿萌又接到一個新的編程任務，要求用Python編寫一個計算自然數n階乘的程序，用於學生利用計算機來計算n的階乘。阿萌梳理了一下編程要求，他認為程序需要實現下面這些功能：程序啟動後，程序在Shell窗口輸出提示信息「請輸入一個自然數，輸入quit可退出程序：」，學生輸入一個自然數，程序計算自然數的階乘，並將計算結果輸出到Shell窗口。程序再次輸出「請輸入一個自然數：」，等待學生的下次輸入。
  • 為什麼規定0的階乘為1?
    階乘(factorial)是基斯頓·卡曼(ChristianKramp，1760～1826)於1808年發明的運算符號。
  • n很大時n的階乘如何計算?斯特靈公式幫你解決一切
    斯特靈公式(Stirling's formula)是一條用來取n階乘近似值的數學公式。一般來說，當n很大的時候，n階乘的計算量十分大，所以斯特靈公式十分好用；而且，即使在n很小的時候，斯特靈公式的取值已經十分準確。
  • 滿天繁星之謎:天上星星有多少?大約3後面23個零
    滿天繁星之謎：天上星星有多少？大約3後面23個零新聞中心-中國網 news.china.com.cn　　　時間： 2013-01-15　　　發表評論>> 新華網北京12月3日電 人們常說，滿天繁星。
  • 用java計算一個數的階乘原來這麼簡單!
    for循環是一個很強大的知識點，我們會經常使用，所以今天再講一個與for循環有關的代碼，那就是計算一個數的階乘。階乘想必大家都知道，一個數的階乘就等於這個數乘所有小於它的正整數，公式也就是：n！=1x2x3x……x(n-1)xn。雖然說這是一個很簡單的知識，但是我們還是用Java來試著編寫一下代碼，鍛鍊一下我們的編程思維。
  • ...自主招生 階乘 藻類 exp sinh cosh 招辦 雪晶 染色劑-長三角...
    用四個0算24點難倒了一片考生　　一位考生向記者介紹了這道令自己啞口無言的神題：給你四個0，你怎麼算出24點？「四個零怎麼能算出這麼大的數字？當時我就愣住了，覺得這不可能完成。」後來他想到了可能要用正弦餘弦這樣的三角函數來做，可算了半天，還是沒算出來。另一位來自山東的考生想到了可能要用特殊的方程式來解決，但是具體怎麼算，試來試去只能放棄。
  • 一行Python代碼寫階乘函數
    背景我以前用Dart寫過一行的階乘函數：fact(double n) => n < 0 ? throw ('n must be bigger than 0') : n == 0 ?1 : n * fact(n - 1);現在突（xián）發（zhe）奇（méi）想（shì），用Python寫。貌似網上還沒有這樣的例子，所以我就發出來了。要求使用一行代碼編寫函數。調用方式為fact(x)，其中x為要求階乘的數。不得使用分號以變相湊成一行。
  • LabVIEW編程實例:計算階乘,學習for循環+移位寄存器+遞歸調用
    階乘定義非負整數n的階乘簡記為n!，在數學上定義為所有小於等於該數的正整數的乘積，並且定義0的階乘等於1，用公式表示為：n!=1×2×3×……×(n-1)×n對於n!也可以用遞歸方式定義為如下形式：n!=(n-1)!×n，且0!
  • 自然數之和1+2+3+……+n等於負1/12?蘊含著什麼秘密
    而在處理黎曼猜想的過程中，出現了一個副產品，就是這個式子，1+2+3+……+n=-1/12，即全體自然數的和等於負的十二分之一。這個式子從出現到今天，一直都引起著人們廣泛的興趣和關注，因為人們都覺得這不尋常的式子後面，也許隱藏著數學裡的大秘密。按人們正常的邏輯，自然越往後加，越趨於無窮大，數學上確實也是這樣，無論是按數列去計算多項和還是按級數算，得到的都是一個發散的結果，無窮大。
  • 為什麼0的階乘等於1
    為什麼0的階乘等於1？看了很多大神的論證過程，邏輯嚴謹，忠於學術，又勤奮。但感覺都沒啥說服力啊，反正我也看不懂。。。。。。
  • 學Python編程為什麼會對學好數學有幫助呢?
    現在我們做個簡單的乘法運算，我們先從2開始：先做2X1運算，運算的值是2；再做3X2X1運算，運算的值是6；繼續做4X3X2X1運算，運算的值是24；再做5X4X3X2X1運算，運算的值是120；一直到nX(n-1)X(n-2)X3X2X1的運算，這裡的n是指自然數1、2、3、4、5、6、……類似上面的運算也稱為階乘運算
  • π是個無理數,小數點後面會不會出現連續3個0或者更多的情況呢?
    π是個無理數，小數點後面會不會出現連續3個0的情況或者更多呢？看看網友們是怎麼回復的吧：網友1：圓周率π是個無理數，而且它還是一個超越數。這個計算可以做到非常高的精度，如果你有一臺超級計算機，只要你的內存不會溢出，你可以計算π到五百億位。這樣，我們就得到了一個數組，也可以理解為一個字符串。這個字符串裡有非常多的數字。其次，我們使用哈希算法來檢驗這個字符串裡有沒有000這樣的組合。這個在計算機編程裡是有的。很多講信息學奧林匹克的書都講了這個算法。
  • 47個互不相同的非零自然數之和為2000,問最少有多少個偶數
    47個互不相同的非零自然數之和為2000,問最少有多少個偶數？這些偶數的和是多少？分析：由於是互不相同的非零自然數之和，又要讓偶數個數最少，那我們當然希望是偶數是0個最好了。2000是個偶數，不過根據和的奇偶性，47個奇數相加，奇數個奇數相加和一定是奇數。所以這47個數中肯定會有偶數。所以說會有偶數個奇數。
  • 二次剩餘——第一個零知識證明協議的歷史背景與證明方法|火星技術帖
    在《不可思議的零知識證明》一文中，我們通過三個小故事介紹了零知識證明裡面的重要概念：紅綠色盲遊戲（交互和隨機性），阿里巴巴洞穴（模擬器），旅行中的數學家（非交互和公開驗證）。但從直覺到嚴格的定義、證明之間，需要一些新的工具和方法論。這些由 GMR[85] 第一次給出，並且在之後得到廣泛的研究和推廣。
  • 科學家給太陽系最重小行星估值：用美元計算 1後面19個零
    太陽系最重小行星價值10000000000000000000美元【科學家給太陽系最重小行星估值：用美元計算 1後面19個零】1852年3月17日，義大利天文學家安尼巴萊·德·加斯帕裡斯發現了一顆小行星，並將其命名為「靈神星」。