【題目描述】

創(chuàng)新互聯(lián)是專業(yè)的徐匯網(wǎng)站建設(shè)公司，徐匯接單;提供成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、成都外貿(mào)網(wǎng)站建設(shè)公司,網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行徐匯網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

Write an algorithm which computes the number of trailing zeros in n factorial.

設(shè)計(jì)一個(gè)算法，計(jì)算出n階乘中尾部零的個(gè)數(shù)。

【題目鏈接】

http://www.lintcode.com/en/problem/trailing-zeros/

【題目解析】

傳統(tǒng)解法是首先求出n!，然后計(jì)算末尾0的個(gè)數(shù)。（重復(fù)÷10，直到余數(shù)非0）該解法在輸入的數(shù)字稍大時(shí)就會導(dǎo)致階乘得數(shù)溢出，不足取。

O（logn）解法：一個(gè)更聰明的解法是考慮n!的質(zhì)數(shù)因子。后綴0總是由質(zhì)因子2和質(zhì)因子5相乘得來的。如果我們可以計(jì)數(shù)2和5的個(gè)數(shù)，問題就解決了?？紤]下面的例子：

n = 5: 5!的質(zhì)因子中 (2 * 2 * 2 * 3 * 5)包含一個(gè)5和三個(gè)2。因而后綴0的個(gè)數(shù)是1。

n = 11: 11!的質(zhì)因子中(2^8 * 3^4 * 5^2 * 7)包含兩個(gè)5和三個(gè)2。于是后綴0的個(gè)數(shù)就是2。

我們很容易觀察到質(zhì)因子中2的個(gè)數(shù)總是大于等于5的個(gè)數(shù)。因此只要計(jì)數(shù)5的個(gè)數(shù)就可以了。那么怎樣計(jì)算n!的質(zhì)因子中所有5的個(gè)數(shù)呢？一個(gè)簡單的方法是計(jì)算floor(n/5)。例如，7!有一個(gè)5，10!有兩個(gè)5。除此之外，還有一件事情要考慮。諸如25，125之類的數(shù)字有不止一個(gè)5。例如，如果我們考慮28!，我們得到一個(gè)額外的5，并且0的總數(shù)變成了6。處理這個(gè)問題也很簡單，首先對n÷5，移除所有的單個(gè)5，然后÷25，移除額外的5，以此類推。

【參考答案】

http://www.jiuzhang.com/solutions/trailing-zeros/

網(wǎng)站標(biāo)題：Lintcode2TrailingZerossolution題解
瀏覽地址：http://www.rwnh.cn/article30/jisgpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供、品牌網(wǎng)站制作、網(wǎng)站策劃、品牌網(wǎng)站建設(shè)、Google、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)