笔试面试题目：1000的阶乘问题

笔试面试题目：1000的阶乘问题

引用

CSDN

1.

https://blog.csdn.net/stpeace/article/details/108921577

大数阶乘问题，是很常见的，来看一下T公司的面试题目：

问题一：1000的阶乘末尾有多少个0？

直接递归计算吗？有点天真了。1000的阶乘，是一个非常大的数字，得想其它办法了。注意：要求的是1000的阶乘末尾的0的个数，而不是求1000的阶乘。

很显然，从分解质因数的过程来看，结尾的0必然是2和5的乘积，而且在阶乘中，5是稀缺值，而2是富余值，所以，只需要知道质因数中5的个数就行了。我们以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(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

所以：

= [1000/5] + [1000/25] + [1000/125] + [1000/625] + [1000/3125]

至于程序，给个递归版本吧：

func getNum(n int) int {
    if n < 5 {
        return 0
    }
    return n/5 + getNum(n/5)
}
fmt.Println(getNum(1000))

结果：249. 可见，1000的阶乘末尾有249个0.

问题二：1000的阶乘有多少位数？

直接递归计算吗？有点天真了。我们来看下如下规律：

设f(x)为x的数位个数，[x]为x向下取整的值，则有：

= [lg(1 * 2 * 3 * ... * n)] + 1
= [lg1 + lg2 + lg3 + ... + lg(n)] + 1

至于程序，那就很简单了：

import "math"
var f float64
for i := 1; i <= 1000; i++ {
    f = f + math.Log10(float64(i))
}
f = f + 1
fmt.Println(int(f))

结果：2568. 可见，1000的阶乘有2568位。

问题三：1000的阶乘的值是多少？

直接递归计算吗？有点天真了。 还是用字符串来做吧：

int multi(char a, char b) {
    return (a - '0') * (b - '0');
}
void strMulti(char *a, char *b, char *c) {
    int maxLen = lenA + lenB;
    int *p = new int[maxLen];
    memset(p, 0, maxLen * sizeof(int));
    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] %= 10;
    }
    for(pTmp = p; pTmp < s + maxLen; pTmp++) {
        *pTmp = *pTmp + '0';
    }
    delete[] p;
}
void factorial(int n, char *str) {
    char a[10000], b[10000];
    strcpy(a, "1");
    for(i = 2; i <= n; i++) {
        snprintf(b, sizeof(b), "%d", i);
        strMulti(a, b, a);
    }
    strcpy(str, a);
}
char str[10000];
factorial(1000, str);
cout << str << endl << endl;

结果是：

可以看到，1000的阶乘有2568位，且最后有249个0.

关于1000的阶乘，就说到这里了。遇到问题，要灵活应变，从具体到抽象，抓住本质。