算法模板 - C++ 高精度运算

时间:2023-12-28 11:37:20

C++算法板子

  • 高精度

高精度推荐用python来写,python有大整数,这里写的是关于C++的高精度运算模板

1、高精 * 低精

#include <iostream>
#include <vector> using namespace std; vector<int> mul ( vector<int> A, int b )
{
vector<int> C; // 结果按位存到 C 中 int t = 0; // 存放进位的数
for ( int i = 0; i < A.size() || t; i++ ) // i 代表 现在在第几位上
{
if ( i < A.size() ) t += A[i] * b; C.push_back ( t % 10 );
t /= 10;
} while ( C.size() > 1 && C.back() == 0 ) C.pop_back(); // 消除最高位上多余的0
return C;
}
int main ( void )
{
// 计算 C = A * b; string a; // eg. input >> "123456" -> a;
int b;
vector<int> A, C; // A 将存储 "654321"; cin >> a >> b; for ( int i = a.size() - 1; i >= 0; i-- ) A.push_back( a[i] - '0' ); C = mul ( A, b ); for ( int i = C.size() - 1; i >= 0; i-- ) cout << C[i]; return 0;
}

while ( C.size() > 1 && C.back() == 0 ) C.pop_back(); // 消除最高位上多余的0 这个是为了防止以下情况出现

算法模板 - C++ 高精度运算

2、高精 + 高精

#include <iostream>
#include <vector>
#include <algorithm> using namespace std; vector<int> add ( vector<int> A, vector<int> B )
{
vector<int> C;
int t = 0; 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 ( void )
{
string a, b;
vector<int> A, B, C; cin >> 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' ); C = add ( A, B ); for ( int i = C.size() - 1; i >= 0; i-- )
printf ( "%d", C[i] ); return 0;
}

3、高精 - 高精

#include <iostream>
#include <vector> using namespace std; bool cmp ( string a, string b )
{
if ( a.size() > b.size() ) return true;
else if ( a.size() < b.size() ) return false;
else if ( a >= b ) return true; // 长度相同时 按字典序大小比较
else return false;
} vector<int> sub ( vector<int> A, vector<int> B )
{
vector<int> C;
int t = 0; for ( int i = 0; i < A.size(); i++ )
{
t = A[i] - t;
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 ( void )
{
string a, b; // 输入 “123456” vector<int> A, B, C; // 转换为“654321”存放到 cin >> a >> b; for ( int i = a.size() - 1; i >= 0; i-- ) A.push_back ( a[i] - '0' ); // 倒序存储 “654321”
for ( int i = b.size() - 1; i >= 0; i-- ) B.push_back ( b[i] - '0' ); if ( cmp ( a, b ) )
{
C = sub ( A, B );
} else {
cout << "-"; // A < B 时,先输出负号
C = sub ( B, A );
} for ( int i = C.size() - 1; i >= 0; i-- ) cout << C[i]; return 0;
}

4、高精 / 低精 ,余 低精

计算非负整数相除,分母不为零

#include <iostream>
#include <vector>
#include <algorithm> using namespace std; vector<int> div ( vector<int> A, int b, int &t ) // 注意 t 为 “引用”
{
vector<int> C;
t = 0;
for ( int i = A.size() - 1; i >= 0; i-- ) // 注意这里是正序修改(在倒序的基础上倒序)
{
t = t * 10 + A[i];
C.push_back ( t / b );
t %= b;
} reverse ( C.begin(), C.end() ); // 倒序修改后导致答案是正序的 将其反转为倒序 while ( C.size() > 1 && C.back() == 0 ) C.pop_back(); // 后面的步骤都一样了
return C;
}
int main ( void )
{
string a; // 需要输入正序 a 然后倒序存入 A
int b;
vector<int> A, C; cin >> a >> b; for ( int i = a.size() - 1; i >= 0; i-- ) A.push_back ( a[i] - '0' ); int t = 0; // t 存放余数;
C = div ( A, b, t ); // 高精 A * 低精 b 余低精 t for ( int i = C.size() - 1; i >= 0; i-- ) cout << C[i]; // 倒序打印输出答案 ( 因是倒序存储 )
cout << endl << t;
}