C语言实现两个大数相乘问题

Standard

同学找我帮忙,简单的写一个能实现的程序,未经优化。

【要求】本问题中,要求输入两个相对较大的正整数,能够通过程序计算出其结果。

【提示】两个相对较大的数肯定是不能够用LONG INT类型存储的,因为LONG型数据的数据范围也并不是很大,于是就需要采用其他的存储结构。这里推荐用数组存储一个大数,数组的初始空间可以定义到如200或300个单元,每个单元存储一位数据,形如下图:

2 5 5  9 6 2 0 7.。。。。

这样理论上,比如数组定义为200,就可以存储200个数字的整数,应该是满足足够大的条件了。而结果的存储也需要考虑空间的问题,所以需要一个更大的数组。

在解决了存储问题后,我们需要来实现乘法运送的过程,也就是说你必须要把这个数组中的每一位数字单独来进行乘法运算,比如我们可以用一个数字和另外一个数组中的每一位去相乘,从而得到乘法运算中一行的数字,再将每一行数字错位相加。这就是乘法运算的过程。

可以使用下面的C程序实现:
//以下是com_def.h文件

[code lang=”c”]
#ifndef __COM_DEF_H_
#define __COM_DEF_H_

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <conio.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

typedef int Boolean;
typedef int Status;

#endif
[/code]

//以下是mul.h文件

[code lang=”c”]
#ifndef __MUL_H_
#define __MUL_H_

#include "com_def.h"
#define N 200

extern void changes(); //将字符转移到数组
extern void mul(); //计算

#endif
[/code]

//以下是mul.c文件

[code lang=”c”]
#include "mul.h"

void changes(int *a ,char *s)
{
int i;
char ch;
int len = strlen (s);

//以下代码是对数组初始化
for (i = 0 ;i < N;i ++)
{
*(a + i) = 0;
}
for (i = 0 ;i < len;i ++)
{
ch = *(s + i);
*(a + len – 1 -i) = ch – ‘0’;
}

}

void mul(int *a ,int *b ,int *c) //结果存入C
{
int i,j;

//以下代码初始化c
for (i = 0 ;i < 2 * N;i ++)
{
*(c + i) = 0;
}

//二层循环逐位相乘
for (i = 0 ;i < N;i ++)
{
for (j = 0 ;j < N;j ++)
{
*(c + i + j) += *(a + i) * *(b + j); //对应位累加
}
}
for (i = 0 ;i < 2 * N;i ++) //移位
{
*(c + i +1) += *(c + i) / 10;
*(c + i) = *(c + i) % 10;
}
}
[/code]

//以下是main.c文件

[code lang=”c”]
#include "mul.h"

int main()
{
int a[N],b[N],c[2 * N];
char s1[N],s2[N];

int i,j = 2 * N – 1;

printf("输入第一个数:");
scanf("%s",s1);
printf("\n");
printf("输入第二个数");
scanf("%s",s2);
printf("\n");

changes(a,s1);
changes(b,s2);
mul(a,b,c);
while (c[j] == 0)
{
j –;
}

for (i = j;i >= 0;i –)
{
printf("%d",c[i]);
}
printf("\n");
return 0;

}
[/code]