C语言笔记：高精度计算问题

本是古典何须时尚 2023-05-31 10:18 41阅读 0赞

### 文章目录 ###

*  C语言中大数据类型的简述
 *  5种有符号整数类型以及2种浮点类型所占字节数以及数据范围
 *  高精度加法
 *  高精度减法
 *  高精度乘法
 *  高精度阶乘
 *  高精度除法
 *   *  高精度数除以低精度数

# C语言中大数据类型的简述 #

我们知道，计算机内部直接使用int或者double等数据类型存储数据是有范围限制的，当运算数据较大时，计算机将会出现溢出情况，使得计算结果不够精确。例如，一个20位的十进制整数，如果用int类型变量存放，就会出现数据溢出。当运算数超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在运算过程中，能表示大数的数据类型有两种：整型数组和字符串

*  整型数组：每个元素存储1位，有多少位就需要多少个数组元素；每一位都是数的形式，可直接加减，运算时非常方便，但整型数组不能直接输入全部元素，只能一个一个输入，并且输入时，每两位数之间必须有分隔符，不符合人们输入数值的习惯，输入输出时不方便。
 *  字符串（本质上是一个字符数组）：字符串的最大长度是多少，就可以表示多少位数字。用字符串表示数值能将全部位直接输入输出，但字符串中的每一个位是一个字符，必须将它转换为数值再进行运算，运算时不方便

综合整型数组和字符数组的优缺点来看，我们在接下来的问题中，用字符串读入数据，运算时转存到整型数组中进行运算，接着再转换为字符串进行输出。

事实上，高精度运算就是通过编程的方法，把简单数学的运算步骤在计算机上完美地演示一遍而已。

# 5种有符号整数类型以及2种浮点类型所占字节数以及数据范围 #

#include <stdio.h>
    #include <limits.h>//该文件包含了CHAR_MIN、INT_MIN等宏
    #include <float.h>//包含FLT_MIN,FLT_MAX宏定义
    int main()
    { 
     printf("整数类型：\n");
     printf("signed char所占字节数：%d,数据范围：【%d,%d】\n",sizeof(signed char),SCHAR_MIN,SCHAR_MAX);
     printf("short 所占字节数：%d,数据范围：【%d,%d】\n",sizeof(short),SHRT_MIN,SHRT_MAX);
     printf("int 所占字节数：%d,数据范围：【%d,%d】\n",sizeof(int),INT_MIN,INT_MAX);
     printf("long 所占字节数：%d,数据范围：【%ld,%ld】\n",sizeof(long),LONG_MIN,LONG_MAX); 
     printf("long long 所占字节数：%d,数据范围：【%lld,%lld】\n",sizeof(long long),LLONG_MIN,LLONG_MAX); 
     printf("\n浮点类型：\n");
     printf("float 所占字节数：%d,数据范围：【%e,%e】，有限存储精度为6位\n",sizeof(float),FLT_MIN,FLT_MAX); 
     printf("double 所占字节数：%d,数据范围：【%e,%e】，有限存储精度为15位\n",sizeof(double),DBL_MIN,DBL_MAX); 
        return 0;
    }

输出：  
![在这里插入图片描述][20191026084349205.png]  
这里需要主要的是：float类型的6位精度是指能够表示33.3333333的前6位数字，而不是精确到小数点后6位。

# 高精度加法 #

问题描述：  
求两个不超过200位的非负整数的和。输入两行，每行是一个不超过200位的非负整数，没有多余的前导0；输出计算式以及相加后的结果，结果里面不能有多余的前导0。

问题分析：  
用一个字符串来保存一个不超过200位大整数的数值，然后为了运算时方便，将存储大整数的字符串转移到整数数组中保存。同时因为两个数相加时要先个位对齐，然后再从低位向高位计算，而实际上在用户输入时，整数数组下标为0对应最高位，而整数数组下标最大的对应个位，所以将存放加数的字符串转移到整数数组时，要先逆置转换，即整数数组下标为0对应个位，而整数数组下标为1对应十位。。。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]

#include <stdio.h>
    #include <string.h>
    #define MAXLEN 210
    void Invert(char *a,int *b);//将a字符逆置转换到整数数组b中，确保下标0对应个位而不是最高位 
    void Output(int *p,int len);//输出整型数组元素 
    int main(void)
    { 
     char str1[MAXLEN],str2[MAXLEN],str[MAXLEN];//存放两个加数（输入）以及和（输出）的字符串
     int a[MAXLEN],b[MAXLEN],c[MAXLEN];//存放加数以及和的整型数组（中间处理） 
     printf("输入两个加数：\n");
     scanf("%s %s",str1,str2);
     //整型数组a,b,c的元素全部清零,memset函数一般用于在对定义的字符串进行初始化为"\0"，对较大的结构体或数组进行清0操作的一种最快方法 
     memset(a,0,sizeof(a));
     memset(b,0,sizeof(b)); 
     memset(c,0,sizeof(c));
     //将两个加数字字符串按位逆置存放到整型数组中，下标0对应个位
     Invert(str1,a);
     Invert(str2,b);
     printf("******************运算过程（列竖式做加法）******************\n");
     Output(a,strlen(str1));
     printf("\n");
     Output(b,strlen(str2));
     int len=strlen(str1)>=strlen(str2) ? strlen(str1):strlen(str2);//求加数较长的位数
     for(int i=0;i<len;i++)//从第一位到最高位逐位相加运算 
     { 
      c[i]+=a[i]+b[i];
      c[i+1]=c[i]/10;//c[i]能除多少个10就表示进多少个位，i位的进位数存放到c[i+1]上
      c[i]%=10; //c[i]进完位后的数则是(a[i]+b[i])求模10，为余下的数 
     } 
     printf("\n");
     Output(c,len);
     printf("\n******************运算过程******************");
     while(len>=0&&c[len]==0)//和的处理，去掉前导0，并把结果复制到串中
     { 
      len--;
     } 
     memset(str,0,sizeof(str));//0<=>'\0'字符串结束符 
     int i=0;
     for(int j=len;j>=0;j--)
     { 
      str[i++]=c[j]+'0';//整型数字转换为字符型数字 
     } 
      if(strlen(str)==0)
     { 
      str[0]='0';//结果为0的情况 
     }
     printf("\n");
     printf("运算结果：%s + %s = %s\n",str1,str2,str);
     return 0;
    } 
    void Invert(char *a,int *b)
    { 
     int len=strlen(a),j=0;
     for(int i=len-1;i>=0;i--)
     { 
      b[j++]=a[i]-'0';
     }
    }
    void Output(int *p,int len)
    { 
     for(int i=0;i<len;i++)
     { 
      printf("%d",p[i]);
     }
    }

运算输出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 1]  
代码释疑：  
整数数组怎么具体运算呢？即模拟小学生列竖式做加法的方法，个位对齐，从个位开始向高位逐位对应位相加，和大于或等于10则进位。在下面的源代码中，用int a\[210\]保存第一个加数，int b\[210\]保存第二个加数，然后逐位相加，两数相加的结果存储在int c\[210\]中，其中下面代码段要处理的就是进位情况

for(int i=0;i<len;i++)//从第一位到最高位逐位相加运算 
     {
      c[i]+=a[i]+b[i];
      c[i+1]=c[i]/10;//c[i]能除多少个10就表示进多少个位，i位的进位数存放到c[i+1]上
      c[i]%=10; //c[i]进完位后的数则是(a[i]+b[i])求模10，为余下的数 
     }

# 高精度减法 #

#include <stdio.h>
    #include <string.h> 
    #define N 1000
    char sa[202],sb[202],sc[202];
    int a[202],b[202],c[202];
    int main(void)
    { 
     printf("请输入被减数与减数（之间用空格隔开）：");
     scanf("%s %s",sa,sb);
     int alen=strlen(sa),blen=strlen(sb),len;
     char cfh='+';//存放结果正负符号 
     if(alen==blen&&strcmp(sa,sb)==0)//被减数等于减数的情况 
     { 
      printf("0\n"); 
      return 0;
     }
     else if(alen<blen||alen==blen&&strcmp(sa,sb)<0)//①减数的位数大于被减数或者②两数位数相等，减数大于被减数 
     { 
      char st[202];//临时字符串数字，用于交换char sa与char sb
      strcpy(st,sa);strcpy(sa,sb);strcpy(sb,st); //保证字符数组sa的位数始终是最大的位数 
      cfh='-';
     }
     alen=strlen(sa);blen=strlen(sb);
     for(int i=0;i<alen;i++)
     { 
      a[i]=sa[alen-1-i]-'0';//将char sa[]逆置存放到int a[]中 
     }
     for(int i=0;i<blen;i++)
     { 
      b[i]=sb[blen-1-i]-'0';
     }
     for(int i=0;i<alen;i++)//开始对int a[],b[],c[]逐位进行减法运算 
     { 
      c[i]=c[i]+a[i]-b[i];
      if(c[i]<0)//处理退位 
      { 
       c[i]+=10;
       c[i+1]--;
      }
     }
     int i=alen-1;//将结果去掉前导0后存放到sc中
     while(c[i]==0)
     { 
      i--;
     }
     int j=0;
     while(i>=0)
     { 
      sc[j++]=c[i]+'0';
      i--;
     }
     sc[j]='\0';//字符串单个赋值不会自动加上字符串结束符'\0'，如果之前有memset(sc,0,sizeof(sc))，则不需要该行语句
     if(strlen(sc)==0)
     { 
      printf("0\n");
     } 
     else
     { 
      printf("结果为："); 
      if(cfh=='-')
      { 
       printf("-");
      }
      printf("%s\n",sc);
     }
     return 0;
    }

输出：  
![在这里插入图片描述][20191027094406362.png]

# 高精度乘法 #

问题描述：  
求两个不超过1000位的大整数的乘积。输入两行，每行是一个不超过1000位的整数，没有多余的前导0；输出算式以及相乘后的结果。结果里不能有多余的前导0。

问题分析：  
此处乘法要考虑正负号，数据结构不变，要考虑的只是将算法改变为乘法运算的模拟过程：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 2]

#include <stdio.h>
    #include <string.h>
    #define MAXLEN 1001
    void Output(int *p,int len);//输出整型数组元素 
    void Invert(char *a,int *b);//将a字符逆置转换到整数数组b中，确保下标0对应个位而不是最高位 
    char str1[MAXLEN],str2[MAXLEN],str[2*MAXLEN];//存放乘数字符串以及乘积对应的字符串
    int a[MAXLEN],b[MAXLEN];//存放运算时乘数的各个位
    int c[2*MAXLEN];//存放运算后乘积的各个位
    int main(void)
    { 
     printf("请输入两个乘数：\n");
     scanf("%s %s",str1,str2);//以字符串的形式输入两个乘数 
     int len1=strlen(str1),len2=strlen(str2);
     /*确定乘积的符号 */
     int sign=1,k=0;//sign标识结果的正负，k用于将字符串首地址向后移动k位 
     memset(a,0,sizeof(a));//整型数组a,b清0 
     memset(b,0,sizeof(b));//整型数组a,b清0 
     if(str1[0]=='-')
     { 
      len1--;
      sign*=-1;
      k++;
     } 
     Invert(str1+k,a);
     k=0;
     if(str2[0]=='-')
     { 
      len2--;
      sign*=-1;
      k++;
     } 
     Invert(str2+k,b);
     /*确定乘积的符号 */
    // Output(a,len1);
    // Output(b,len2); 
     /*逐位运算，没有处理进位*/
     memset(c,0,sizeof(c));
     for(int i=0;i<len2;i++)
     { 
      for(int j=0;j<len1;j++)
      { 
       c[i+j]+=a[j]*b[i];
      } 
     }
     /*逐位运算，没有处理进位*/
     /*处理进位*/
     for(int i=0;i<len1+len2;i++)
     { 
      c[i+1]+=c[i]/10;
      c[i]%=10;
     }
     /*处理进位*/
     /*结果处理，将最高位(len1+len2-1)前导0去掉后，转换成字符存储到积串str中*/
     int i=len1+len2-1,j=0;
     while(c[i]==0)
     { 
      i--;
     }
     memset(str,0,sizeof(str));
     for(;i>=0;i--)
     { 
      str[j++]=c[i]+'0';//整型数字转换为字符型数字 
     }
     /*结果处理，将最高位(len1+len2-1)前导0去掉后，转换成字符存储到积串str中*/ 
     /*输出运算结果*/
     if(strlen(str)==0)//结果为0的情况 
     { 
      str[0]='0';
     }
     printf("%s * %s = ",str1,str2);
     if(sign==-1)
     { 
      printf("-");
     }
     printf("%s \n",str);
     /*输出运算结果*/
     return 0;
    }  
    void Invert(char *a,int *b)
    { 
     int len=strlen(a),j=0;
     for(int i=len-1;i>=0;i--)
     { 
      b[j++]=a[i]-'0';
     }
    }
    void Output(int *p,int len)
    { 
     for(int i=0;i<len;i++)
     { 
      printf("%d",p[i]);
     }
    }

输出：  
![在这里插入图片描述][20191025082906908.png]

# 高精度阶乘 #

问题描述：  
求10000以内整数n的阶乘，输入一个整数n（n<=n<=10000）。输出n!的值  
问题分析：  
10000以内的整数可以Int类型变量存储，但它的阶乘结果却会很大，如15！的值就已经是13位数字了。

#include <stdio.h>
    int main()
    { 
        int i,n;
        double sum=1;//阶乘结果肯定非常大，所以用更大存储范围的double类型
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            sum=sum*i;
        printf("%d!=%lf",n,sum);
        printf("\n");
        return 0;
    }

输出：  
![在这里插入图片描述][20191026085021809.png]  
由前面的各个数据类型输出值可知，若用int或者float（【-2147483648,2147483647】）声明sum变量，输出的15位数字肯定不能用10位数字来存储，所以用double等更大存储类型来声明变量sum，欲存储比double类型更多位的数，只能用整形数组或者字符串来表示了。此处我们想到用整形数组存放n!的各个位，假设阶乘结果不超过3000位，定义int result\[3000\]存放n!的各个位，result\[0\]对应n!的个位，初始时result\[0\]=1表示累乘前的初始值，digits=1表示结果的位数。这里也涉及进位的问题，具体方法和手动计算n!的方法差不多，每乘一个数i时，从下标0（个位）开始遍历，遍历到下标为digits-1就可以了，每遍历一位，要计算当前位与i相乘，考虑进位情况，并计算出进位值以及进位后当前位的值。

#include <stdio.h>
    #include <string.h>
    #include <limits.h>
    #define N 3000
    int result[N];//存放n!值的各个位上的数，result[0]存放个位 
    int main(void)
    { 
     int n;//存放n 
     printf("计算n!,输入n的值：");//提示输入n
     scanf("%d",&n);
     memset(result,0,N);
     result[0]=1;//累乘器初始化赋值为1
     int digits=1;//存放结果的位数，初始化时位数为1
     for(int i=2;i<=n;i++)//i存放每次阶乘的操作数（1*2*3...*n） 
     { 
      int jw=0;//jw存放低位向高位的进位数
      for(int j=0;j<digits;j++)//将result从个位起至第digits位依次乘以i 
      { 
       int total=result[j]*i+jw;
       result[j]=total%10;//int result[0]存放运算结果的个位，result[1]存放十位 
       jw=total/10;
       if(j==digits-1&&jw)
       { 
        digits++;
       }
      } 
     }
     char factarr[N];//存放result的字符串
     memset(factarr,0,N);
     for(int i=digits-1,j=0;i>=0;i--)
     { 
      factarr[j++]=result[i]+'0';//int result[]转换为char factarr[]，并且char factarr[0]存放运算结果最高位.... 
     }
     printf("%d!=%s\n",n,factarr);//输出n!= factarr
     return 0;
    }

输出：  
![在这里插入图片描述][20191026093529492.png]

# 高精度除法 #

## 高精度数除以低精度数 ##

问题描述：  
已知被除数为位数不超过1000的正整数，除数是位数小于10的正整数，求它们的商（取整）。

问题分析：  
采用整数相除的手动计算模拟法，即“按位相除法”。两个正整数做除法时，每位商的值都是0~9的数，每次每次求得的余数与后面的若干位连接后得到新的被除数，继续做除法。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 3]

#include <stdio.h>
    #include <string.h>
    #define MAXLEN 1010
    char str1[MAXLEN];//以字符串存放高精度被除数
    int main(void)
    { 
    	int b;//存放低精度除数
    	printf("请输入被除数和除数：\n");
    	scanf("%s %d",str1,&b);
    	int a[MAXLEN],c[MAXLEN];//元素值分别存放被除数以及商的各个位对应整数
    	memset(a,0,sizeof(a));//数组元素值初始化为0 
    	memset(c,0,sizeof(c));//数组元素值初始化为0 
    	int len1=strlen(str1);
    	for(int i=0;i<len1;i++)
    	{ 
    		a[i]=str1[i]-'0';//将被除数str1的数值，按各个位转换为整型对应存放到整型数组a[]中 ,a[0]为最高位 
    	}
    	int x=0;//存放每次做除法时的被除数 
    	for(int i=0;i<len1;i++)//从高位向低位按位相除,"按位相除法"四行代码搞定 
    	{ 
    		c[i]=(x*10+a[i])/b;
    		x=(x*10+a[i])%b;
    	}
    	//删除商前导0，将商存放到串中并输出式子以及商
    	int len=0;
    	while(c[len]==0&&len<len1)
    	{ 
    		len++;
    	} 
    	char str[MAXLEN];//存放字符串类型的商
    	memset(str,0,sizeof(str));
    	for(int i=len,j=0;i<len1;i++)
    	{ 
    		str[j++]=c[i]+'0';
    	} 
    	printf("%s / %d = %s\n",str1,b,str);
    	return 0;
    }

输出：  
![在这里插入图片描述][20191026154147916.png]

[20191026084349205.png]: /images/20230531/73bfc856e96b49b79fbfc541ab552c68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]: /images/20230531/711d03de85564170a42681e4e0e73cff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 1]: /images/20230531/355f91c120794e6c88e95758a5679e25.png
[20191027094406362.png]: /images/20230531/ae74b703b0074f3e9ed8b0d4c0fc35ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 2]: /images/20230531/6514786ec118431ea5a413501cab1ff7.png
[20191025082906908.png]: /images/20230531/9ff701096f78436f88bf8a016c4845cf.png
[20191026085021809.png]: /images/20230531/f371bbd2a02a46689b61430d9071e598.png
[20191026093529492.png]: /images/20230531/7b41f31943d942abb0ff832dec42eb5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70 3]: /images/20230531/58413d34f81f4d9488638cd852bb7772.png
[20191026154147916.png]: /images/20230531/6f056f76254146028c5f9263087143d2.png