注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

众里寻他千百度,名师成就满分路

AP 微积分 AP 计算机 腾飞的博客

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

网易考拉推荐

阶乘 大整数的阶乘 转载  

2015-10-29 14:54:41|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1、先说小点的数的阶乘计算:

Cpp代码  收藏代码
  1. // n!     
  2. unsigned long fac(int n)  
  3. {  
  4.     if(n == 0)  
  5.         return 1;  
  6.     else  
  7.         return n * fac(n - 1);  
  8. }  


2、如果需要稍微提高效率,还可以:

Cpp代码  收藏代码
  1. unsigned long fac_ex(int n)  
  2. {  
  3.     if(n == 0 || n == 1)  
  4.         return 1;  
  5.     else  
  6.         return n * (n - 1) * fac(n - 2);  
  7. }  

3、依此类推,继续想提高一点效率: 

Cpp代码  收藏代码
  1. unsigned long fac_ex1(int n)  
  2. {  
  3.     if(n == 0 || n == 1)  
  4.         return 1;  
  5.     else if(n == 2)  
  6.         return 2;  
  7.     else  
  8.         return n * (n - 1) * (n - 2) * fac(n - 3);  
  9. }  
  10.   
  11. unsigned long fac_ex3(int n)  
  12. {  
  13.     if(n == 0 || n == 1)  
  14.         return 1;  
  15.     else if(n == 2)  
  16.         return 2;  
  17.     else if(n == 3)  
  18.         return 6;  
  19.     else  
  20.         return n * (n - 1) * (n - 2) * (n - 3) * fac(n - 4);  
  21. }  

4、如果不像用递归,那就用下面的,效率比递归的要好:


Cpp代码  收藏代码
  1. unsigned long fac_ex2(int n)  
  2. {  
  3.     unsigned long ret = 1;  
  4.     for(int i = 2; i <= n; ++i)  
  5.     {  
  6.         ret *= i;  
  7.     }  
  8.     return ret;  
  9. }  

5、如果对空间要求不高,可以把一些数据计算出来,放在静态区:


Cpp代码  收藏代码
  1. unsigned long fac_ex10(int n)  
  2. {  
  3.     static int facArr[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,  
  4.     fac_ex2(11)};       // fac_ex2(11) will be calculated only once  
  5.     if(n >= 0 && n < sizeof(facArr) / sizeof(facArr[0]))  
  6.         return facArr[n];  
  7.     else  
  8.         return n * (n - 1) * (n - 2) * (n - 3) * (n - 3) * (n - 3)  
  9.          * (n - 4) * (n - 5) * (n - 6) * (n - 7) * (n - 8) * (n - 9)  
  10.          * (n - 10) * fac(n - 11);  
  11. }  

6、上面的是放在函数里面,也可以放在文件作用域里或全局作用域:

Cpp代码  收藏代码
  1. static int facArr[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,  
  2.     fac_ex2(11)};   // fac_ex2(11) will be calculated only once, at the initialization of the app  

7、上面的不讨论了,现在讨论大整数阶乘:

Cpp代码  收藏代码
  1. // 大整数阶乘          
  2. void    fac_bigInteger(int n, int result[], int maxSize, int *resultLen)  
  3. {  
  4.     if(maxSize < 1)  
  5.         return;  
  6.     memset(result, 0, maxSize * sizeof(int));  
  7.     result[0] = 1;  
  8.     int currLen = 1;  
  9.       
  10.     for(int j = 2; j <= n; ++j)  
  11.     {  
  12.         int carry = 0;  
  13.         for(int k = 0; k < maxSize && k < currLen; ++k)  
  14.         {  
  15.             int temp = result[k] * j + carry;  
  16.             if(temp < 10)  
  17.             {  
  18.                 result[k] = temp;  
  19.                 carry = 0;  
  20.             }  
  21.             else  
  22.             {  
  23.                 carry = temp / 10;  
  24.                 result[k] = temp - carry * 10;  
  25.             }  
  26.         }  
  27.         if(carry > 0)  
  28.         {  
  29.             char buf[512];  
  30.             sprintf(buf, "%d", carry);  
  31.             int currLenTemp = currLen;  
  32.             for(int i = strlen(buf) - 1; i >= 0; --i)  
  33.             {  
  34.                 result[currLenTemp++] = buf[i] - '0';  
  35.             }  
  36.             currLen = currLenTemp;  
  37.         }  
  38.     }  
  39.     *resultLen = currLen;  
  40. }  

测试代码:

Cpp代码  收藏代码
  1. void ccTestFac()  
  2. {  
  3. #if 1     
  4.     int arr[1024];  
  5.     int len;  
  6.     fac_bigInteger(50, arr, 1024, &len);  
  7.     for(int i = len - 1; i >= 0; --i)  
  8.     {  
  9.         std::cout << arr[i];  
  10.     }  
  11.     std::cout << endl;  
  12.     std::cout << len << std::endl;  
  13.       
  14. #endif  
  15. }  
  评论这张
 
阅读(192)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017