C程序训练：大数相乘与阶乘的计算

两个大数相乘，我们可以利用小学生列竖式做乘法的方法编写程序即可。例如，计算123*23，可以按以下步骤做：

1. answer = 0；

2. temp=123*3 =369

3. answer = answer + temp

4. temp = 123 * 20 = 2460

5. answer = answer + temp

按该方法编写程序，需要设计：

1. 计算两个数的加，完成上面的3和4步。

2. 完成被乘数与一位数的乘法，完成上面的第2步和第4步。注意低位的0，比如第4步，123和乘数的十位2相乘，结果还需乘10。如果有百位，计算结果需要乘以100。在实现时，可以预先留出0的位数，计算的结果放在前面。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define DIGIT 500
void reserved(char * str, int len) // 逆置
{
  for (int m = 0, n = len - 1; m < n; m++, n--) {
    char temp = str[m];
    str[m] = str[n];
    str[n] = temp;
  }  
} 
// 加法  a=a+b, 返回a的长度。
int add(char *a, char *b, int len_a, int len_b) {
  int len, i;
  len = (len_a>=len_b)?len_a:len_b;
  for(i=0; i<len; i++){
    a[i] = a[i] + b[i];  
    a[i+1] += a[i] / 10;
    a[i] %= 10;        
  }
  if(a[i]) i++;
  return i;
}

int multiply(char *a, char *b, char *answer, int len1, int len2) 
{
  char temp[DIGIT]={0};//每一轮乘法的值
  int anslen = 0;  
  int k;
  for (int i = 0; i <len2; i++) {    
    memset(temp,0,DIGIT);
    k = i;  
    for(int j=0; j<len1; j++,k++) {
      temp[k] += a[j] * b[i];
      temp[k+1] = temp[k] / 10;
      temp[k] %= 10;
    }
    if(temp[k]) k++;   
    anslen = add(answer, temp, anslen, k);//加法运算    
  }
  reserved(answer, anslen);
  return anslen;
}

int main() 
{
  char num1[DIGIT]={0}, num2[DIGIT]={0}, answer[DIGIT]={0};
  int i,len1,len2,len;
  scanf("%s", num1);
  scanf("%s", num2);
  len1 = strlen(num1);
  i=len1;
  while(i) {
    num1[--i] -= '0';    
    if(num1[i]<0 || num1[i]>9) {
      printf("输入错。\n");
      exit(1);
    } 
  }
  len2 = strlen(num2);
  i=len2;
  while(i) {
    num2[--i] -= '0';    
    if(num2[i]<0 || num2[i]>9) {
      printf("输入错。\n");
      exit(2);
    } 
  }  
  reserved(num1, len1);
  reserved(num2, len2);
  len = multiply(num1, num2, answer, len1, len2);
  for(i=0; i<len; i++) 
    printf("%d", answer[i]);
  printf("\n");  
  return 0;
}

对上面的算法进行优化，将add和multiply两个函数合并在一起，代码更紧凑。

优化后的multiply代码如下。

int multiply(char *a, char *b, char *answer, int len1, int len2) {
  int anslen = 0;  
  for (int i = 0; i <len2; i++) {
    for (int j = 0; j <len1; j++) {
      answer[i+j] += a[j] * b[i];
      answer[i+j+1] += answer[i+j]/10;
      answer[i+j] %= 10;
    }    
  }
  for(anslen=len2+len1;!answer[anslen]; anslen--);
  reserved(answer, ++anslen);
  return anslen;
}

同样，按此思路，我们可以计算出任何数的阶乘。

程序代码如下：

#include <stdio.h>
#define DIGIT 5000

int multiply(int *answer,int n) 
{
  int length = 1;
  int k,i,j,c=0;  
  for (i = 2; i <= n; i++) {
    for(k=0; k<length; k++) {
       answer[k] = answer[k] * i + c;
       c = answer[k] / 10;    
       answer[k] %= 10;        
    }
    while(c) {
       answer[length++]=c % 10;        
       c /= 10;
    }        
  }
  return length;
}

int main() {
  int answer[DIGIT]={1};
  int n,len;
  scanf("%d",&n);
  len = multiply(answer,n);
  for(int i=len-1; i>=0; i--) 
    printf("%d", answer[i]);
  printf("\n");
  return 0;
}

为了让程序看起来更加容易，对程序进行改进、优化，代码如下。

#include <stdio.h>
#define DIGIT 5000
int multiply(int answer[],int len, int n) 
{  
  int i,c=0;  
  for (i = 0; i < len; i++) {
       answer[i] = answer[i] * n + c;
     c = answer[i] / 10;    
     answer[i] %= 10;        
    }
    while(c){
     answer[i++] = c%10;  
     c = c / 10;         
  }
  return i;
}

int main() {
  int answer[DIGIT]={1};
  int n,len=1;
  scanf("%d",&n);
  for(int i=2; i<=n; i++) {
    len = multiply(answer,len,i);
  }
  for(int i=len-1; i>=0; i--) 
    printf("%d", answer[i]);
  printf("\n");
  return 0;
}

参考文献：

[1]李红卫，李秉璋. C程序设计与训练（第四版）[M]，大连，大连理工大学出版社，2003.

[2]https://pan.baidu.com/s/17ZXphwqySNIsIgcGtYMjvg?pwd=lhwc