AcWing算法学习第三节---高精度问题.

系列文章目录

第一节快速排序
第二节二分法

---

学习路上的风景，我陪你一起去看，编程路上的算法，我陪你一起去学，朋友们你们好，我是夏目浅石，蟹蟹你点开文章和我一同进步，加油！遇见更好的自己。

---

前言

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

---

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

一、高精度加法

知识点如下：

这是我在AcWing打卡界面总结的一些我自己的想法和思路，希望大家可以看完，接下来就是题目的讲解和代码；

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

题目如下：

代码如下（示例）：

#include
#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二、高精度减法

知识点如下：

之前看过许多博客关于这些高精度的，但是都是模棱两可，不是太理解，今天学了一下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.
然后就是扫除前导零输出就可以了.

题目如下：

代码如下（示例）：

#include
#include
//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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

三、高精度乘法

知识点如下：

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

题目如下：

代码如下（示例）：

#include
#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

---

四、高精度除法

知识点如下：

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

题目如下：

代码如下（示例）：

#include
#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

总结

自己的感想：
这里为了大家方便大家复习我会给出我的acwing的地址想去看的话就去看看，当然也可以去acwng报名自己学然后再看我的博客这样会效果更好，不理解的咱们一起讨论学习，我觉得会很不错hhh~
知识点图片汇总
思维导图

记住这里面我是没有把核心算法家里面的，因为这只是一个宏观的导图，最重要的还是把我在acwing上的知识总结好好理解消化一下，这样才能获得收获hhh~咱们下一期见吧！

下期预告

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