POJ 1423 Big Number

//转载请写上本帖链接: 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(1*2*3…..*9*10)=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越大,估计得就越准确.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 #include<iostream>
#include<cmath>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注