首页 > ACM题库 > HDU-杭电 > HDU 1018 Big Number-高精度-[解题报告] C++
2013
11-26

HDU 1018 Big Number-高精度-[解题报告] C++

Big Number

问题描述 :

In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a number, you have to determine the number of digits in the factorial of the number.

输入:

Input consists of several lines of integer numbers. The first line contains an integer n, which is the number of cases to be tested, followed by n lines, one integer 1 ≤ n ≤ 107 on each line.

输出:

The output contains the number of digits in the factorial of the integers appearing in the input.

样例输入:

2
10
20

样例输出:

7
19

分析:

第一种方法:

N!=1*2*3….*n 要求位数我们很自然想到对一个数取对数,log10(n!)=log10(1)+ log10(2) +log10(3)…+log10(n)
第二种方法:
关于斯特林数,有斯特林公式:lnN!=NlnN-N+0.5*ln(2*N*pi;也很容易得出其位数。

 

#include<stdio.h>
#include<math.h>

int main()
{
    int n,i,m;
    double sum;
    scanf("%d",&n);
    while(n--)
    {
       sum=0;
       scanf("%d",&m);
       for(i=1;i<=m;i++)
           sum+=log10((double)i);
       printf("%d\n",(int)sum+1);
    }
    return 0;
}

第二种:

#include<stdio.h>
#include<math.h>

#define e 2.7182818284590452354
#define pi acos(-1.00)

int main()
{
    int n,i,m,sum;
    scanf("%d",&n);
    while(n--)
    {
       scanf("%d",&m);
       sum=(int)(1.0/2.0*log10(2.0*pi*m)+1.0*m*log10(m/e)+1);
       printf("%d\n",sum);
    }
    return 0;
}

 


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  4. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  5. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.