big.cpp

实现大整数加减乘除

#include<iostream>
#include<conio.h>
#include<stdlib.h>
#define max 2002

using namespace std;

typedef struct
{
 short add[max+1];//最大运算位数
 int n;           //记录是几位数
}num;


//串的比较大小
short compare(num a,num b)
{
 short t=1;
    int i,j;
 for(i=0;a.add[i]==0;)i++;
 if(i)
 {
  for(j=i;j<=a.n;j++)a.add[j-i]=a.add[j];
  a.n=a.n-i;
 }
 for(i=0;b.add[i]==0;)i++;
 if(i)
 {
  for(j=i;j<=b.n;j++)b.add[j-i]=b.add[j];
  b.n=b.n-i;
 }
 if(a.n>b.n)t=1;
 else if(a.n<b.n)t=2;
 else
 {
  for(i=0;i<=a.n;i++)
  {
   if((a.add[i]-b.add[i])>0)
   {
    t=1;break;//第一个数大返回 1
   }
   else if((a.add[i]-b.add[i])<0)
   {
    t=2;break;//第二个数大返回 2
   }
  }
  if(i>a.n)t=0;       //两个数相等返回 0
 }
 return t;
}

//加法运算
num add(num addend1,num addend2)
{
 int carry=0;     //进位
 num result;      //运算结果
 int i,j,k,t;     //暂存器
 for(i=addend1.n,j=addend2.n,k=0;i>=0||j>=0;i--,j--,k++)
 {
  if(i>=0&&j>=0)
  {
   t=addend1.add[i]+addend2.add[j]+carry;
   result.add[k]=t%10;
   carry=(t-t%10)/10;
  }
  else if(i>=0)
  {
   t=addend1.add[i]+carry;
   result.add[k]=t%10;
   carry=(t-t%10)/10;
  }
  else
  {
   t=addend2.add[j]+carry;
   result.add[k]=t%10;
   carry=(t-t%10)/10;
  }
 }
 if(carry)
 {
  result.add[k]=carry;
  result.n=k;
 }
 else 
 {
  for(;0==result.add[k-1];)k--;
  if(k)result.n=k-1;
  else result.n=0;
 }
 return result;
}


//减法运算
num sub(num subtrahend1,num subtrahend2)
{
 int carry=1;    //进位，新发明的，减法用加法做
 num result;     //演算结果
 int i,j,k,t;    //暂存器
 result.add[0]=0;
 result.n=0;
    short comp=compare(subtrahend1,subtrahend2);
 if(1==comp)   //用comp记录是不是被减数大于减数，如果是就置为1，否则置为2
 {
  for(i=subtrahend1.n,j=subtrahend2.n,k=0;i>=0;i--,j--,k++)
  {
   if(j>=0)
   {
    t=subtrahend1.add[i]-subtrahend2.add[j]+carry+9;
       result.add[k]=t%10;
       carry=(t-t%10)/10;
   }
   else
   {
    t=subtrahend1.add[i]+carry+9;
    result.add[k]=t%10;
    carry=(t-t%10)/10;
   }
  }  
  for(;0==result.add[k-1];)k--;
  result.n=k-1;
 }
 else if(2==comp)
 {
  for(i=subtrahend1.n,j=subtrahend2.n,k=0;j>=0;i--,j--,k++)
  {
   if(i>=0)
   {
    t=subtrahend2.add[j]-subtrahend1.add[i]+carry+9;
       result.add[k]=t%10;
       carry=(t-t%10)/10;
   }
   else
   {
    t=subtrahend2.add[j]+carry+9;
    result.add[k]=t%10;
    carry=(t-t%10)/10;
   }
  }
  result.add[k]=0;
  for(;0==result.add[k-1];)k--;
  result.n=k;
 }
 else return result;
 return result;
}

//乘法运算
num mul(num mul1,num mul2)
{
 int carry;   //进位
 num registe1,registe2,registe3; //寄存器
 num result;  //结果
 result.add[0]=0;
 result.n=0;
 int i,j,k,t; //暂存器
 for(i=mul2.n;i>=0;i--)
 {
  carry=0;
  for(j=mul1.n,k=0;j>=0;j--,k++)
  {
   t=mul1.add[j]*mul2.add[i]+carry;
   registe1.add[k]=t%10;
   carry=(t-t%10)/10;
  }
  if(carry)
  {
   registe1.add[k]=carry;
   for(j=0;j<=k;j++)registe3.add[j]=registe1.add[k-j];
   for(;j<=k+mul2.n-i;j++)registe3.add[j]=0;
   registe3.n=k+mul2.n-i;
  }
  else
  {
   for(j=0;j<k;j++)registe3.add[j]=registe1.add[k-j-1];
   for(;j<k+mul2.n-i;j++)registe3.add[j]=0;
   registe3.n=k+mul2.n-i-1;
  }
  for(j=result.n;j>=0;j--) 
   registe2.add[j]=result.add[result.n-j];
  registe2.n=result.n;
  result=add(registe2,registe3);
 }
 return result;
}

//除法运算
num div(num division1,num division2,short remainder[])
{
 num result;
 remainder[0]=0;//没有余数置为0
 result.add[0]=0;
 result.n=0;
 num registe1,registe2,registe3;
 int i,j,k,t,n=-1;
 for(i=0;division1.add[i]==0;)i++;
 if(i)
 {
  for(j=i;j<=division1.n;j++)
   division1.add[j-i]=division1.add[j];
  division1.n=division1.n-i;
 }
 for(i=0;division2.add[i]==0;)i++;
 if(i)
 {
  for(j=i;j<=division2.n;j++)
   division2.add[j-i]=division2.add[j];
  division2.n=division2.n-i;
 }//把两个数的高位零去除
 for(i=0;i<=division2.n;i++)
 {
  if(division2.add[i])break;
 }
 if(i>division2.n)//除数为零返回错误值
 {
  result.add[0]=-1;
  return result;
 }
 for(i=0;i<=division1.n;i++)
 {
  if(division1.add[i])break;
 }
 if(i>division1.n)
  return result;//被除数为零返回0值
    short tt,comp;
 comp=compare(division1,division2);
 if(0==comp)
 {
  result.add[0]=1;
  return result;//除数等于被除数返回1值
 }
 else if(2==comp)
 {
  remainder[0]=division1.n+1;
        for(i=0;i<=division1.n;i++)
   remainder[i+1]=division1.add[i];
  return result;//除数大于被除数返回除数作为余数值
 }                 //remainder[0]记录余数是几位数
 else
 {
  for(i=division2.n;i<=division1.n;i++)
  {
   if(i==division2.n)
   {
       for(j=0;j<=i;j++)
     registe1.add[j]=division1.add[j];
    registe1.n=i;
   }
   else
   {
    registe1=registe2;
    registe1.n++;
    registe1.add[registe1.n]=division1.add[i];
   }//registe1做新的被除数，registe1[0]是高位
   comp=compare(registe1,division2);
   if(0==comp)
   {
    result.add[++n]=1;
    registe2.add[0]=0;
    registe2.n=0;
   }
   else if(1==comp)
   {
    for(j=1;j<=10;j++)
    {
     registe3.n=0;
     registe3.add[0]=j;
     registe3=mul(registe3,division2);
     for(k=0;k<=registe3.n/2;k++)
     {
      tt=registe3.add[k];
      registe3.add[k]=registe3.add[registe3.n-k];
      registe3.add[registe3.n-k]=tt;
     }
     comp=compare(registe3,registe1);
     if(0==comp)
     {
      result.add[++n]=j;
      registe2.add[0]=0;
      registe2.n=0;
      break;
     }
     else if(2==comp)continue;
     else
     {
      result.add[++n]=j-1;
      registe3.n=0;
      registe3.add[0]=j-1;
      registe3=mul(registe3,division2);
      for(t=0;t<=registe3.n/2;t++)
      {
       tt=registe3.add[t];
       registe3.add[t]=registe3.add[registe3.n-t];
       registe3.add[registe3.n-t]=tt;
      }
      registe3=sub(registe1,registe3);
      for(t=0;t<=registe3.n;t++)
       registe2.add[t]=registe3.add[registe3.n-t];
      registe2.n=registe3.n;
      break;
     }
    }
   }
   else
   {
    result.add[++n]=0;
    registe2=registe1;
   }
  }
  for(i=0;i<=n/2;i++)
  {
   tt=result.add[i];
   result.add[i]=result.add[n-i];
   result.add[n-i]=tt;
  }
  for(i=n;result.add[i]==0;i--)n--;
  if(n>=0)result.n=n;
  else result.n=0;
  for(i=0;i<=registe2.n;i++)if(registe2.add[i])break;
  if(i<=registe2.n)
  {
   for(j=i,k=1;j<=registe2.n;j++,k++)
    remainder[k]=registe2.add[j];
   remainder[0]=k-1;
  }
 } 
 return result;
}
void main()
{
 system("cls");
 cout<<"\t\t#============================================#"<<endl;
 cout<<"\t\t#              本软件使用说明                #"<<endl;
 cout<<"\t\t#============================================#"<<endl;
 cout<<"\t\t|     本软件实现两个巨大正整数的加减乘除四种 |"<<endl;
 cout<<"\t\t| 运算，如果输入错误，比如输入带小数点的实数 |"<<endl;
 cout<<"\t\t| 等，就会跳转到此页面要求用户自己先看清楚说 |"<<endl;
 cout<<"\t\t| 明，再继续操作。如果要求本软件做这三种运算 |"<<endl;
 cout<<"\t\t| 之外的操作，也会出现错误，并跳回此页面。   |"<<endl;
 cout<<"\t\t|     按任意键进入操作选择，比如你如果选择了 |"<<endl;
 cout<<"\t\t| 加法运算，进入界面后输入一个整数敲回车，再 |"<<endl;
 cout<<"\t\t| 输入另一个整数敲回车，此时运算结果就会出来 |"<<endl;
 cout<<"\t\t| 不遵守操作规则就会跳回此页面，另外注意不能 |"<<endl;
 cout<<"\t\t| 输入正负号，即没有负数输入。  请按任意键… |"<<endl;
 cout<<"\t\t|                                  2008年    |"<<endl;
 cout<<"\t\t#============================================#"<<endl;
 cout<<"\t\t#============================================#"<<endl;
 getch();system("cls");
 cout<<"\t\t#***********************#"<<endl;
 cout<<"\t\t|  请选择一种操作：     |"<<endl;
 cout<<"\t\t|   1、加法运算         |"<<endl;
 cout<<"\t\t|   2、减法运算         |"<<endl;
 cout<<"\t\t|   3、乘法运算         |"<<endl;
 cout<<"\t\t|   4、除法运算         |"<<endl;
 cout<<"\t\t#***********************#"<<endl;
 cout<<"\t\t#***********************#"<<endl;
 int choice;
 while(1)
 {
  choice=getch();
  if(choice>48&&choice<53)break;
  else cout<<endl<<"输入错误! 请重新输入："<<endl;
 }
 system("cls");
 if(49==choice)cout<<endl<<"\t\t欢迎进入加法运算\n"<<endl;
 else if(50==choice)cout<<endl<<"\t\t欢迎进入减法运算\n"<<endl;
 else if(51==choice)cout<<endl<<"\t\t欢迎进入乘法运算\n"<<endl;
 else if(52==choice)cout<<endl<<"\t\t欢迎进入除法运算\n"<<endl;
 num a,b,c;
 c.add[0]=0;
 int i,read=0;
 for(i=0;(a.add[i]=getch()-48)!=-35;i++)
 {
  cout<<a.add[i];
  if(a.add[i]<0||a.add[i]>9)
  {
   read=1;break;
  }
  if(1000==i)
  {
   i++;
   a.add[i]=-35;
   break;
  }
 }
 if(a.add[i]==-35)cout<<endl;
 if(read)main();
 else
 {
  a.n=i-1;
  for(i=0;(b.add[i]=getch()-48)!=-35;i++)
  {
   cout<<b.add[i];
   if(b.add[i]<0||b.add[i]>9)
   {
    read=1;break;
   }
   if(1000==i)
   {
    i++;
    b.add[i]=-35;
    break;
   }
  }
  if(b.add[i]==-35)cout<<endl;
  if(read)main();
  else
  {
   b.n=i-1;
   num result;
   if(49==choice)result=add(a,b);
   else if(50==choice)result=sub(a,b);
   else if(51==choice)result=mul(a,b);
   else if(52==choice)result=div(a,b,c.add);
   cout<<endl<<"计算结果为：";
   for(i=result.n;i>=0;i--)//打印结果
   {
    if((i==result.n)&&(i>0)&&(0==result.add[i]))
     cout<<"-";
    else if((result.n==0)&&(-1==result.add[i]))
     cout<<"错误警告：除数不能为零!";
    else
        cout<<result.add[i];
   }
   if(c.add[0])
   {
    cout<<"\t余数为：";
    for(i=1;i<=c.add[0];i++)
     cout<<c.add[i];
   }
   cout<<endl;
   getch();system("cls");
   cout<<"\n\n是否继续? (y/n)?"<<endl;
   while(1)   //继续操作询问
   {
    choice=getch();
    if(choice=='y'||choice=='Y'||choice=='n'||choice=='N')break;
    else cout<<endl<<"输入格式不对，请输入 y/n 。"<<endl;
   }
   if(choice=='y'||choice=='Y')main();
   else
   {
    system("cls");
    cout<<"\n\n\t\t\t谢谢使用!\n\n\n";
   }
  }
 }
}