首页 > 其他 > 详细

阶乘位数

时间:2020-03-29 10:28:55      阅读:62      评论:0      收藏:0      [点我收藏+]

昨天校赛模拟赛考了个题,不会这个知识点还真做不出来。。。。

技术分享图片

 

 

1. O(n)解法 , n 为数的大小:

log10(n!)=log10(1*2*3…*n)=log10(1)+log10(2)+…+log10(n)+1

即对log10(n!)的值取整加1就是n!的位数。

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 int main(){
 5     int n;
 6     double d=0;
 7     cin>>n;
 8     for(int i=1;i<=n;i++)    {
 9         d+=log10(double(i));
10     }
11     cout<<"n阶乘的位数位: "<<(int)(d+1)<<endl;
12     return 0;
13 }

 

效率太慢,肯定超时。

 

2. O(1)解法,近似计算的方法,斯特林公式。n!近似等于sqrt(2*pi*n) * (n/e)^n

#include <iostream>
#include <cmath>
using namespace std;
int main(){
    int t;
    cin >> t;
    while (t--) {
        int n;
        double d = 0;
        cin >> n;
        if( n == 1 || n == 0){
            d = 1;
        }else{
            d = log10(double(2 * M_PI * n))/2 + n * log10(double( n / M_E));
        }
        cout << (int)ceil(d) << endl;
    }
    return 0;
}

阶乘位数

原文:https://www.cnblogs.com/popodynasty/p/12590845.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!