首页 > 代码库 > 算法之大数问题

算法之大数问题

2024-07-05 09:49:55   227人阅读

<1>大数相加

[cpp] view plaincopy
  1. #include<stdio.h>  
  2. #include<string.h>  
  3.   
  4. char a[10001],b[10001],sum[10002];  
  5.   
  6. int BigIntegerAdd(){  
  7.     //两个数的长度  
  8.     int lena = strlen(a);  
  9.     int lenb = strlen(b);  
  10.     //进位标记  
  11.     int c = 0;  
  12.     int i,j,k;  
  13.     //初始化数组sum  
  14.     memset(sum,0,10001);  
  15.     //倒序相加  
  16.     k = 0;  
  17.     for(i = lena-1,j = lenb-1;i >= 0 && j >= 0;i--,j--){  
  18.         sum[k] = a[i] + b[j] - ‘0‘ + c;  
  19.         c = 0;  
  20.         //如果相加大于等于10  
  21.         if(sum[k] > ‘9‘){  
  22.             sum[k] -= 10;  
  23.             c = 1;  
  24.         }  
  25.         k++;  
  26.     }  
  27.     //a > b  
  28.     while(i >= 0){  
  29.         sum[k] = a[i] + c;  
  30.         c = 0;  
  31.         //如果相加大于等于10  
  32.         if(sum[k] > ‘9‘){  
  33.             sum[k] -= 10;  
  34.             c = 1;  
  35.         }  
  36.         k++;  
  37.         i--;  
  38.     }  
  39.     //b > a  
  40.     while(j >= 0){  
  41.         sum[k] = b[j] + c;  
  42.         c = 0;  
  43.         //如果相加大于等于10  
  44.         if(sum[k] > ‘9‘){  
  45.             sum[k] -= 10;  
  46.             c = 1;  
  47.         }  
  48.         k++;  
  49.         j--;  
  50.     }  
  51.     //如果最后两个数相加有进位的情况  
  52.     //例如：67 + 51：5+6有进位  
  53.     if(c == 1){  
  54.         sum[k++] = ‘1‘;  
  55.     }  
  56.     //翻转  
  57.     char temp;  
  58.     for(i = 0,j = k-1;i < j;i++,j--){  
  59.         temp = sum[i];  
  60.         sum[i] = sum[j];  
  61.         sum[j] = temp;  
  62.     }  
  63.     return 0;  
  64. }  
  65.   
  66. int main(){  
  67.     while(scanf("%s %s",a,b) != EOF){  
  68.         BigIntegerAdd();  
  69.         puts(sum);  
  70.     }  
  71. }  


<2>大数相减

[cpp] view plaincopy
  1. /* 
  2. 1.比较减数与被减数的长度,确定正负号 
  3. 2.模拟减法运算 
  4.     (1)a[i] == b[j]  
  5.     (2)a[i] < b[j] //借位 
  6.     (3)a[i] > b[j]  
  7.  */  
  8. #include<stdio.h>  
  9. #include<string.h>  
  10.   
  11. char a[10001],b[10001],sum[10001],temp[10001];  
  12.   
  13. int BigIntegerMinus(){  
  14.     //两个数的长度  
  15.     int lena = strlen(a);  
  16.     int lenb = strlen(b);  
  17.     //借位标记  
  18.     int c = 0;  
  19.     int i,j,k,positive = 1;  
  20.     //判断正负号  
  21.     if(lena < lenb || (lena == lenb && strcmp(a,b) < 0) ){  
  22.         strcpy(temp,a);  
  23.         strcpy(a,b);  
  24.         strcpy(b,temp);  
  25.         positive = -1;//负号  
  26.         lena = strlen(a);  
  27.         lenb = strlen(b);  
  28.     }  
  29.     //倒序相减   
  30.     k = 0;    
  31.     for(i = lena-1,j = lenb-1;i >= 0 && j >= 0;i--,j--){    
  32.         sum[k] = a[i] - b[j] + ‘0‘ + c;    
  33.         c = 0;    
  34.         //如果相减小于0    
  35.         if(sum[k] < ‘0‘){    
  36.             sum[k] += 10;    
  37.             c = -1;    
  38.         }    
  39.         k++;    
  40.     }    
  41.     //a > b    
  42.     while(i >= 0){    
  43.         sum[k] = a[i] + c;    
  44.         c = 0;    
  45.         //如果相减小于0    
  46.         if(sum[k] < ‘0‘){    
  47.             sum[k] += 10;    
  48.             c = -1;    
  49.         }    
  50.         k++;    
  51.         i--;    
  52.     }    
  53.     //b > a    
  54.     while(j >= 0){    
  55.         sum[k] = b[j] + c;    
  56.         c = 0;    
  57.         //如果相减小于0    
  58.         if(sum[k] < ‘0‘){    
  59.             sum[k] += 10;    
  60.             c = -1;    
  61.         }    
  62.         k++;    
  63.         j--;    
  64.     }  
  65.     int index = k - 1;  
  66.     //检索高位，有可能相减为0  
  67.     while(sum[index] == ‘0‘ && index > 0){  
  68.         index--;  
  69.     }  
  70.     //正号  
  71.     if(positive == 1){  
  72.         sum[index+1] = ‘\0‘;  
  73.     }  
  74.     //负号  
  75.     else{  
  76.         sum[++index] = ‘-‘;  
  77.         sum[index+1] = ‘\0‘;  
  78.     }  
  79.     //翻转  
  80.     char t;  
  81.     for(i = 0,j = index;i < j;i++,j--){  
  82.         t = sum[i];  
  83.         sum[i] = sum[j];  
  84.         sum[j] = t;  
  85.     }  
  86.     return 0;  
  87. }  
  88.   
  89. int main(){  
  90.     while(scanf("%s %s",a,b) != EOF){  
  91.         BigIntegerMinus();  
  92.         puts(sum);  
  93.     }  
  94. }  

<3>大数乘法

[cpp] view plaincopy
  1. #include<stdio.h>  
  2. #include<string.h>  
  3.   
  4. char a[10001],b[10001],c[20002];  
  5.   
  6. int BigIntegerMulti()  
  7. {  
  8.     int i,j,lena,lenb,lenc;  
  9.     //初始化  
  10.     memset(c,‘0‘,20002);  
  11.     //两个数的长度  
  12.     lena = strlen(a);  
  13.     lenb = strlen(b);  
  14.     //乘积最大位数  
  15.     lenc = lena + lenb - 1;  
  16.     //翻转    
  17.     char temp;    
  18.     for(i = 0,j = lena-1;i < j;i++,j--){    
  19.         temp = a[i];    
  20.         a[i] = a[j];    
  21.         a[j] = temp;    
  22.     }    
  23.     for(i = 0,j = lenb-1;i < j;i++,j--){    
  24.         temp = b[i];    
  25.         b[i] = b[j];    
  26.         b[j] = temp;    
  27.     }   
  28.     //倒序相乘  
  29.     /* 
  30.           123 
  31.         *  54 
  32.         ------ 
  33.           492 
  34.          615 
  35.         ----- 
  36.          6642  
  37.     */  
  38.     int t;  
  39.     for(i = 0;i < lena;i++){  
  40.         for(j = 0;j < lenb;j++){  
  41.             /* c[i+j] = (a[i] - ‘0‘) * (b[j] - ‘0‘) + c[i+j];  
  42.                9 * 9 + ‘0‘ 超出char范围越界所以设置一个int临时变量t    */  
  43.             t = (a[i] - ‘0‘) * (b[j] - ‘0‘) + c[i+j] - ‘0‘;  
  44.             //进位  
  45.             c[i+j+1] = t / 10 + c[i+j+1];  
  46.             c[i+j] = t % 10 + ‘0‘;  
  47.         }  
  48.     }  
  49.     //确定乘积的位数  
  50.     while(c[lenc] == ‘0‘ && lenc >0){  
  51.         lenc--;  
  52.     }  
  53.     //注意：加‘\0‘  
  54.     c[lenc+1] = ‘\0‘;  
  55.     //翻转  
  56.     for(i = 0,j = lenc;i < j;i++,j--){    
  57.         temp = c[i];    
  58.         c[i] = c[j];    
  59.         c[j] = temp;    
  60.     }   
  61.     return 0;  
  62. }  
  63.   
  64. int main(){  
  65.     while(scanf("%s %s",a,b) != EOF){  
  66.         BigIntegerMulti();  
  67.         puts(c);  
  68.     }  
  69.     return 0;  
  70. }  


自己写的如有问题，请告知一下。


联系
我们