Chinaunix首页 | 论坛 | 博客
  • 博客访问: 186179
  • 博文数量: 89
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 828
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-08 10:44
文章分类
文章存档

2014年(9)

2013年(80)

我的朋友

分类: Java

2013-11-05 17:05:28

   问题描述:编写程序,对给定的n(n <= 100),计算并输出k的阶乘k!的全部有效数字。


    注意:如果要求一个5的阶乘,用整型可以存储,求10的阶乘可以用长整型表示,但若要求100的阶乘,就无法用长整型表示,此时就必须考虑别的方法。


    要求的k!的值,必定已求得(k-1)!的值,依次地推,当 k = 2时,要求的1! = 1为已知。求得(k-1)!的值后,对(k-1)!连续累加k-1此后即可求得K!值。


    例如:5!= 120,计算6!,可对原来的120累加5次120后得到720.


   由于k!可能大大超出一般整数的位数,因此程序用一个一维数组存储长整型,存储长整数数组的每个元素只存储长整数的一位数字。如有m位长整数N用数组a[]存储,并用a[0]存储长整数N的位数m,即a[0] = m。按上述约定,数组的每个元素存储k的阶乘k!的一位数字,并从低位到高位依次存于数组的第二个元素、第三个元素....


  例如:6! = 720,在数组中的存储形式为:


 a[0]       a[1]        a[2]     a[3]


  3         0           2        7


 a[0] = 3表示长整数是一个3位数,接着从低位到高位依次是0、2、7,表示成整数720.


程序实现:


[cpp] view plaincopy
/* 
 *程序功能:计算任意位数的阶乘 
 *作者
 */  
#include  
#include  
#define MAXN 1000  
  
//已知a中的(k-1)!,求k!  
void PreNext(int a[],int k)   
{  
    int *b,m = a[0],i,j,r,carry;  
    b = (int*)malloc(sizeof(int)*(m+1));  
    for(i = 1; i <= m; i++)    
        b[i] = a[i];  
    for(j = 1; j < k; j++)   //控制累加k-1次  
    {  
        for(carry=0,i = 1;i <= m;i++)  
        {  
            r = (i <= a[0]?a[i]+b[i]:a[i])+carry; //计算加的结果  
            a[i] = r % 10; //计算本位结果  
            carry = r / 10; //计算进位数字  
        }  
        if(carry)  //向最高为进位  
            a[++m] = carry;  
    }  
    free(b);  
    a[0] = m;  
}  
void Print(int *a,int k)  
{  
    int i;  
    int m = 0;  
    for(i = a[0]; i >0; i--){  
        printf("%d",a[i]);  
        m++;  
        if(m % 5 == 0)             //每5个数字空一格     
            printf(" ");    
        if(40 == m)                //每行输出40个数字     
        {    
            printf("\n");    
            m = 0;            
        }  
    }  
    printf("\n");  
}  
void main()  
{  
    int a[MAXN],n,k;  
    n = 1;  
    printf("本程序计算任意位数的阶乘!\n");  
      
    while(n){  
        printf("请输入一个数:");  
        scanf("%d",&n);  
        a[0] = a[1] = 1;  
        for(k = 2; k <= n; k++)  
        {  
            PreNext(a,k);         
            if(k == n)  
                Print(a,k);  
        }  
    }  
}  
阅读(536) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~