C++ 高精度算法
本帖最后由 zltzlt 于 2020-2-10 19:28 编辑高精度算法
高精度数
计算机数据范围的表示有一定限制。如整型 int、无符号整型的表达范围都约为几十亿。
而实数型中，能保存最多位数的双精度型 double 也只能提供 15~16 位的有效数字，只能精确地表达十多位的数。
因此，在计算位数超过十几位的数时，不能采用现有类型，只能自己编程计算。这就是高精度算法。
高精度算法使用计算机对于超大数据的一种模拟加、减、乘、除、乘方、阶乘、开方等运算的算法。
一般来说，对于非常庞大的数字无法在计算机中正常存储。
于是我们将这个数字拆开，拆成一位一位的存储到数组中，用一个数组去表示一个数字，这样这个数字就被称为是高精度数。
高精度数存储
高精度数一般有两种输入方法，分别是：
[*]采用字符串形式输入
[*]直接输入
1. 采用字符串形式输入（常用）
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100; // 最多一百位
int main()
{
int a, i;
string s;
getline(cin, s);
memset(a, 0, sizeof(a)); // 数组清零
a = s.size(); // 位数
for (i = 1; i <= a; i++)
a = s - i] - '0'; // 将字符串转为数字并倒序存储
return 0;
}
2. 直接输入
#include <iostream>
using namespace std;
const int N = 100; // 最多一百位
int main()
{
int a = {}, i = 0, s;
long long key;
cin >> key;
while (key)
{
a[++i] = key % 10;
key = key / 10;
}
a = i;
return 0;
}
高精度数比较
int compare(int a[], int b[])
{
/* 比较 a 和 b 的大小关系，若 a > b 则返回 1，a < b 则返回 -1，a == b 则返回 1 */
int i;
if (a > b)
return 1; // a 的位数大于 b 的位数，则 a 比 b 大
if (b > a)
return -1; // b 的位数大于 a 的位数，则 b 比 a 大
for (i = a; i > 0; i--)
{
cout << a << " " << b << endl;
if (a > b)
return 1;
if (a < b)
return -1;
}
return 0; // 各位都相等则两数相等
}
普通整型数转化为高精度数
int *convert(unsigned long long n)
{
/* 将非负整数转化成高精度数 */
int i, dg, *r = (int *)malloc(digit + 1);
if (n < 10)
dg = 1;
else
{
i = 2;
for (;; i++)
{
if (n < pow(10, i))
{
dg = i;
break;
}
}
}
r = dg;
for (i = 1; i <= dg; i++)
r = n % int(pow(10, i)) / int(pow(10, i - 1));
return r;
}
高精度数加法
int *add(int a[], int b[])
{
/* 计算 a + b 并返回 */
int i = 1, k = a > b ? a : b, *r = (int *)malloc(digit + 1); // k 是 a 和 b 中位数最大的数的位数
for (; i <= k; i++)
{
r = a + (a + b) / 10; // 有进位，先进位
r = (a + b) % 10; // 计算当前位数字
}
if (r > 0)
r = k + 1; // 修正新的数字的位数
else
r = k;
return r;
}
高精度数减法
int *sub(int a[], int b[])
{
/* 计算 a - b 并返回，如果 a < b 或 a == b 则返回 0 */
int flag = compare(a, b), i = a, *r = (int *)malloc(digit + 1); // 调用比较函数比较大小
if (flag != 1)
{
r = 1;
r = 0;
return r;
}
r = a;
for (; i > 0; i--)
r = a;
for (i = 1; i <= a; i++)
{
if (a < b)
{
// 不够减，向上借 1
r--;
r += 10;
}
r = r - b;
}
while (!r])
r--; // 修正 r 的位数
return r;
}
高精度数乘法
int *mul(int a[], int b[])
{
int i, j, *r = (int *)malloc(digit + 1);
memset(r, 0, sizeof(r));
for (i = 1; i <= a; i++)
{
for (j = 1; j <= b; j++)
{
r = r + a * b;
r = r + r / 10;
r = r % 10;
}
}
r = a + b;
if (r] == 0)
r--;
return r;
}
页:
[1]