Question

用c语言编写大整数的四则运算，求大神

大整数指超过十位的十进制整数，这里为简便，假定不超过五十位。这类大整数在C语言系统中因超界溢出，是不能直接表达和计算的。可以用数组来表示大整数，在此基础上编写出实现大整数加、减、乘、除的程序，并努力加以优化。（不要C++的）

Answer 1

你可以找一下加密库的源文件来研究下，里面就有大数四则运算，曾经试着写2048位的大数四则运算，结果就写了加法，减法，和简单的没有优化的乘法就没信心写了。。。大数是用数组表示的，没有用结构体，复制来的，不知能不能运行。。

#define MAX 400
void my_read(int *a)
{
int len,i,flag=0;
char s[MAX];
aa:
while(1)
{
  scanf("%s",&s);
  len=strlen(s);
  if (s[0]=='-') flag=1;
  for(i=len-flag;i>=1;i--)
  {
   if ((s[len-i]-'0')<0||(s[len-i]-'0')>9)
    {
      printf("\t\t\t你输入的第%d位不合法，按任意键重新输!!",len-i+1);
      getch();
      goto aa;
    }
    else
     a[i]=s[len-i]-'0';
   }
   if (flag)
       a[0]=-(len-1);
    else
       a[0]=len;
   break;
  }
return;
}

void my_print(int *a)
{
int i;
if (a[0]<0) printf("-");
if (a[0]==0)
   {
    printf("0");
    return;
    }
for(i=abs(a[0]);i>=1;i--)
  printf("%d",a[i]);
printf("\n");
}

void format(int *a)
{
int p;
for(p=1;p<a[0]||a[p]>=10;p++)
{
  if (p>=a[0]) a[p+1]=0;
     a[p+1]+=a[p]/10;
  a[p]=a[p]%10;
  }
if (p>=a[0]) a[0]=p;
return;
}
void add(int *a,int *b,int *c)
{
int len,i;
if (a[0]<b[0]) len=a[0];
   else len=b[0];
for(i=1;i<=len;i++)
   c[i]=a[i]+b[i];
if (len<a[0])
{
  for (;i<=a[0];i++)
    c[i]=a[i];
  c[0]=a[0];
  }
  else
  {
  for(;i<=b[0];i++)
  {
   c[i]=b[i];
   }
  c[0]=b[0];
  }
  format (c);
}

void commaltiply (int *a,int x,int *b)
{
int i;
for(i=1;i<=a[0];i++)
   b[i]=a[i]*x;
b[0]=a[0];
format(b);
return;
}
void matiply(int *a,int *b,int *c)
{
int i,temp[MAX],j;
commaltiply(a,b[1],c);
for(i=2;i<=b[0];i++)
{
  if (b[i]==0)
   {
    c[0]++;
    for (j=c[0];j>1;j--)
     c[1]=0;
    }
    else
    {
    commaltiply(a,b[i],temp);
    for(j=1;j<i;j++)
     commaltiply(temp,10,temp);
    add(c,temp,c);
  }
}
}
void dectobin(int *a,int *b)
{
int p;
b[0]=0;
while(a[0]>0)
{
  b[0]++;
  b[b[0]]=a[1]%2;
  p=a[0];
  while(p>0)
  {
   if (a[p]%2 && p>1) a[p-1]+=10;
    a[p]/=2;
   if (a[a[0]]==0) a[0]--;
     p--;
   }
}
}

format1(int *a)
{
int i;
for (i=1;i<=a[0];i++)
   if (a[i]<0)
   { a[i]+=10;
     a[i+1]-=1;
   }
}

void sub_1(int *a,int *b,int *c)
{
  int i;
  for (i=1;i<=b[0];i++)
    c[i]=a[i]-b[i];
  if (a[0]==b[0]) goto loop;
  for (;i<=a[0];i++)
    c[i]=a[i];
  loop:
  c[0]=a[0];
  format1(c);
  i=c[0];
  while(1)
   if (c[i]==0) i--;
     else break;
  c[0]=i;
  return;
}


void sub(int *a,int *b,int *c)
{
int i,flag=0;
for (i=1;i<=a[0];i++)
     if (a[i]!=b[i]) {flag=1;break;}
if (flag==0)
  {
   c[0]=0;
   return;
   }
flag=0;
if (a[0]==b[0])
   {
    i=a[0];
    while(i>0)
    {
     if (a[i]>b[i])
{
 sub_1(a,b,c);
 break;
 }
     if (a[i]<b[i])
{
 flag=1;
 sub_1(b,a,c);
 break;
}
     i--;
    }
  }
if (a[0]>b[0])
    sub_1(a,b,c);
  else
   if (a[0]<b[0])
     {
      flag=1;
      sub_1(b,a,c);
     }
if (flag)
   c[0]=-c[0];
  else
   c[0]=c[0];
}
void main()
{
int i,a[MAX],b[MAX],c[MAX];
char yn;
strat:
while(1)
{
  clrscr();
  printf("\n\n\n");
  printf("\t\t\t**************************************\n");
  printf("\t\t\t*        *\n");
  printf("\t\t\t*           1.大整数的加法          *\n");
  printf("\t\t\t*           2.大整数的减法          *\n");
  printf("\t\t\t*           3.大整数的乘法          *\n");
  printf("\t\t\t*           4.大整数进制转换　　 　 *\n");
  printf("\t\t\t*           5.帮助　　　　　　　　?*\n");
  printf("\t\t\t*           6.退出                  *\n");
  printf("\t\t\t*                                   *\n");
  printf("\t\t\t**************************************\n");
  printf("\n\n\t\t\t      请选择（1－6）：");
  yn=getch();
  if (yn=='1'||yn=='2'||yn=='3'||yn=='4'||yn=='5'||yn=='6') break;
    else
    {
     printf("\n\t\t\t　　输入不合法！按任意键重新输入！！！！");     getch();
    }
  }
  clrscr();
  if (yn=='6') return;
  if (yn=='4')
   {
    printf("请输入待转换的大整数:");
    printf("\n");
    my_read(a);
    for (i=1;i<=abs(a[0]);i++)
      b[i]=a[i];
    b[0]=a[0];
    if (a[0]<0) {a[0]=-a[0];dectobin(a,c);a[0]=-a[0];c[0]=-c[0];goto e;}
    dectobin(a,c);
    e:
    printf("十进制:");
    my_print(b);
    printf("二进制:");
    my_print(c);
    goto loop;
   }
  printf("请输入大整数A:");
  my_read(a);
  printf("请输入大整数B:");
  my_read(b);
  if (yn=='1')
   {
    if (a[0]<0 && b[0]<0) {a[0]=-a[0];b[0]=-b[0];add(a,b,c);c[0]=-c[0];a[0]=-a[0];b[0]=-b[0];goto c;}
    if (a[0]>0 && b[0]<0) {b[0]=-b[0];sub(a,b,c);b[0]=-b[0];goto c;}
    if (a[0]>0 && b[0]>0) {add(a,b,c);goto c;}
    if (a[0]<0 && b[0]>0) {a[0]=-a[0];sub(b,a,c);a[0]=-a[0];goto c;}
    c:
    printf("\n\t\t\t");
    printf("A=");
    my_print(a);
    printf("\n\t\t\t");
    printf("B=");
    my_print(b);
    printf("\n\t\t\t");
    printf("C=A+B=");
    my_print(c);
    goto loop;
   }
  if (yn=='2')
   {
    if (a[0]<0 && b[0]<0) {a[0]=-a[0];b[0]=-b[0];sub(b,a,c);a[0]=-a[0];b[0]=-b[0];}
    if (a[0]<0 && b[0]>0) {a[0]=-a[0];add(a,b,c);a[0]=-a[0];c[0]=-c[0];}
    if (a[0]>0 && b[0]<0) {b[0]=-b[0];add(a,b,c);b[0]=-b[0];}
    if (a[0]>0 && b[0]>0) sub(a,b,c);
    printf("A=");
    my_print(a);
    printf("\nB=");
    my_print(b);
    printf("\nC=A-B=");
    my_print(c);
    goto loop;
   }
  if (yn=='3')
   {
    if (a[0]<0 && b[0]>0) {a[0]=-a[0];matiply(a,b,c);a[0]=-a[0];c[0]=-c[0];goto d;}
    if (a[0]>0 && b[0]<0) {b[0]=-b[0];matiply(a,b,c);b[0]=-b[0];c[0]=-c[0];goto d;}
    if (a[0]<0 && b[0]<0) {a[0]=-a[0];b[0]=-b[0];matiply(a,b,c);a[0]=-a[0];b[0]=-b[0];goto d;}
    matiply(a,b,c);
    d:
    printf("\n\t\t\tA=");
    my_print(a);
    printf("\n\t\t\tB=");
    my_print(b);
    printf("\n\t\t\tC=A*B=");
    my_print(c);
    goto loop;
   }
  loop:
  while(1)
  {
   printf("\n\t\t\t继续计算吗？(y/n)");
   yn=getch();
   if (yn=='y') goto strat;
   if (yn=='n') return;
  }
}

Answer 2

思路：

1. 实现大数的比较

2. 实现大数的加1操作

3. 实现大数的减1操作

4. 加法：A+B=(A+1) + (B-1)，按照此原则递归直到B-1为0

5. 减法：A-B=(A-1) - (B-1)，按照此原则递归直到B-1为0

6. 乘法：A*B=A+A*(B-1)，按照此原则递归直到B-1为0

7. 除法：A/B=1 + (A-B)/B，按照此原则递归直到 (A-B) < B

Answer 3

用结构体来表示大数，理论上是不限制的。
吧相应的进位做好就ok