//转载请写上本帖链接: http://www.wutianqi.com/?p=167 //及【C++奋斗乐园/ACM乐园】
/**************************************** ID: POJ 1423 Big Number 题目地址： http://acm.pku.edu.cn/JudgeOnline/problem?id=1423 My Name: Tanky_Woo My Website: C++奋斗乐园|C++学习|算法学习|ACM/ICPC学习 Website Link: http://www.cpply.com/
My BBS: C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛 BBS Link：http://www.cppleyuan.com/
My Blog：www.wutianqi.com 豆瓣小组：http://www.douban.com/group/cppleyuan/ QQ:17611904 QQ群：C++奋斗乐园①群：19333724（满） ②群：23840480 (满） ③群：17314377 ④群：23829384 *****************************************/ 解题思路： 两种解法 1：1+lg(1)+lg(2)+..+lg(n) 2:strling公式。
方法一： 分析： 题目的意思是给出一个N，问N!的数字有多少位。对于这种题目，我们首先想到的是使用高精度乘法的方法模拟，最后在看看有多少位，但是这道题目的数据庞大，达10^7，高精度模拟显然不行。因此我们必须另外想方法。 要知道一个数字的位数是多少，我们可以用log10函数求得。例如，对于一个数，N=10，10!=3628800，而log10(3628800)=6.559763033，那么只要将这个数向上取整，就是7，就是10!的位数。当然，直接算log10(10!)是不可能的，但是根据对数的加法的性质，我们有log10(10!) = log10(123.....910)=log10(1) + log10(2) + log10(3) + ... + log10(9) +log10(10)，这样的话，即使是10^7，我们也可以对其直接进行log10的函数计算。至于向上取整，我们有另外一个函数，其原形double ceil(double)。有这个函数我们可以很方便的对一个浮点数向上取整。 问题又来了，这道题目给出的限时是1000ms。假如对于给出的每一个数据，我们都慢慢地将它从log10(1) 慢慢加到log10(N)，绝对会超时。因为里面有大量重复的运算，例如log10(1)，如果有100组数据，那么它的值就会被计算100次。于是，我们想到，能否把所有计算过的log10值保存起来，然后若遇到重复的，就从这个结果数组里面提取就可以了，不用再计算。这个方法很好，但是题目给出的数据规模比较大，开一个10^7大的double数组，绝对会Memory Excceed Limit。那么，既然如此，我们应该用什么方法来计算呢？ 假设问题给出的C组数据，是从小往大排列的，例如，给出三个数据，10，20，30，那么我们可以想到，计算log10(20!)的时候，我们是可以利用long10(10!)的结果。因为： log10(10!) = log10(1) + log10(2) + log10(3) + ... + log10(9) +log10(10) log10(20!) = log10(1) + log10(2) + log10(3) + ... + log10(9) +log10(10) + log10(11) + log10(12) +... +log10(19) + log10(20) 容易看出： log10(20!) = log10(10!) + log10(11) + log10(12) +... +log10(19) + log10(20) ; 同理： log10(30!) = log10(10!) + log10(21) + log10(22) +... +log10(29) + log10(30) ;
也就是说，我们只需要保存之前的那个数的运算结果。这种方法，有人就说是DP，但是我觉得这算是记忆化搜索吧。 题目没有说给出的数据是有序的，但是我们可以通过排序使之有序。至于排序，那么当然是系统的qsort()函数了。我解题时定义了一个结构体： typedef struct { int num; int id; double result; } data; 其中，num是给出的N，result保存的是log10(N!)，而id则记录这个数据输入时的顺序。因为我们输出答案时还是要按回之前输入的顺序输出的。因此输入时的顺序不能丢弃。 另外要注意，log10(1) = 0，但是1!的位数是1，这个要在输出时进行特判。还有，这道题提交时，若语言选择GCC，是会超时的。但是选择C，通常500ms都不用就出结果了。难道VC的最优化编译真是那么恐怖？我极度怀疑是GCC的math库的log10函数写得不好，导致耗费的时间长，从而超时。
#include
#include
#include
int cmp_num(const void *, const void *);
int cmp_id(const void *, const void *);
typedef struct
{
int num;
int id;
double result;
} data;
data table[100];
int main()
{
int n, i, j;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &table[i].num);
table[i].id = i;
}
qsort(table, n, sizeof(table[0]), cmp_num);
table[0].result = 0.0;
for (j = 1; j <= table[0].num; j++)
table[0].result += log10((double)j);
for (i = 1; i < n; i++)
{
table[i].result = table[i-1].result;
for (j = table[i-1].num + 1; j <= table[i].num; j++)
table[i].result += log10((double)j);
}
qsort(table, n, sizeof(table[0]), cmp_id);
for (i = 0; i < n; i++)
{
if (table[i].num == 1)
printf("1\n");
else
printf("%.0lf\n", ceil(table[i].result));
}
return 0;
}
int cmp_num(const void *a, const void *b)
{
return (*(data *)a).num - (*(data *)b).num;
}
int cmp_id(const void *a, const void *b)
{
return (*(data *)a).id - (*(data *)b).id;
}
方法二：
分析：
【Stirling公式】
lim(n→∞) √(2πn) * (n/e)^n / n! = 1
也就是说当n很大的时候,n!与√(2πn) * (n/e) ^ n的值十分接近
这就是Stirling公式.
Stirling公式的意义在于:当n足够大之后n!计算起来十分困难,
虽然有很多关于n!的不等式,但并不能很好的对阶乘结果进行估计,
尤其是n很大之后,误差将会非常大.但利用Stirling公式可以将阶乘转化成幂函数,
使得阶乘的结果得以更好的估计.而且n越大,估计得就越准确.
#include
#include
using namespace std;
const double e = 2.7182818284590452354, pi = 3.141592653589793239;
double strling_digits_num(int n)
{
return log10(2*pi*n)/2.0+n*(log10(n/e)); //0ms
//return log10( sqrt( 2 * pi * n ) ) + n * log10( n / e ); //16ms
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
double m=0;
m=strling_digits_num(n);
int answer=(int)m;
//注意！！！！10的n次方有n+1位数字
answer++;
cout<<answer<<endl;
}
system("pause");
return 0;
}