问题引入
这些天看到了有关1000的阶乘的问题,决定对这个问题做一个整理,方便日后观看。1000的阶乘有以下几个问题值得探讨:
1000的阶乘结果末尾有多少个01000的阶乘的值有多少位1000的阶乘的精确值是多少 下面对这三个问题进行研讨,并会给出相关代码 1000的阶乘结果后面有多少个0
1000个数每一个数都可以分解成几个质数的乘积,而能够产生0的最小的两个质数是2和5,所以我们只用知道1000里面有多少个5和多少个2,因为2的数量是远远多余5的,所以问题就变成了求解1000里面有多少个5。
1、首先5的个数是 1000/5 = 200;
2、如果分解成的质数有两个5,即包含55,这种结果要多出一个5,共 1000/25 = 40;(由于只有一个5的情况包含了一次有两个5的情况,所以这里只用算25的个数就行了,不用乘以2)
3、同理,对于555 共有 1000/125 = 8
4、对于5555 = 1000/625 = 1;
所以一共有 200+40+8+1 = 249个0;
1000的阶乘有多少位
这个我们值需要一点点数学知识就行了,假设结果是M,把这个数变成科学计数法为0.M*10n次方,这里的n显然就是M的位数,也就是得到的结果的位数。
所以我们可以有1234…1000 = 0.M10n次方,两边同时取对数,即
lg(123*…*1000) = lg(0.M)+n
n =int(lg(1)+lg(2)+…+lg(1000)-lg(M)=lg(1)+lg(2)+…+lg(1000)+1);
(因为n肯定是整数,而且-1<lg(0.M)<0,所以lg(0.M)只用取-1,然后把多余的会在int取整时去掉)
这里代码只用一个简单循环就行了。结果为2568
1000的阶乘精确值是多少
因为1000的阶乘的值特别大,所以没有一种数据类型可以来存储,所以我们用数组来存储,将结果的低位放在数组的开头,高位放在末尾,对于1-1000每个数都遍历一次数组。然后进行乘法和进位的处理。
/* * 例如1*2*3*4=24 那么数组中a[0]=4 a[1]=2 //将大数倒序装进数组 * 24*5 = 120 那么就是a[0]*5 = 20 a[1]*5=10 //每一位只能是0-9 * 所以需要进位 那么就是a[0]=20%10=0 * a[1]=a[1]+a[0]/10=12 * a[1] = a[1]%10=2 * a[2] = a[2]+a[1]/10 =1 * 就变成120了 * 关键在于对进位的控制 */
代码:
#include <iostream>#include <cmath>const int EXT = 5;//求数组的长度int length(int n){ double m = 0; for (int i = 1; i <= n; ++i) { m += log(i); } return int(m + 1);}//计算值void fact(int n){ //——n<=0——— if (n < 0) { std::cout << “error\n”; return; } else if (0 == n) { std::cout << 1; return; } //———construct————– int len = length(n) + EXT; short *num = new short[len]; short carry, sum; //———-init————- for (int i = 0; i < len; ++i) { num[i] = 0; } num[0] = 1; //———calc——— for (int i = 2; i <= n; ++i) { carry = 0; for (int j = 0; j < len; ++j) { sum = num[j] * i + carry; num[j] = sum % 10; carry = sum / 10; } } //———–end———— //———–output———- bool zero = true; for (int i = len – 1; i >= 0; –i) { if (zero) { if (0 != num[i – 1]) { zero = false; } } else { std::cout << num[i]; } } //———–destruct———– delete[] num;}int main(){ fact(1000); return 0;}
第二种方法:使用vector动态添加。
#include <iostream>#include <vector>#include <cmath>using namespace std;vector<int> nums;int len(int num){ int len = 0; while (num) { num /= 10; len++; } return len;}void cal(int n){ int carry; nums.push_back(1); for (int k = 2; k <= n; ++k) { carry = 0; for (int &num : nums) { num = num * k + carry; carry = (num / 10); num = (num % 10); } if (carry != 0) { int mod = 0; for (int i = 0; i < len(carry); ++i) { mod = (carry / int(pow(10, i))) % 10; nums.push_back(mod); } } } for (int i = nums.size() – 1; i >= 0; i–) { cout << nums[i]; }}int main(){ cal(1000); return 0;}
结果: