新浪博客 发表时间 -- 2009-07-26 21:45:21
N!求解位数
下面介绍两种方法直接求阶乘结果的位数:
方法一
<wbr><wbr><wbr> 可以将n!表示成10的次幂,即n!=10^M(10的M次方)则不小于M的最小整数就是 n!的位数,对该式两边取对数,有 <wbr><wbr><wbr> M =log10^n!<br>
即:<br><wbr><wbr><wbr> M = log10^1+log10^2+log10^3...+log10^n<br><wbr><wbr><wbr> 循环求和,就能算得M值,该M是n!的精确位数</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
代码:
#include "iostream"
#include "math.h"
using namespace std;
int main()
{
<wbr>int n;<br><wbr>register<wbr> int i;<br><wbr>long double d;<br><wbr>while (scanf("%d",&n)!=EOF)<br><wbr>{<br><wbr><wbr>d=0;<br><wbr><wbr>for (i=1;i<=n;i++)<br><wbr><wbr>{<br><wbr><wbr><wbr>d+=(double)log10(i);<br><wbr><wbr>}<br><wbr><wbr>printf("%d\n",(int)d+1);<br><wbr>}<br><wbr>return 0;<br>
}</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
方法二
<wbr><wbr><wbr> 利用斯特林(Stirling)公式的进行求解。下面是推导得到的公式:<br><wbr><wbr><wbr> res=(long)( (log10(sqrt(4.0*acos(0.0)*n)) + n*(log10(n)-log10(exp(1.0)))) + 1 );<br><wbr><wbr><wbr> 当n=1的时候,上面的公式不适用,所以要单独处理n=1的情况!<br><wbr><wbr><wbr> 有关斯特林(Stirling)公式及其相关推导,这里就不进行详细描述,</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
<wbr><wbr><wbr> 这种方法速度很快就可以得到结果。<br></wbr></wbr></wbr>
分享到:
相关推荐
ACM-ICPC 历年竞赛 真题,各大赛区真题详解,内含几大赛区各年度的真题
这是我的竞赛培训资料,介绍了大数算法与组合数学算法的相关学习内容,欢迎大家来下载
Algorithm-203-ACM-Problems-Code.zip,203个ACM问题的C 源代码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
我09年参加现场赛前准备的,这些公式有的是在POJ等OJ上做题时遇到的,还有些可能会出现的数学公式,本人非数学出身,准备的内容尚浅,就是多和乱(不敢说丰富)
背包问题!不用说一定不会让你失望!非常经典!非常详细!
很有用的关于ACM程序设计大赛中的大数问题的全解析。。。
个人ACM-ICPC模板acm-icpc-master.zip
杭电ACM -ppt 杭电ACM -ppt 杭电ACM -ppt 杭电ACM -ppt 杭电ACM -ppt 杭电ACM -ppt
2015北大ACM-ICPC暑期课 pdf
2010年第34届ACM-icpc程序设计大赛全球总决赛试题
ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版
ACM-ICPC 历年竞赛 真题,各大赛区真题详解,内含几大赛区各年度的真题
ACM-ICPC培训资料汇编
Stanford-acm-ppt very good !
Algorithm-ACM-ICPC.zip,感觉自己做假题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
ACM_ACM-ICPC算法示例之Greedy_题解
ACM_ACM-ICPC算法示例之Hashing_题解
ACM----博弈论
ACM-ICPC要求的知识点 ACM/ICPC要求的知识点 排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排序,外部排序) 数论(整除,集合论,关系,素数,进位制,辗转相除,...
ACM---算法数论