(基础算法)高精度加法，高精度减法
高精度加法
- 什么叫做高精度加法呢？包括接下来的高精度减法，高精度乘法与除法都是同一个道理。正常来讲的话加减乘除，四则运算的数字都是整数，也就是需要在int的范围之内，但当这个操作数变得非常"大"的时候（其实就是一个字符串，比方说有一个数是20位，如果用整数视角来看待的话，天方夜谭，没有数据类型能放得下它，所以它此刻是一个字符串了）。高精度运算操作的对象就是这些字符串化的巨大数字
- 对于高精度加法而言，这些操作数实际上是一些字符串，首先是将数字读进来，并且计算一下字符串的长度，字符串的长度实际上就是数字的位数
//输入
scanf("%s %s",num1,num2);
//计算字符串数组的长度
int sz1=strlen(num1);
int sz2=strlen(num2);
//
int s1=sz1-1;
int s2=sz2-1;
- 然后就进行加法的操作，这边需要一个变量t，用来记录一下是否需要进位。
int t=0;
- 然后输入的字符串当中最后一位才是数字的个位数，加法操作需要从个位开始加，所以说对于两个字符串而言，需要从后往前依次遍历。并且需要注意字符与数字之间的转化。
int t=0;
while(s1>=0 && s2>=0)
{
int num=(num1[s1--]-'0')+(num2[s2--]-'0')+t;
if (num>9)
{
t=1;
num%=10;
}
else
{
t=0;
}
ans[k++]=num+'0';
}
- 两个字符串同时从后往前依次遍历，一开始肯定是齐头并向，但到最后肯定会有其中一个字符串先走完。此时就退出上面的while循环，接下来进行判断处理，也就是说哪个字符串还没有走完，就单独去处理这个字符串。在处理的过程当中必须得保留之前的进位，万一之前有进位的话，这边需要继续加上去。
while(s1>=0)
{
int num=(num1[s1--]-'0')+t;
if (num>9)
{
t=1;
num%=10;
}
else
{
t=0;
}
ans[k++]=num+'0';
}
while(s2>=0)
{
int num=(num2[s2--]-'0')+t;
if (num>9)
{
t=1;
num%=10;
}
else
{
t=0;
}
ans[k++]=num+'0';
}
- 当单独处理完之后并没有结束，此刻还需要去特判一下这个进位表示变量t是否等于1，如果说此刻他还等于1，这就说明还要继续去进一位。
if (t==1)
{
ans[k++]='1';
}
- 至此，我们已经把这两个数相加的形成的和的所有位数都已经放到新数组当中。但由于我们是从数组的从前往后放，也就意味着开始是数字的个位数。为了字符串打印出来符合视觉直觉，所以说我们还需要把这个结果数组给他倒置一下。
void reverse(char* arr, int l, int r)
{
while(l<r)
{
char tmp=arr[l];
arr[l]=arr[r];
arr[r]=tmp;
l++;
r--;
}
}
reverse(ans,0,k-1);
经典例题
luck
#include <stdio.h>
#include <string.h>
#define N 100010
char num1[N];
char num2[N];
char ans[N];
int k=0;
//数组反转
void reverse(char* arr, int l, int r)
{
while(l<r)
{
char tmp=arr[l];
arr[l]=arr[r];
arr[r]=tmp;
l++;
r--;
}
}
int main()
{
//输入
scanf("%s %s",num1,num2);
//计算字符串数组的长度
int sz1=strlen(num1);
int sz2=strlen(num2);
//
int s1=sz1-1;
int s2=sz2-1;
//
int t=0;
while(s1>=0 && s2>=0)
{
int num=(num1[s1--]-'0')+(num2[s2--]-'0')+t;
if (num>9)
{
t=1;
num%=10;
}
else
{
t=0;
}
ans[k++]=num+'0';
}
while(s1>=0)
{
int num=(num1[s1--]-'0')+t;
if (num>9)
{
t=1;
num%=10;
}
else
{
t=0;
}
ans[k++]=num+'0';
}
while(s2>=0)
{
int num=(num2[s2--]-'0')+t;
if (num>9)
{
t=1;
num%=10;
}
else
{
t=0;
}
ans[k++]=num+'0';
}
if (t==1)
{
ans[k++]='1';
}
reverse(ans,0,k-1);
printf("%s\n",ans);
return 0;
}
高精度减法
- 高精度减法的话比高精度加法要更加复杂一些，先由于是高精度嘛，所以我们先把字符串给他读进来，并且计算一下两个字符串的大小。
scanf("%s %s",num1,num2);
int sz1=strlen(num1);
int sz2=strlen(num2);
- 然后我们这边需要实现一个两个字符串相减的函数，我们这边的模板是必须是第一个数比第二个数要大，那首先我们得判断一下这两个字符串所代表的整数到底哪个大？先实现一个函数判断大小
int cmp(int sz1, int sz2)
{
if(sz1>sz2)
{
return 1;
}
else if (sz1<sz2)
{
return 2;
}
else
{
for (int i=0;i<sz1;i++)
{
if (num1[i]>num2[i])
{
return 1;
}
else if (num1[i]<num2[i])
{
return 2;
}
}
return 0;
}
}
- 然后当我们判断出来两个数的大小关系之后，然后根据大小关系给他把参数传到实现两个字符串所代表的整数相减的这个函数里面。首先我们得把这个sub函数给他实现出来，具体解法的逻辑的话，需要这么去判断：
- 上面的这张图表示两个数在相减的过程当中每一位的一次变化关系，然后由于我们已经规定这个sub函数必须是第一个数大，第二个数小，然后第一个数去减第二个数。这也就同时意味着当指向第二个数的指针在不断移位的时候移到尽头了，但第一个数他还有余量。所以说在依次相减的过程之后，接下来就是把第一个数余下的部分给他再放到新数组当中。在这个过程当中仍然需要保持之前的借位状态，因为那个t仍然是会产生影响的，总的sub函数实现过程如下：
void sub(char* arr1, int sz1, char* arr2, int sz2)
{
int t=0;
int i=sz1-1;
int j=sz2-1;
while(i>=0 && j>=0)
{
if ((arr1[i]-'0')-(arr2[j]-'0')-t>=0)
{
ans[k++]=(arr1[i]-'0')-(arr2[j]-'0')-t+'0';
t=0;
}
else
{
ans[k++]=(arr1[i]-'0')-(arr2[j]-'0')+10-t+'0';
t=1;
}
i--;
j--;
}
while(i>=0)
{
if ((arr1[i]-'0')-t>=0)
{
ans[k++]=(arr1[i]-'0')-t+'0';
t=0;
}
else
{
ans[k++]=(arr1[i]-'0')-t+10+'0';
t=1;
}
i--;
}
}
- 最后还需要注意一点的是，在两个数相减的过程当中，有可能在最开头高位会出现前导0的情况，这个也需要特别去处理一下。相减的结果的高位也就意味着结果数组的右边（为我把结果的数据往数组里面放的时候，是从左往右放的），所以说只需要对结果数组ans的右边界去进行一些稍微处理就可以，去判断一下，如果说当前元素为字符0的话，就把这个k给他左移一位，并且要把这个字符零改成斜杠0，毕竟从形式语法上来说还是个字符串。
while(k>0 && ans[k-1]=='0')
{
ans[k-1]='\0';
k--;
}
- 然后最后的话，这个结果数组由于数据是从左往右放的，这也就意味着数组的左边是个位，然后是十位这么一直上去，那么在打印字符数组的时候，呈现出来的样子，要求我们必须要把数字的高位放在前面，所以说需要把这个数组给他翻转一下。
void reverse (char* arr, int l ,int r)
{
while(l<r)
{
char tmp=arr[l];
arr[l]=arr[r];
arr[r]=tmp;
l++;
r--;
}
}
reverse(ans,0,k-1);
经典例题
luck
#include <stdio.h>
#include <string.h>
#define N 100010
char num1[N];
char num2[N];
char ans[N];
int k;
void reverse (char* arr, int l ,int r)
{
while(l<r)
{
char tmp=arr[l];
arr[l]=arr[r];
arr[r]=tmp;
l++;
r--;
}
}
//比较两个数哪个数大，第一个大返回1， 第二个大返回2，相等就返回0
int cmp(int sz1, int sz2)
{
if(sz1>sz2)
{
return 1;
}
else if (sz1<sz2)
{
return 2;
}
else
{
for (int i=0;i<sz1;i++)
{
if (num1[i]>num2[i])
{
return 1;
}
else if (num1[i]<num2[i])
{
return 2;
}
}
return 0;
}
}
void sub(char* arr1, int sz1, char* arr2, int sz2)
{
int t=0;
int i=sz1-1;
int j=sz2-1;
while(i>=0 && j>=0)
{
if ((arr1[i]-'0')-(arr2[j]-'0')-t>=0)
{
ans[k++]=(arr1[i]-'0')-(arr2[j]-'0')-t+'0';
t=0;
}
else
{
ans[k++]=(arr1[i]-'0')-(arr2[j]-'0')+10-t+'0';
t=1;
}
i--;
j--;
}
while(i>=0)
{
if ((arr1[i]-'0')-t>=0)
{
ans[k++]=(arr1[i]-'0')-t+'0';
t=0;
}
else
{
ans[k++]=(arr1[i]-'0')-t+10+'0';
t=1;
}
i--;
}
}
int main()
{
scanf("%s %s",num1,num2);
int sz1=strlen(num1);
int sz2=strlen(num2);
if (cmp(sz1,sz2)==1)
{
sub(num1,sz1,num2,sz2);
}
else if (cmp(sz1,sz2)==2)
{
sub(num2,sz2,num1,sz1);
printf("-");
}
else
{
printf("0\n");
return 0;
}
while(k>0 && ans[k-1]=='0')
{
ans[k-1]='\0';
k--;
}
reverse(ans,0,k-1);
printf("%s\n",ans);
return 0;
}