【algorithm】算法基础课---高精度问题（附笔记 | 建议收藏）

àì夳堔傛蜴生んèń 2024-03-31 13:45 67阅读 0赞

## 系列文章目录 ##

[第一节快速排序][Link 1]  
[第二节二分法][Link 2]

--------------------

![在这里插入图片描述][0dead988b1f04c3bb7496eacff42e7a2.jpeg_pic_center]  
**学习路上的风景，我陪你一起去看，编程路上的算法，我陪你一起去学，朋友们你们好，我是夏目浅石，蟹蟹你点开文章和我一同进步，加油！遇见更好的自己。**

#### 文章目录 ####

*  系列文章目录
 *  前言
 *  一、高精度加法
 *  二、高精度减法
 *  三、高精度乘法
 *  四、高精度除法
 *  总结
 *   *  下期预告

--------------------

## 前言 ##

今天学了一些高精度问题的方法这里给大家分享一下，希望大家也可以学习并且掌握。

--------------------

`提示：以下是本篇文章正文内容，下面案例可供参考`

## 一、高精度加法 ##

**知识点如下：**  
![在这里插入图片描述][02f04340a01f49528e6173357e177b07.png]  
这是我在AcWing打卡界面总结的一些我自己的想法和思路，希望大家可以看完，接下来就是题目的讲解和代码；

1.输入的scanf还是效率很高的.并且有时候gets函数没办法使用，所以scanf，是一个挺好用的办法  
2.char类型的输入方便输入更高位数，然后再减去‘0’的ASCII码值就能转换成想要的了。  
3.核心的高精度算法–>就是每一个位数相加再加进位，然后再去莫10就是这个位数的答案了，再把进位除去10就是下一位的进位，依次类推就行…  
4.输出的时候就是按照人类的习惯输出就好，就是倒着输出.

**题目如下：**  
![在这里插入图片描述][b51a13431e1a453ea2c7e91ce85852f9.png]

> 代码如下（示例）：

#include<stdio.h>
    #include<string.h>
    int main()
    {
        
        char arr1[100010],arr2[100010];
        scanf("%s",arr1);
        scanf("%s",arr2);
        int a[100010],b[100010],c[100010],len1=strlen(arr1),len2=strlen(arr2),i,j,k=0,t=0;
        for(i=len1-1,j=0;i>=0;i--) a[j++]=arr1[i]-'0';
        for(i=len2-1,j=0;i>=0;i--) b[j++]=arr2[i]-'0';
        for(i=0;i<len1||i<len2;i++)
        {
        
            if(i<len1) t=t+a[i];
            if(i<len2) t=t+b[i];
            c[k++]=t%10;
            t=t/10;
        }
        if(t) c[k++]=1;
        for(i=k-1;i>=0;i--) printf("%d",c[i]);
        return 0;
    }

## 二、高精度减法 ##

**知识点如下：**  
![在这里插入图片描述][0a151f32f9b24bb8937dc170feb2be39.png]

之前看过许多博客关于这些高精度的，但是都是模棱两可，不是太理解，今天学了一下y总的高精度，大抵是懂了，这就来分享给大家让大家学习了。  
总结：  
1.我想就是拆分模块来写这一个算法，第一就是main函数，这里处理输入和调用函数的功能(作用)，过多细节就看代码就行  
2.讲解一下最先出现的cmp函数和后面出现的sub函数  
@1.cmp函数就是比较这一串数字的长度以及大小这个功能，你先看俩字符串是否相同长度，不相同则长的一定大。  
当长度相同时就需要比较两者的最高位是否相同(或者谁大谁小)，依次类推直到找到不同则 return 1 or 0，这个函数尽量做到的是 c=a-b;a>=b。  
@2.sub函数就是做减法对吧，根据cmp函数就是a-b这样，所以根据人的习惯啊，当3-5的时候人往往会变成-(5-3)这样去计算，所以就分成两种情况即：a开始就大于b，和a一开始小于b两种情况，所以一种需要先打印’-‘然后打印数字，另一种则不需要打印’-‘对吧？  
3.高精度减法的核心算法：  
两个数的低位相减然后看是否为负数，如果为负数则需要借10，则进位为1.  
两个数的低位相减然后看是否为非负数，如果为非负数则不需要借10，且进位为0.  
然后就是扫除前导零输出就可以了.

**题目如下：**  
![在这里插入图片描述][d8109df3283c41bdb0876f134be973d8.png]

> 代码如下（示例）：

#include<stdio.h>
    #include<string.h>
    //c=a-b;a>=b;
    int cmp(char arr1[],char arr2[],int len1,int len2)
    {
        
        if(len1!=len2)
        {
        
            if(len1>len2) return 1;
            else return 0;
        }
    
        for(int i=0;i<len1;i++)
        {
        
            if(arr1[i]!=arr2[i])
            {
        
                if(arr1[i]>arr2[i]) return 1;
                else return 0;
            }
        }
    }
    void sub(int a[],int b[],int len1,int len2)
    {
        
        int c[100010],t=0;
        for(int i=0;i<len1;i++)
        {
        
            t=a[i]-t;
            if(i<len2)
            {
        
                t=t-b[i];
            }
            c[i]=(t+10)%10;
            if(t<0) t=1;
            else t=0;
        }
        while(c[len1-1]==0&&len1-1>0) len1--;
        for(int i=len1-1;i>=0;i--)
        {
        
            printf("%d",c[i]);
        }
    }
    
    int main()
    {
        
        //输入 
        char arr1[100010],arr2[100010];
        int a[100010],b[100010];
        scanf("%s",arr1);
        scanf("%s",arr2);
        int len1=strlen(arr1),len2=strlen(arr2);
    
        for(int i=len1-1,j=0;i>=0;i--) a[j++]=arr1[i]-'0';
        for(int i=len2-1,j=0;i>=0;i--) b[j++]=arr2[i]-'0';
    
        if(cmp(arr1,arr2,len1,len2))
        {
        
            sub(a,b,len1,len2);
        }
        else
        {
        
            printf("-");
            sub(b,a,len2,len1);
        }
        return 0;
    }

## 三、高精度乘法 ##

**知识点如下：**  
![在这里插入图片描述][db2887f6f3a543a4aace586f5769b6ae.png]

类似于加法，会加法这个乘法真的非常简单。  
总结：  
1.输入的处理；  
2.拿b去和数组a的每一位去乘，然后就是莫10放到c数组里面，然后让进位/10就是下一个数的进位了

**题目如下：**  
![在这里插入图片描述][7a88494de09b4984b899da7c4c3c8a81.png]

代码如下（示例）：

#include<stdio.h>
    #include<string.h>
    const int N=100010;
    void cheng(int a[],int b,int len)
    {
        
        int c[N],i,t=0;
        for(i=0;i<len||t;i++)
        {
        
            if(i<len) 
            t=a[i]*b+t;
            c[i]=t%10;
            t/=10;
        }
        while(c[i]==0&&i>0) i--;
        for(int j=i;j>=0;j--) printf("%d",c[j]);
    }
    int main()
    {
        
        char arr[N];
        scanf("%s",arr);
        int b,a[N],len=strlen(arr),i,j;
        scanf("%d",&b);
        for(i=strlen(arr)-1,j=0;i>=0;i--) a[j++]=arr[i]-'0';
        cheng(a,b,len);
        return 0;
    }

该处使用的url网络请求的数据。

--------------------

## 四、高精度除法 ##

**知识点如下：**  
![在这里插入图片描述][5f6ad02223f0421582ddd387e001bd17.png]

高精度除法我感觉理解了这个过程其实这个题就不难，下main我来讲解一下吧hhh~  
总结：  
1.这里其实我想讲一讲最最重要的核心算法部分  
这里其实就是理解t是除法做完商的余数，然后余数乘10+下一位数字就是新的被除数，依次类推，直到退出循环为止，下面只需要处理前导零，就可以输出啦！

**题目如下：**  
![在这里插入图片描述][421963cd75334a269b93c05e046e5899.png]

代码如下（示例）：

#include<stdio.h>
    #include<string.h>
    void chu(int a[],int b,int len)
    {
        
    	int c[100010],t=0;
    	for(int i=len-1;i>=0;i--)
    	{
        
    		t=t*10+a[i];
    		c[i]=t/b;
    		t%=b;
    	}
    	while(c[len-1]==0&&len-1>0) len--;
    	for(int i=len-1;i>=0;i--) printf("%d",c[i]);
    	printf("\n"); printf("%d",t);
    }
    int main()
    {
        
    	char arr[100010];
    	int b,a[100010],len;
    	scanf("%s",arr);
    	scanf("%d",&b);
    	len=strlen(arr);
    	for(int i=len-1,j=0;i>=0;i--) a[j++]=arr[i]-'0';
    	chu(a,b,len);
    	return 0;
    }

## 总结 ##

**自己的感想：**  
这里为了大家方便大家复习我会给出我的acwing的地址想去看的话就去看看，当然也可以去acwng报名自己学然后再看我的博客这样会效果更好，不理解的咱们一起讨论学习，我觉得会很不错hhh~  
知识点图片汇总  
**思维导图**  
![在这里插入图片描述][a97bd4cfbe4f446eb2e77a4d7b8e9e47.png]  
记住这里面我是没有把核心算法家里面的，因为这只是一个宏观的导图，最重要的还是把我在acwing上的知识总结好好理解消化一下，这样才能获得收获hhh~咱们下一期见吧！

### 下期预告 ###

**前缀和与差分，欢迎来看哦hhh拜拜啦大家！**

[Link 1]: https://blog.csdn.net/congfen214/article/details/127973670
[Link 2]: https://blog.csdn.net/congfen214/article/details/128078143
[0dead988b1f04c3bb7496eacff42e7a2.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6756ddaed95a46d287ddb3424e3bda3d.jpeg
[02f04340a01f49528e6173357e177b07.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/5d688f08ae8e49efa6c116187d0e48cf.png
[b51a13431e1a453ea2c7e91ce85852f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/adbabb655d1d430f935dc2765d1d4fe7.png
[0a151f32f9b24bb8937dc170feb2be39.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d235f467bb5d403ea9d317fa43908eb8.png
[d8109df3283c41bdb0876f134be973d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/accbfe96b34c4d8e926cb75be281b78e.png
[db2887f6f3a543a4aace586f5769b6ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1180dfa991d04f20b8ee864e235a958f.png
[7a88494de09b4984b899da7c4c3c8a81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2045737a751e42f1b021d12c03e80468.png
[5f6ad02223f0421582ddd387e001bd17.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6e4a5c57f71a4141a75d547537be2103.png
[421963cd75334a269b93c05e046e5899.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a2abe4480fe5476bbf82208451ed59f9.png
[a97bd4cfbe4f446eb2e77a4d7b8e9e47.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3b2a177f8e554b8e82d279026343a7d2.png