首页 > 代码库 > hdu--1018--水题-用下斯特林..
hdu--1018--水题-用下斯特林..
很水的一题...
计算阶乘的位数..
touch me
斯特林公式:
或更精确的
或
我一开始是不知道这个公式 所以用了自己的方法 就是简单利用下 log(x*y)=logx+logy==============log(1*2*3....*n)=log1+log2+log3+....+logn
看到一篇对于这个 介绍的不错的公式依据
/****************************************************这题要求n的阶乘的位数,如果n较大时,n的阶乘必将是一个很大的数,题中说1<=n<10000000,当n=10000000时可以说n的阶乘将是一个非常巨大的数字,对于处理大数的问题,我们一般用字符串,这题当n取最大值时,就是一千万个数字相乘的积,太大了,就算保存在字符串中都有一点困难,而且一千万个数字相乘是会涉及到大数的乘法,大数的乘法是比较耗时的,就算计算出结果一般也会超时。这让我们不得不抛弃这种直接的方法。再想一下,这题是要求n的阶乘的位数,而n的阶乘是n个数的乘积,那么要是我们能把这个问题分解就好了。在这之前,我们必须要知道一个知识,任意一个正整数a的位数等于(int)log10(a) + 1;为什么呢?下面给大家推导一下: 对于任意一个给定的正整数a, 假设10^(x-1)<=a<10^x,那么显然a的位数为x位, 又因为 log10(10^(x-1))<=log10(a)<(log10(10^x)) 即x-1<=log10(a)<x 则(int)log10(a)=x-1, 即(int)log10(a)+1=x 即a的位数是(int)log10(a)+1我们知道了一个正整数a的位数等于(int)log10(a) + 1,现在来求n的阶乘的位数:假设A=n!=1*2*3*......*n,那么我们要求的就是(int)log10(A)+1,而: log10(A) =log10(1*2*3*......n) (根据log10(a*b) = log10(a) + log10(b)有) =log10(1)+log10(2)+log10(3)+......+log10(n)现在我们终于找到方法,问题解决了,我们将求n的阶乘的位数分解成了求n个数对10取对数的和,并且对于其中任意一个数,都在正常的数字范围之类。总结一下:n的阶乘的位数等于 (int)(log10(1)+log10(2)+log10(3)+......+log10(n)) + 1根据这个思路我们很容易写出程序****************************************************/
---》稍微有点长 但讲得很细致
1 #include <iostream> 2 #include<math.h> 3 using namespace std; 4 5 #define PI 3.141592657 6 #define E 2.71828182845904523536028747135266250 7 8 int main() 9 {10 int t , n;11 double cnt;12 while( cin >> t )13 {14 while( t-- )15 {16 cin>>n;17 cnt = log10( sqrt( 2*PI*n ) ) + n * log10(n/E);18 cout << (int)(cnt+1) << endl;19 }20 }21 return 0;22 }
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 5 int main() 6 { 7 cin.sync_with_stdio(false); 8 int t , n; 9 double cnt;10 while( cin >> t )11 {12 while( t-- )13 {14 cnt = 0;15 cin >> n;16 for( int i = 1 ; i<=n ; i++ )17 {18 cnt += log10(i*1.0);19 }20 cout << (int)(cnt+1) << endl;21 }22 }23 return 0;24 }
today:
花开不同赏
花落不同悲
欲问相思处
花开花落时
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。