基础数学的应用–POJ1423

原创文章,转载请注明出处.转载自: Li Haifeng's Blog
本文链接地址: 基础数学的应用–POJ1423

方法1:


      POJ1423题目的意思是给出一个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) ;

    位数=CEIL(log10(n!))


方法2:


    直接利用《计算机程序设计艺术》所给出的公式


CEIL(log10(n!) = log10(sqrt(2 * pi * n)) + n * log10(n / e))


From Li Haifeng's Blog, post 基础数学的应用–POJ1423

Post Footer automatically generated by wp-posturl plugin for wordpress.

分享到: