(期末了,天天都会想创作,但是有点怕费时间,耽误复习,之前想发一个关于C语言程序漏洞的博客,但是写一半操作发现那个漏洞被vs改了,因此没发布,今天就写一下我前几周写过的算法题,高精度加减法吧(用C++写法更方便,若需要C语言写法,可以先理解此文章自行进行更改))
自我介绍:一个脑子不好的大一学生,c语言接触还没到半年,若涉及到效率等问题,各位都可以在评论区提出见解,谢谢啦。
该账号介绍:此帐号会发布游戏(目前还只会简单小游戏),算法,基础知识等内容。
高精度算法:是可以处理较大数据的算法,这里所说的较大数据指的是已经爆了long long范围的,而此算法是模拟正常加减法计算操作的算法。
(题目链接:P1601 A+B Problem(高精) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int main()
{
//因为加法都是从后往前加,但是数据输入时却是从前往后输入,因此先把他当作字符串输入,方便倒置
string str1, str2;
//因为加数a和b最大为10^500,所以数组设置505就足够
//定义三个整形数组a,b,c,两个存加数,一个存答案
int a[505] = { 0 }, b[505] = { 0 }, c[505] = { 0 };
cin >> str1;
cin >> str2;
//字符串逆置
for (int i = 0; i < str1.size(); i++)
{
//注意:在c++里面和C语言不一样,c++里面的size计算不会把'\0'计算进去
// 因此循环条件里面不要像C语言一样减一
a[i] = str1[str1.size() - 1 - i]-'0';
/*要减去‘0’啊!!!!!!!,转化为与对应数字相同的值*/
//这里需要减一,因为数组下标从0开始
}
for (int i = 0; i < str2.size(); i++)
{
b[i] = str2[str2.size() - 1 - i]-'0';
}
//进行加法
//首先要把位数多的先拿出来,作为被加数,方便计算
int len= str2.size() > str1.size() ? str2.size() : str1.size();
for (int i = 0; i < len; i++)
{
c[i] += a[i] + b[i];
if (c[i] >= 10)
{
c[i+1]+= c[i] /10;
//该位的进位
c[i] = c[i] % 10;
//该位的数字
}
}
len++;
//因为两个数加一起可能位数增加
//要最高位为0 并且 位数超过一位才可len--
if (c[len - 1] == 0 && len > 1)
len--;
//要一个一个数字的打印,不然会爆long long,无法通过
for (int i = 0; i < len; i++)
{
printf("%d", c[len - 1 - i]);
}
printf("\n");
return 0;
}
(题目链接:P2142 高精度减法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
与加法相似,但是要多调换字符串这一步骤
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int main()
{
string str1, str2;
cin >> str1;
cin >> str2;
//两个数字最大为10^10086,因此数组设为10088就可(咱图个吉利)
int a[10088] = { 0 }, b[10088] = { 0 }, c[10088] = { 0 };
int flag = 0;
//标记是否进行了调转字符串
//与加法不同的是减法要调转字符串,把位数多的放前面,方便计算
//至于负号,可以先标记,最后再进行处理
if (str2.size() > str1.size()||(str2.size() == str1.size()&&str1<str2))
{
/*!!!!!!!!!!!!!!!!!!!!注意或者后面的情况,若只有或者前面部分的,若是3-4这种情况,则无法算出正确答案*/
//str1<str2:前者的数字小于后面的数,虽然这是字符串,但仍然可以这样比较
flag = 1;
//标记进行了调换
swap(str1, str2);
//调转的函数,具体的大家可以去自行了解
}
for (int i = 0; i < str1.size(); i++)
{
a[i] = str1[str1.size() - 1 - i] - '0';
//减'0'别忘了
}
for (int i = 0; i < str2.size(); i++)
{
b[i] = str2[str2.size() - 1 - i] - '0';
}
//因为一开始就进行了调换最长的数放在str1,所以这里不需要取str1和str2中最长的赋值给len
for (int i = 0; i < str1.size(); i++)
{
c[i] = a[i] - b[i];
if (c[i] < 0)
{
//c[i + 1]--;
///*!!!!!!!!!!!!是a[i+1]--啊 !!!!!!!!!*/
a[i + 1]--;
c[i] = a[i] + 10 - b[i];
//记得给a[i]加10,就是模拟实际的计算
}
}
//因为一开始就进行了调换最长的数放在str1,所以这里不需要取str1和str2中最长的赋值给len,叶不用进行len++
//直接判断是否要进行len--
int len = str1.size();
/*是while!!!!!!!!!!,不是if!!!!!!*/
while(c[len - 1] == 0 && len > 1)
len--;
if (flag == 1)
printf("-");
for (int i = 0; i < len; i++)
{
printf("%d", c[len - 1 - i]);
}
printf("\n");
return 0;
}
不知你掌握的怎么样呢,欢迎大家提问和评论,共同加油哦!