摘要: 階乘是個(gè)很有意思的東西,可能很多朋友看到關(guān)于他的計(jì)算就怕了,其實(shí)沒什么,看完下面兩個(gè)問題您應(yīng)該有低了。
1. 給定一個(gè) N ,求出N!末尾有多少個(gè)零,比如 N=10,N!=3628800,N!末尾有兩個(gè)零。
2. 求N!的二進(jìn)制表示中最低為1的位置,比如 11010010, 最低為1的位置為2。
問題一解法:
在上一個(gè) blog 中介紹的子數(shù)組乘積最大值的問題中,有朋友考慮到溢出的問題,在這個(gè)問題中,我們從那些數(shù)相乘能得到10這個(gè)命題開始思考。比如N!=K×10m那么N!后面就有m個(gè)零。這個(gè)問題轉(zhuǎn)化為將N!進(jìn)行分解,如N!=2a×3b×5c 很顯然 10=2×5,那么零的個(gè)數(shù)m=min(a,c), 一個(gè)數(shù)能夠被2整除的機(jī)率比5要大很多因此 m=c,因此轉(zhuǎn)化為求 c的問題,具體算法如:
閱讀全文