网站首页命名,企业如何进行网站推广,做网站要先买域名吗,山东网站优化推广目录
算法实现基础
高精度加法AB
测试链接
源代码
代码重点
高精度减法A-B
测试链接
源代码
代码重点
高精度乘法A*b和A*B
测试链接
源代码
代码重点
高精度除法A/b和A/B
测试链接
源代码
代码重点
高精度求和差积商余 算法实现基础 本算法调用STL…
目录
算法实现基础
高精度加法AB
测试链接
源代码
代码重点
高精度减法A-B
测试链接
源代码
代码重点
高精度乘法A*b和A*B
测试链接
源代码
代码重点
高精度除法A/b和A/B
测试链接
源代码
代码重点
高精度求和差积商余 算法实现基础 本算法调用STL库函数vector容器来使用
vector库的详细用法可查看单链双链表以及vector 中的部分内容
建议学习过vector的使用方法之后再来看本算法文章
由于Java与Python等语言拥有特性可以不使用高精度算法实现
因此本篇文章主要讲解的是c的高精度算法 高精度加法AB 测试链接
洛谷P1601 AB Problem高精
源代码
c解法
代码重点
1.数字的存储为倒叙存储。就vector容器的特点来说在头部插入元素的难度以及数据处理量要远远大于在尾部插入元素因此对于长整数的存储来说在vector容器当中倒叙存储(注意字符数组与字符数组的转换)对于答案容器中的数字也是倒叙存储。
2.t的功能包括计算当前位数的和和为下一位的和做进位
3.如果t不为0时证明仍有进位若此时答案数组全部已经计算完毕则证明要在最高位加一
4.auto类型的设定可以让系统根据函数的返回值类型自动对C进行类型限制
#include iostream
#include vector
using namespace std;
vectorint add(vectorint A,vectorint B)
{vectorint C;int t 0;if(A.size()B.size())return add(B,A);for(int i 0;i A.size()||i B.size();i ){if(i A.size())t A[i];if(i B.size())t B[i];C.push_back(t%10);t / 10; }if(t)C.push_back(1);return C;
}
int main()
{string a,b;cinab;vectorint A,B;for(int i a.size()-1;i 0;i -- )A.push_back(a[i]-0);for(int i b.size()-1;i 0;i -- )B.push_back(b[i]-0);auto C add(A,B);for(int i C.size()-1;i 0;i -- )coutC[i];return 0;
}
Python解法
aint(input())
bint(input())
ansab
print(ans) 高精度减法A-B 测试链接 洛谷P2142 高精度减法
源代码
c解法
代码重点
1.cmp函数当大整数A和B的长度不相等时比较二者长度即可。当二者长度相同时从最高位依次向下比当有其中一位不相等时返回本位比较值即可。当各位都相等时则返回ture。经过此函数的处理之后若布尔函数返回true则为AB的情况。若布尔函数返回false则为AB的情况
2.sub函数t为借位情况经过cmp函数的调整之后A一定是大于等于B的所以从最低为开始减若此位运算结果小于0则加10再对10取余为本位结果必向高位进行了借位因此在下一位运算时-1。若此位运算结果大于等于0则不进行借位下次运算时t为0。在进行运算之后要进行去掉前导0的运算
3.main函数依旧本着方便运算的原则对于大整数进行倒叙存储根据cmp函数结果进行分流当true时为正倒叙输出C即可。当false时为负首先输出一个负号再倒序输出即可
#include iostream
#include vector
using namespace std;
bool cmp(vectorint A,vectorint B)
{if(A.size() ! B.size())return A.size() B.size();for(int i A.size() - 1;i 0;i -- ){if(A[i] ! B[i])return A[i] B[i];}return true;
}
vectorint sub(vectorint A,vectorint B)
{vectorint C;int t 0;for(int i 0;i A.size();i ){t A[i];if(i B.size())t - B[i];C.push_back((t 10) % 10);if(t 0)t -1;else t 0;}while(C.size() 1 C.back() 0)C.pop_back();return C;
}
int main()
{string a,b;cinab;vectorint A,B;for(int i a.size() - 1;i 0;i -- )A.push_back(a[i] - 0);for(int i b.size() - 1;i 0;i -- )B.push_back(b[i] - 0);if(cmp(A,B)){auto C sub(A,B);for(int i C.size() - 1;i 0;i -- )coutC[i];}else{cout-;auto C sub(B,A);for(int i C.size() - 1;i 0;i -- )coutC[i];}
} Python3
aint(input())
bint(input())
ansa-b
print(ans) 高精度乘法A*b和A*B 测试链接 洛谷P1303 A*B Problem
源代码
c解法b为短数据
代码重点
1.c代码为大整数乘以小整数因此对于洛谷的那道题来说只能通过40%的数据。高精度大乘小的原理在于A从最低为乘b乘到最高位其中的t为进位乘b之后当前位为(t A[i] * b)%10进位为((t A[i] * b)%10)/10
2.其余依旧是大整数通过string和vector进行逆序存储逆序输出
#include iostream
#include vector
using namespace std;
typedef long long ll;
vectorint mul(vectorint A,ll b)
{vectorint C;int t 0;for(int i 0;i A.size() || t;i ){if(i A.size())t A[i] * b;C.push_back(t % 10);t / 10;}return C;
}
int main()
{string a;ll b;cinab;vectorint A;for(int i a.size() - 1;i 0;i -- )A.push_back(a[i] - 0);auto C mul(A,b);for(int i C.size() - 1;i 0;i -- )coutC[i];return 0;
}
Python3B为长数据
A*B太麻烦直接用Python3
aint(input())
bint(input())
ansa*b
print(ans) 高精度除法A/b和A/B 测试链接
洛谷P1480 A/B Problem
源代码 c解法(b为短数据)
代码重点
1.与高精度加法、减法、乘法不同的是高精度除法在div函数之中对于A的遍历顺序为从为到头因存储时为倒叙存储即为从最高位开始计算。所以r作为一个余数来模拟人工算法因一道题当中很可能不仅仅只对于除法进行考察很有可能是四则运算因此为了方便起见C需要反转一下便于后面的输出注意在反转之后要去掉前导零因洛谷上的b为小整数小于10^9因此能够通过所有数据测试点
2.部分题目可能要输出余数因此将输出余数那一行的注释去掉就ok了
#include iostream
#include vector
#include algorithm
using namespace std;
typedef long long ll;
vectorint div(vectorint A,ll b,ll r)
{vectorint C;r 0;for(int i A.size() - 1;i 0;i -- ){r r * 10 A[i];C.push_back(r / b);r r % b; }reverse(C.begin(),C.end());while(C.size() 1 C.back() 0)C.pop_back();return C;
}
int main()
{string a;ll b,r;cin a b;vectorint A;for(int i a.size() - 1;i 0;i -- )A.push_back(a[i] - 0);auto C div(A,b,r);for(int i C.size() - 1;i 0;i -- )coutC[i];//coutendlr;//此处输出的为余数return 0;
}
Python3解法(B为长数据)
aint(input())
bint(input())
ansa//b
print(ans) 高精度求和差积商余 c太太太太太头疼了还是Python3比较暴力省事
aint(input())
bint(input())
print(ab)
print(a-b)
print(a*b)
print(a//b)
print(a%b)
