求阶乘优化算法 鄙人想不到·····

苍祭

阶乘的递归算法慢了，求个优化的算法···我试了几种方法（不能称之为算法）都不能满足要求；
各位大侠顺便说说阶乘优化算法的原理哦·······

wAterLoo

估计楼主应该是在算一个大数，如果楼主了解汇编就，会发现，经过多次乘法运算后，由于数据的长度越来越大，数据的存取会越来越慢，一开始我也没有思考楼主所谓的递归优化，但是看了前面几位的回复，楼主居然还对时间有限制，我就想到应该是在算一个大数
定义一个整型的数组，每一位不是存放一位而是存放五位，这样相加，相乘的次数就是原来的

1. #include<stdio.h>
   
2. 
   
3. 
   
4. 
   
5. int main()  
   
6. 
   
7. {   
   
8. 
   
9.      int n;
   
10. 
    
11.      printf("请输入一个整数N(0~20000)：\n");   
    
12. 
    
13.      while(scanf("%d", &n) != EOF){      
    
14. 
    
15.          int s[16000] = {0}, j, i, k = 0, t = 0, p = 0;
    
16.          long sum = 0;        
    
17. 
    
18.          s[0] = 1;  
    
19. 
    
20.          for(j = 1;j <= n;j++){  
    
21.               for(i = 0;i <= t;i++){  
    
22.                    sum = s[i] * j + p;  
    
23.                    p = 0;  
    
24.                    if(sum > 99999){  
    
25.                        s[i] = sum % 100000;   //每一位存放位         
    
26.                        p = sum / 100000;         
    
27.                        if(t == i){
    
28.                             t++;
    
29.                             s[t] = 0;
    
30.                        }  
    
31.                    }  
    
32.                    else s[i]=sum;  
    
33.               }  
    
34.          }  
    
35. 
    
36.          printf("%d!=", n);
    
37.          printf("%d", s[t]);  
    
38.          for(i = t - 1;i >= 0;i--){   
    
39.               printf("%05d",s[i]);  
    
40.          }  
    
41. 
    
42.          printf("\n\n");
    
43. 
    
44.          printf("请再输入一个整数N(0~20000)：\n");
    
45. 
    
46.      }  
    
47. 
    
48.      return 0;  
    
49. 
    
50. }
    

复制代码

小马过河

多优化算优化

1. #include<stdio.h>
   
2. void main()
   
3. {
   
4. int qjc(int x);
   
5. int a,b;
   
6. printf("请输入欲求阶乘的数字!\n");
   
7. scanf("%d",&a);
   
8. b=qjc(a);
   
9. printf("阶乘的数字=%d\n",b);
   
10. }
    
11. int qjc(int x)
    
12. {
    
13. int a,q=1;
    
14. for(a=1;a<=x;a++)
    
15. {
    
16. q*=a;
    
17. }
    
18. return  (q);
    
19. }

复制代码

funoranges

迭代啊。

int a = 1, n;
cin >> n;
for ( ; n > 0 ; n-- )
{
     a = n * a;
}

苍祭

小马过河 发表于 2012-3-22 17:15

                               
登录/注册后可看大图

多优化算优化

呃···不好意思的说··这样不行·····会超时的···我试过了··我第一个就是这样的····

苍祭

wAterLoo 发表于 2012-3-22 16:47

                               
登录/注册后可看大图

估计楼主应该是在算一个大数，如果楼主了解汇编就，会发现，经过多次乘法运算后，由于数据的长度越来越大， ...

谢谢了，没有想到这个方面的事情，受教了·····

ccqiji

给你个程序自己看下吧
这个应该速度还行的

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <math.h>
   
4. #include <time.h>
   
5. 
   
6. #define MAX 100000
   
7. 
   
8. int aryResult[MAX * 4];
   
9. 
   
10. int main(void)
    
11. {
    
12.     /*nMulTemp(乘积临时变量), nCarry(保存进位信息)*/
    
13.     int nNum, nMulTemp, nCarry, nIndex;
    
14.     int i,j;
    
15.     clock_t begin, end; /*计时*/
    
16.     double  cost;
    
17.     FILE *fp;
    
18.    
    
19.     printf("Input N Please!:");
    
20.     scanf("%d", &nNum);
    
21.    
    
22.     aryResult[0] = 1; /*初始化结果数组*/
    
23.     nIndex = 1;
    
24.    
    
25.     begin = clock(); /*计时开始*/
    
26.    
    
27.     for(i = 2; i <= nNum; i++)
    
28.     {
    
29.         nCarry = 0; /*进位信息清零*/
    
30.         for(j = 0; j < nIndex; j++)
    
31.         {
    
32.             nMulTemp = aryResult[j] * i + nCarry; /*乘积 + 进位*/
    
33.             aryResult[j] = nMulTemp % 100000;
    
34.             nCarry = nMulTemp / 100000; /*计算进位*/
    
35.         }
    
36.         while(nCarry != 0) /*循环处理进位*/
    
37.         {
    
38.             aryResult[nIndex] = nCarry % 100000;
    
39.             nCarry = nCarry / 100000;
    
40.             nIndex++;
    
41.         }
    
42.     }
    
43.     /*计算耗时*/
    
44.     end = clock();
    
45.     cost = (double)(end - begin) / CLOCKS_PER_SEC;
    
46.     printf("%lf seconds\n", cost);
    
47.    
    
48.     system("pause");
    
49.     /*输出计算结果到"output.txt*/
    
50.     fp = fopen("output.txt", "w");
    
51.     for(i = (nIndex - 1); i >= 0; i--)
    
52.     {
    
53.         fprintf(fp, "%05d", aryResult[i]);
    
54.     }
    
55.     fclose(fp);   
    
56.     printf("Result Output To "output.txt"\r\n");
    
57.     return 0;
    
58. }

复制代码

追忆_、流年

好样的 加油

sc3297

大数迷茫啊~~~~~~

苍祭

追忆_、流年 发表于 2012-3-24 18:37

                               
登录/注册后可看大图

好样的 加油

其实 路还很长的哦····

苍祭

sc3297 发表于 2012-3-26 02:37

                               
登录/注册后可看大图

大数迷茫啊~~~~~~

对啊···对于数组的处理还真要多学了····

苍祭

ccqiji 发表于 2012-3-23 20:34

                               
登录/注册后可看大图

给你个程序自己看下吧
这个应该速度还行的

学友高见！那个  我能不能请教一下 就是错过用数组储存了一个很大的数（比如位数有1000位）然后我要用这个数对某个数（比如说13）求余，该怎么控制进位啊，我想不到······