用C++實(shí)現(xiàn)求N!中末尾0的個(gè)數(shù)的方法詳解
題目描述:
輸入一個(gè)正整數(shù)n,求n!(即階乘)末尾有多少個(gè)0? 比如: n = 10; n! = 3628800,所以答案為2
輸入描述:
輸入為1行,n(1≤n≤1000)
輸出描述:
輸出一個(gè)整數(shù)
樣例:
輸入:10
輸出:2
看到這個(gè)題,常規(guī)思路就是先把階乘算出來,再用算出來的結(jié)果求余,余數(shù)為0則個(gè)數(shù)加1,代碼如下:
#include<iostream> using namespace std; int main(void) { int n, m = 1; cin >> n; for (int i = n; i > 0; i--) { m = m * i; } int sum = 0; int t; for (int i = 0; m > 0; i++) { t = m % 10; m = m / 10; if (t != 0) //要是0前面的數(shù)字不是0,則直接結(jié)束 { cout << sum; return 0; } else { sum++; } } return 0; }
注意一點(diǎn),就是題目要求是算出末尾的0的個(gè)數(shù),而不是整個(gè)數(shù)字中有多少0,所以要注意當(dāng)余數(shù)不是0的時(shí)候就要結(jié)束代碼。
但是這樣做其實(shí)是不對的,因?yàn)槲覀冏⒁獾筋}目的輸入描述為n(1≤n≤1000),也就是說當(dāng)n很大的時(shí)候,就會(huì)越界,超出int表示的范圍。所以也就不能用這種方法進(jìn)行求解。
正確思路:我們先看一下末尾的0是怎么來的:末尾有0,就說明這個(gè)數(shù)可以被10整除,而再對10進(jìn)行因數(shù)分解,不難看出10=5*2,而5乘以任何一個(gè)偶數(shù),所得結(jié)果都會(huì)被10整除,所以問題就轉(zhuǎn)化為這個(gè)階乘里面含有多少個(gè)能被5整除的數(shù)字。當(dāng)然還要注意一點(diǎn),那就是25,125,625這三個(gè)數(shù)字,25本質(zhì)上是2個(gè)5(平方),125本質(zhì)上是3個(gè)5(立方),625本質(zhì)上是4個(gè)5(4次方),所以在算到這些數(shù)字的時(shí)候要把他們本身含有的多的5算進(jìn)去。
代碼如下:
#include<iostream> using namespace std; int main(void) { int n,sum=0; cin>>n; while(n) { sum=sum+n/5; n=n/5; } cout<<sum; return 0; }
到此這篇關(guān)于用C++實(shí)現(xiàn)求N!中末尾0的個(gè)數(shù)的方法詳解的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)求N!中末尾0的個(gè)數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++使用異或運(yùn)算實(shí)現(xiàn)交換兩個(gè)數(shù)的值
- C++如何判斷一個(gè)數(shù)字是否為質(zhì)數(shù)
- C++使用遞歸和非遞歸算法實(shí)現(xiàn)的二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)計(jì)算方法
- C++算法之在無序數(shù)組中選擇第k小個(gè)數(shù)的實(shí)現(xiàn)方法
- C++統(tǒng)計(jì)中英文大小寫字母、數(shù)字、空格及其他字符個(gè)數(shù)的方法
- C++求1到n中1出現(xiàn)的次數(shù)以及數(shù)的二進(jìn)制表示中1的個(gè)數(shù)
- c++統(tǒng)計(jì)文件中字符個(gè)數(shù)代碼匯總
- c++通過引用實(shí)現(xiàn)三個(gè)數(shù)字求最大值
- 利用C++的基本算法實(shí)現(xiàn)十個(gè)數(shù)排序
相關(guān)文章
spring aop實(shí)現(xiàn)用戶權(quán)限管理的示例
本篇文章主要介紹了spring aop實(shí)現(xiàn)用戶權(quán)限管理的示例,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-12-12MyBatis實(shí)現(xiàn)物理分頁的實(shí)例
這篇文章主要介紹了MyBatis實(shí)現(xiàn)物理分頁的實(shí)例,MyBatis使用RowBounds實(shí)現(xiàn)的分頁是邏輯分頁,有興趣的可以了解一下。2017-01-01logback配置中變量和include的應(yīng)用方式
這篇文章主要介紹了logback配置中變量和include的應(yīng)用方式,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-08-08通過實(shí)例學(xué)習(xí)Either 樹和模式匹配
這篇文章主要介紹了通過實(shí)例學(xué)習(xí)Either 樹和模式匹配,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,,需要的朋友可以參考下2019-06-06Java Callable接口實(shí)現(xiàn)細(xì)節(jié)詳解
這篇文章主要介紹了Java Callable接口實(shí)現(xiàn)細(xì)節(jié)詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-05-05