大数阶乘问题,是很常见的,来看一下T公司的面试题目:
问题一:
1000的阶乘末尾有多少个0?
问题二:
1000的阶乘有多少位数?
问题三:
1000的阶乘的值是多少?
1000的阶乘末尾有多少个0?
直接递归计算吗?有点天真了。1000的阶乘,是一个非常大的数字,得想其它办法了。注意:要求的是1000的阶乘末尾的0的个数,而不是求1000的阶乘。
很显然,从分解质因数的过程来看,结尾的0必然是2和5的乘积,而且在阶乘中,5是稀缺值,而2是富余值,所以,只需要知道质因数中5的个数就行了。我们以26的阶乘为例:
26!= 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * ... * 25 * 26= 1 * 2 * 3 * 2*2 * 5 * 2*3 * 7 * 2*2*2 * 9 * 2*5 * 11 * ...3*5 * ... * 4*5 * ... * 5*5 * 2*13可见:其中有6个5,有充足的2,所以只需要看5的个数。易知,26的阶乘的末尾有6个0. 用阶乘计算器来看下,果然如此:
我们来讨论更一般的情况:
设f(x)是x中因数5的个数, [x]为x向下取整的值,则有:
f(n!)= f(1 * 2 * 3 * 4 * 5 * 6 * ... * n)= f(1 * 2 * 3 * 4 * 5 * 6 * ... * ([n/5]*5))= f(5 * 10 * ... * ([n/5]*5))= f(5*1 * 5*2 * ... * ([n/5]*5))= f(5^[n/5] * 1 * 2 * ... * [n/5])= [n/5] + f(1 * 2 * ... * [n/5])= [n/5] + [n/25] + f(1 * 2 * ... * [n/25])= [n/5] + [n/25] + [n/125] + f(1 * 2 * ... * [n/125])= [n/5] + [n/25] + [n/125] + [n/625] + ... + 0所以:
f(1000!) = [1000/5] + [1000/25] + [1000/125] + [1000/625] + [1000/3125]= 200 + 40 + 8 + 1 + 0= 249至于程序,给个递归版本吧:
package mainimport ( "fmt")func getNum(i int) int { if i < 5 { return 0 } return i/5 + getNum(i/5)}func main() { fmt.Println(getNum(1000))}结果:249. 可见,1000的阶乘末尾有249个0.
1000的阶乘有多少位数?
直接递归计算吗?有点天真了。我们来看下如下规律:
lg99 = 1.alg100 = 2lg101 = 2.blg999 = 2.clg1000 = 3lg1001 = 3.d设f(x)为x的数位个数,[x]为x向下取整的值,则有:
f(x)= [lg(x)] + 1f(n!)= f(1 * 2 * 3 * ... * n)= [lg(1 * 2 * 3 * ... * n)] + 1= [lg1 + lg2 + lg3 + ... + lg(n)] + 1至于程序,那就很简单了:
package mainimport ( "fmt" "math")func main() { f := float64(0) for i := 1; i <= 1000; i++ { f = f + math.Log10(float64(i)) } n := int(f) + 1 fmt.Println(n)}结果:2568. 可见,1000的阶乘有2568位。
1000的阶乘的值是多少?
直接递归计算吗?有点天真了。 还是用字符串来做吧:
#include <iostream>#include <cstring>#include <cstdio>using namespace std; int multi(char a, char b){ return (a - '0') * (b - '0');} void strMulti(char *a, char *b, char *c){ int lenA = strlen(a); int lenB = strlen(b); int maxLen = lenA + lenB; int *p = new int[maxLen]; memset(p, 0, maxLen * sizeof(int)); int i = 0; int j = 0; for(j = lenB - 1; j >= 0; j--) { for(i = lenA - 1; i >= 0; i--) { p[j + i + 1] += multi(b[j], a[i]); } } // 处理进位操作 for(i = maxLen - 1; i >= 1; i--) { p[i - 1] += p[i] / 10; p[i] = p[i] % 10; } int *s = p; // m位正整数和n位正整数相乘,结果的位数必然是(dqddg-1)位或者(dqddg)位 if(0 == p[0]) { p++; } int *pTmp = NULL; for(pTmp = p; pTmp < s + maxLen; pTmp++) { *c++ = *pTmp + '0'; } *c = ' '; delete s;} void factorial(int n, char *str){ int i = 0; *str = '1'; *(str + 1) = ' '; char b[5000] = {0}; for(i = 1; i <= n; i++) { snprintf(b, sizeof(b), "%d", i); strMulti(str, b, str); }} int main(){ char str[5000] = {0}; factorial(1000, str); cout << str << endl << endl; return 0;}结果是:
可以看到,1000的阶乘有2568位,且最后有249个0.
关于1000的阶乘,就说到这里了。遇到问题,要灵活应变,从具体到抽象,抓住本质。