Pku acm 1423 Big Number 解题报告----求n!的位数

发布于:2021-07-19 07:16:03

题目要求n!有几位,由于n最大可以到10^7,一般的方法是不可以的,然后推导以下公式:


n!=n*(n-1)*(n-2)*…..*1


N的位数=[lg(N)]+1;


所以:n!的位数=[lg(n*(n-1)*(n-2)*…..*1)]+1=[lgn+lg(n-1)+lg[n-2]+….+lg1]+1;


由于题目要计算很多数,所以如果每次都重新算会有很多重复,会超时,所以我们想办法保存中间的结果,最初的想法是开一个10^7的数组,把对应lgn+lg(n-1)+lg[n-2]+….+lg1结果全部存起来,会超过要求的空间,最后ac的办法是对输入的n个数字进行排序,然后每次计算出相应的lgn+lg(n-1)+lg[n-2]+….+lg1,保存起来,然后计算下一个lgn+lg(n-1)+lg[n-2]+….+lg1,排序采用快速排序。具体方法:


array存放输入的原始数组,如{20,10,80,70,60,40,50,30},sort临时存放array排序前和排序后的相应位置,初始化sort为{1,2,3,4,5,6,7,8},然后是快速排序,array sort 指针同时移动, 排序后array存放排序后的数组,如{10,20,30,40,50,60,70,80},排序后sort为{2,1,8,6,7,5,4,3},index[i]表示第i个输入现在的位置,排序后index为{2,1,8,7,6,4,5,3},循环计算每个array[i]对应的lg[i]+lg[i-1]+...+lg[1],存放在log中,最后输出即可。

带有详细注释的代码可以从
http://download.csdn.net/user/china8848/
获得。

相关推荐

最新更新

猜你喜欢