2012图像所复试编程题一, 精确计算阶乘.

一个32 位整型变量无法精确表示大数的阶乘, 但一个整型数组却可表示.

算法思路: 当阶乘结果为不超过10的4次方的十进制正整数时, 可用一个整型数组( int nFactorial[4] )来依次存放阶乘的每一位数字. 比如, 5!=120可被记录为nFactorial[0]= 0, nFactorial[1] = 2, nFactorial[2] = 1, nFactorial[3] = 0.

当已计算出k的阶乘, 要计算(k+1)的阶乘时, 将记录k的阶乘的数组的每一位都与(k+1)相乘, 乘积依然存在数组的对应位上. 最后, 从最低位开始, 依次向高位循环处理每个位中大于9的数. 若数大于9，则需要进位. 将数的10的倍数进到高一位上，将数的小于10的余数存在原来的位中.一直到所有位中的数都小于10为止.

(1)(6分) 按此思路, 当已知阶乘结果为一个不超过10的1000次方的十进制整数时, 写出计算正整数阶乘的完整C/C++代码.

输入: 键盘输入一个正整数

输出: 显示输入正整数的阶乘

(2)(2分) 完善代码, 实现键盘输入是否满足要求的检查功能.

(3)(2分) 写出几种测试用例.

/***************************************************************************

       function:

              to calculate the factorial of a positive integer using array

       IPRAI, HUST, 2012, April, 9

       test example:

              5!=120, 0!=1!=1, 25!=15511210043330985984000000, 499!=...

              (a, =, *, ', 1.3, -0, >=450) are invalid input,

              -1,-2 for ending.

****************************************************************************/

#include <stdio.h>

#include <string.h> // only for memset()

#include <stdlib.h> // only for itoa(), atoi()

int main(void)

{

  int Data[1000];

  int digit; // number of the valid decimal bit of the factorial

  int i, j;

  int N;

  char cN[100], cNN[100];

  do

  {

       // input a positive integer

       printf("\nEnter a positive integer(less than 450) to calculate its factorial(negative integer for ending): ");

       scanf("%s", &cN);

  

       // check the validity of the input

       N = atoi(cN);

       itoa(N, cNN, 10);

       if(strcmp(cN, cNN))

       {

              printf("\nThis is not a valid number. Try again!\n");

              continue;

       }

       if(N >449)

      {

         printf("\nThis number is too big. Try a smaller one(less than 450).\n");

         continue;

       }

 

       // check the stop condition

       if(N < 0)

       {

              printf("\nCaculating ends.\n");

              break;

       }

 

       // initialize Data = 0

       memset(Data, 0, sizeof(Data));

 

       // 0!=1!=1

       Data[0] = 1;

       digit = 1;  

 

       for( i=1; i<=N; i++ )

       {

              for(j=0; j<digit; j++)

              {

                     Data[j] *= i;

              }

 

              for(j=0; j<digit; j++)

              {           

                     if(Data[j] > 9)

                     {

                            if(Data[digit-1] > 9)

                            {

                                   digit++;

                            }

                           

                            Data[j+1] += (Data[j]/10);

                            Data[j] = Data[j]%10;

                     }// end of if(Data[j])

 

              }// end of for(j)

 

       }// end of for(i)

 

       // output the result

       printf("%d! = ",N);

       for(j=digit-1; j>=0; j--)

              printf("%d", Data[j]);

       printf("\n");

 

  }while(1);

 

  return 0;

}