算法-大数的四则运算

待我称王封你为后i 2022-08-04 11:58 161阅读 0赞

题目描述以加法为例  
给出两个正整数A和B，计算A+B的值。保证A和B的位数不超过500位。  
  
输入描述 Input Description  
读入两个用空格隔开的正整数  
  
输出描述 Output Description  
输出A+B的值  
  
样例输入 Sample Input  
3 12  
  
样例输出 Sample Output  
15

**大数加法**

#include"stdio.h"
    #include"string.h"
    #include"stdlib.h"
    int main()
    {
    	char s1[500],s2[500];
    	int i,j,k=0,*a,n;
    	scanf("%s%s",s1,s2);
    	i=strlen(s1)-1;
    	j=strlen(s2)-1;
    	n=i>j? i:j;
    	a=(int*)malloc((n+2)*sizeof(int));
    	while(k<=n+1)
    	     a[k++]=0;
    	k=0;
    	while(i>=0||j>=0)
    	{
    	     if(i>=0&&j>=0)
    		  a[k]+=(s1[i]-'0')+(s2[j]-'0');
    	     else if(j<0)
    		  a[k]+=s1[i]-'0';
    	     else
    		  a[k]+=s2[j]-'0';
    	     if(a[k]>=10)
    	     {
    		  a[k]=a[k]-10;
    		  a[k+1]=1;
    	     }
    	     k++;i--;j--;
    	}
    	if(a[k]==0)
    	     k=k-1;
    	while(k>=0)
    	     printf("%d",a[k--]);	
      	free(a);	
    	return 0;
    }

**大数减法**

#include"stdio.h"
    #include"string.h"
    #include"stdlib.h"
    int main()
    {
    	char s1[500],s2[500],t[500];
    	int flg=1,i,j,k=0,*a,n;
    	scanf("%s%s",s1,s2);
    	i=strlen(s1)-1;
    	j=strlen(s2)-1;
    	n=i>j? i:j;
    	a=(int*)malloc(n*sizeof(int));	
    	if(i==j)
    	{
    	     flg=strcmp(s1,s2);
    	     if(flg==0)
    		 printf("0");
    	}	
    	else
    	{
    	     if(i<j)
    	     {
    		 flg=-1;
    		 strcpy(t,s1);
    		 memset(s1,0,sizeof(s1));
    		 strcpy(s1,s2);
    		 memset(s2,0,sizeof(s2));
    		 strcpy(s2,t);
    		 k=i;
    		 i=j;
    		 j=k;k=0;
    	     }
    	     while(i>=0||j>=0)
    	     {
    		 if(i>=0&&j>=0)
    		 {
    		      a[k]=s1[i]-s2[j];
    		      if(a[k]<0)
    		      {
    			   a[k]=10+a[k];
    			   s1[i-1]=s1[i-1]-1;
    		      }
    		      j--;
    	         }
    	         else if(j<0)
    		      a[k]=s1[i]-'0';
    	         k++;i--;
    	     }
    	     k=k-1;
    	     i=k;
    	     while(i>0)
    	        if(a[i]>0)
    	        {
    		    k=i;i--;break;
    	        }			
    	     if(flg<0)
    	        printf("-");
    	     while(k>=0)
    	     {
    	        printf("%d",a[k]);
    	        k--;
    	     }	 	
    	}
        free(a);
        return 0;
    }

**大数乘法**

#include"stdio.h"
    #include"string.h"
    void mult(char a[],char b[],char s[])
    {
        int i,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0;
        char result[65];
        alen=strlen(a);blen=strlen(b); 
        for(i=0;i<alen;i++)
        	for(j=0;j<blen;j++)
    	    res[i][j]=(a[i]-'0')*(b[j]-'0');
        for(i=alen-1;i>=0;i--)
        {
            for(j=blen-1;j>=0;j--)
    	     sum=sum+res[i+blen-j-1][j];
            result[k]=sum%10;
            k=k+1;
            sum=sum/10;
        }
        for(i=blen-2;i>=0;i--)
        {
            for(j=0;j<=i;j++) 
    	    sum=sum+res[i-j][j];
            result[k]=sum%10;
            k=k+1;
            sum=sum/10;
        }
        if(sum!=0)
        {
    	 result[k]=sum; 
    	 k=k+1;
         }
        for(i=0;i<k;i++)
    	result[i]+='0';
        for(i=k-1;i>=0;i--)
    	s[i]=result[k-1-i];
        s[k]='\0';
        while(1)
        {
            if(strlen(s)!=strlen(a)&&s[0]=='0') 
                strcpy(s,s+1);
            else
                break;
        }
    }
    int main(){
    	char a[500],b[500],c[1100];
    	gets(a);
    	gets(b);
    	mult(a,b,c);
    	puts(c);
    	return 0;
    }

**大数除法**

#include"stdio.h"
    #include"string.h"
    #define MAXSIZE 200
    void div(char *str1, char *str2, char *str3)
    {
    	int i1,i2,i,j,jj,tag,carry,cf,c[MAXSIZE];
    	int len1 = strlen(str1), len2 = strlen(str2), lend;
    	char d[MAXSIZE];
    	memset(c, 0, sizeof(c));
    	memcpy(d, str1, len2);
    	lend = len2; j = 0;
    	for( i1=len2-1; i1 < len1; ++i1 ){
    	     if( lend < len2 ){
    		  d[lend] = str1[i1+1]; c[j] = 0;
    		  ++j; ++lend;
    	     }
    	     else if( lend == len2 )
    	     {
    		  jj = 1;
    		  for( i=0; i < lend; ++i )
    		  {
    		       if( d[i] > str2[i] ) break;
    		       else if( d[i] < str2[i] )
    		       {
    			    jj = 0; break;
    		       }
    		  }
    		  if( jj == 0 )
    		  {
    		       d[lend] = str1[i1+1]; c[j] = 0;
    		       ++j; ++lend;
    		       continue;
    		  }
    	     }
    	     if( jj==1 || lend > len2 )
    	     {
    		  cf = jj=0;
    		  while( d[jj] <= '0' && jj < lend )
    		       ++jj;
    		  if( lend-jj > len2 )
    		       cf = 1;
    		  else if( lend-jj < len2 ) 
    		       cf = 0;
    		  else
    		  {
    		       i2 = 0; cf = 1;
    		       for( i=jj; i < lend; ++i )
    		       {
    			    if( d[i] < str2[i2] )
    			    {
    				cf = 0; break;
    			    }
    			    else if( d[i] > str2[i2] )
    				break;				
    			    ++i2;
    		       }
    		  }//else
    		  while( cf )
    		  {
    		       i2 = len2-1; cf = 0;
    		       for( i=lend-1; i >= lend-len2; --i )
    		       {
    			    d[i] = d[i]-str2[i2]+'0';
    			    if( d[i] < '0' )
    			    {
    				d[i] = d[i]+10;  carry = 1;
    				--d[i-1];
    			    }
    			    else 
    			        carry = 0;
    			    --i2;
    		       }
    		       ++c[j]; jj=0;
    		       while( d[jj] <= '0' && jj < lend )
    			    ++jj;
    		       if( lend-jj > len2 ) 
    			    cf = 1;
    		       else if( lend-jj < len2 ) 
    			    cf = 0;
    		       else
    		       {
    			    i2 = 0; cf = 1;
    			    for( i=jj; i < lend; ++i )
    			    {
    				 if( d[i] < str2[i2] )
    				 {
    				      cf = 0; break;
    				 }
    				 else if( d[i] > str2[i2] )
    				      break;
    				 ++i2;
    			    }
    		       }
    		  }
    		  jj = 0;
    		  while( d[jj] <= '0' && jj < lend )
    		       ++jj;
    		  for( i=0;i < lend-jj; ++i )
    		       d[i] = d[i+jj];
    		  d[i] = str1[i1+1];  
    		  lend = i+1;
    		  ++j;
    	     }
    	}
    	i = tag = 0;
    	while(c[i] == 0 )
    	    ++i;
    	for( ; i < j; ++i, ++tag ) 
    	    str3[tag] = c[i]+'0';
    	str3[tag] = '\0';
    }
    int main(){
    	char a[MAXSIZE],b[MAXSIZE],c[MAXSIZE];
    	scanf("%s%s",a,b);
    	div(a,b,c);
    	puts(c);
    	return 0;
    }