高精度计算
chao_smile 2024/3/30
# 高精度计算
利用计算机进行数值计算，有时会遇到这样的问题：有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计算精度也算较高了，但因受到硬件的限制，往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。介绍常用的几种高精度计算的方法。
高精度计算中需要处理好以下几个问题：
# 1. 数据的接收方法和存储方法
数据的接收和存储：当输入的数很长时，可采用字符串方式输入，这样可输入位数很长的数，利用字符串函数和操作运算，将每一位数取出，存入数组中。
void init(int a[]) {
// 传入一个数组
string s;
cin >> s; // 读入字符串s
a[0] = s.length(); // 用a[0]计算字符申s的位数
for(int i = 1; i <= a[0]; i++) {
a[i] = s[a[0] - i] - '0'; // 将数串s转换为数组a，并倒序存储
}
}
- 示例
#include <iostream>
#include <string>
using namespace std;
// 初始化函数，将输入的长整数转换为数组表示
void init(int a[]) {
// 传入一个数组
string s;
cin >> s; // 读入字符串s
a[0] = s.length(); // 用a[0]记录字符串s的位数
for(int i = 1; i <= a[0]; i++) {
a[i] = s[a[0] - i] - '0'; // 将数串s转换为数组a，并倒序存储
}
}
int main() {
int array[1000]; // 假设数组大小为1000
init(array); // 调用初始化函数
cout << "Stored array size: " << array[0] << endl; // 输出存储的数组大小
cout << "Stored array content: ";
for (int i = 1; i <= array[0]; ++i) {
cout << array[i]; // 输出存储的数组内容
}
cout << endl;
return 0;
}
另一种方法是直接用循环加数组方法输入数据。
# 2. 高精度数位数的确定
位数的确定：接收时往往是用字符串的，所以它的位数就等于字符串的长度。
- 示例
#include <iostream>
#include <string>
using namespace std;
// 初始化函数，将输入的长整数转换为数组表示
void init(int a[]) {
// 传入一个数组
string s;
cin >> s; // 读入字符串s
a[0] = s.length(); // 用a[0]记录字符串s的位数
for(int i = 1; i <= a[0]; i++) {
a[i] = s[a[0] - i] - '0'; // 将数串s转换为数组a，并倒序存储
}
}
int main() {
int array[1000]; // 假设数组大小为1000
cout << "Enter a long integer: ";
init(array); // 初始化长整数数组
// 输出长整数的位数
cout << "Number of digits: " << array[0] << endl;
return 0;
}
# 3. 进位，借位处理
- 加法进位:
c[i] = a[i] + b[i];
if(c[i] >= 10) {
c[i] %= 10;
c[i + 1]++;
}
- 减法借位:
if(a[i] < b[i]) {
a[i + 1]--;
a[i] += 10;
}
c[i] = a[i] - b[i];
- 乘法进位：
c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
x = c[i + j - 1] / 10;
c[i + j - 1] %= 10;
相关示例
- C++ 数组实现：
- 这段代码使用数组来表示大整数。
- 输入被读入为字符串然后转换为整数数组。
- 通过数组操作实现了算术运算。
- 手动管理数组的内存。
#include <iostream>
#include <string>
#include <cstring> // 包含memset函数头文件
using namespace std;
// 初始化函数，将输入的长整数转换为数组表示
void init(int a[]) {
// 传入一个数组
string s;
cin >> s; // 读入字符串s
a[0] = s.length(); // 用a[0]记录字符串s的位数
for(int i = 1; i <= a[0]; i++) {
a[i] = s[a[0] - i] - '0'; // 将数串s转换为数组a，并倒序存储
}
}
// 加法函数，将两个长整数数组相加
void add(int a[], int b[], int c[]) {
int len = max(a[0], b[0]); // 取两个数中位数较大的一个作为结果数组的长度
for (int i = 1; i <= len; ++i) {
c[i] = a[i] + b[i]; // 相同位上的数字相加
if (c[i] >= 10) { // 判断是否需要进位
c[i] %= 10; // 取个位数
c[i + 1]++; // 进位
}
}
if (c[len + 1] > 0) // 若最高位仍然有进位，则增加结果数组长度
++len;
c[0] = len; // 存储结果数组的长度
}
// 减法函数，计算长整数数组a减去b的结果，并存储到数组c中
void subtract(int a[], int b[], int c[]) {
int len = max(a[0], b[0]); // 取两个数中位数较大的一个作为结果数组的长度
for (int i = 1; i <= len; ++i) {
if (a[i] < b[i]) { // 判断是否需要借位
a[i + 1]--; // 借位
a[i] += 10; // 借位后当前位数加10
}
c[i] = a[i] - b[i]; // 相同位上的数字相减
}
while (len > 1 && c[len] == 0) // 去除结果数组中多余的前导零
--len;
c[0] = len; // 存储结果数组的长度
}
// 乘法函数，将两个长整数数组相乘
void multiply(int a[], int b[], int c[]) {
int len1 = a[0], len2 = b[0]; // 获取两个数组的长度
for (int i = 1; i <= len1; ++i) {
int carry = 0; // 初始化进位
for (int j = 1; j <= len2; ++j) {
int temp = a[i] * b[j] + c[i + j - 1] + carry; // 计算乘积并加上之前的结果和进位
c[i + j - 1] = temp % 10; // 保存当前位的结果
carry = temp / 10; // 更新进位
}
c[i + len2] += carry; // 将最终的进位加到当前位的后一位
}
int resultLen = len1 + len2; // 计算结果数组的长度
while (resultLen > 1 && c[resultLen] == 0) // 去除结果数组中多余的前导零
--resultLen;
c[0] = resultLen; // 存储结果数组的长度
}
int main() {
int array1[1000], array2[1000], result[2000]; // 假设数组大小为1000
cout << "Enter the first number: ";
init(array1); // 初始化第一个长整数数组
cout << "Enter the second number: ";
init(array2); // 初始化第二个长整数数组
// 进行加法操作
add(array1, array2, result);
cout << "Addition result: ";
for (int i = result[0]; i >= 1; --i) {
cout << result[i]; // 输出加法结果
}
cout << endl;
// 进行减法操作
subtract(array1, array2, result);
cout << "Subtraction result: ";
for (int i = result[0]; i >= 1; --i) {
cout << result[i]; // 输出减法结果
}
cout << endl;
// 注意受之前影响 result 是有值的，而我们关于乘法的运算需要涉及 result，所以需初始化
memset(result, 0, sizeof(result)); // 初始化结果数组为 0
// 进行乘法操作
multiply(array1, array2, result);
cout << "Multiplication result: ";
for (int i = result[0]; i >= 1; --i) {
cout << result[i]; // 输出乘法结果
}
cout << endl;
return 0;
}
- C++ 动态内存分配：
- 类似于第一个代码块，但是内存管理是动态的。
init函数根据输入字符串的长度动态分配数组的内存。- 算术函数返回动态分配的数组。
- 在
main结束时使用delete[]释放动态分配的数组内存。
#include <iostream>
#include <string>
using namespace std;
// 初始化函数，将输入的长整数转换为数组表示
int* init() {
string s;
cin >> s; // 读入字符串s
int* a = new int[s.length() + 1]; // 创建数组
a[0] = s.length(); // 用a[0]记录字符串s的位数
for (int i = 1; i <= a[0]; i++) {
a[i] = s[a[0] - i] - '0'; // 将数串s转换为数组a，并倒序存储
}
return a;
}
// 加法函数，将两个长整数数组相加
int* add(int a[], int b[]) {
int len = max(a[0], b[0]); // 取两个数中位数较大的一个作为结果数组的长度
int* c = new int[len + 1]; // 创建结果数组
for (int i = 1; i <= len; ++i) {
c[i] = a[i] + b[i]; // 相同位上的数字相加
if (c[i] >= 10) { // 判断是否需要进位
c[i] %= 10; // 取个位数
c[i + 1]++; // 进位
}
}
if (c[len + 1] > 0) // 若最高位仍然有进位，则增加结果数组长度
++len;
c[0] = len; // 存储结果数组的长度
return c;
}
// 减法函数，计算长整数数组a减去b的结果，并存储到数组c中
int* subtract(int a[], int b[]) {
int len = max(a[0], b[0]); // 取两个数中位数较大的一个作为结果数组的长度
int* c = new int[len + 1]; // 创建结果数组
for (int i = 1; i <= len; ++i) {
if (a[i] < b[i]) { // 判断是否需要借位
a[i + 1]--; // 借位
a[i] += 10; // 借位后当前位数加10
}
c[i] = a[i] - b[i]; // 相同位上的数字相减
}
while (len > 1 && c[len] == 0) // 去除结果数组中多余的前导零
--len;
c[0] = len; // 存储结果数组的长度
return c;
}
// 乘法函数，将两个长整数数组相乘
int* multiply(int a[], int b[]) {
int len1 = a[0], len2 = b[0]; // 获取两个数组的长度
int* c = new int[len1 + len2 + 1]; // 创建结果数组，最大长度为两个数组长度之和
for (int i = 1; i <= len1; ++i) {
int carry = 0; // 初始化进位
for (int j = 1; j <= len2; ++j) {
int temp = a[i] * b[j] + c[i + j - 1] + carry; // 计算乘积并加上之前的结果和进位
c[i + j - 1] = temp % 10; // 保存当前位的结果
carry = temp / 10; // 更新进位
}
c[i + len2] += carry; // 将最终的进位加到当前位的后一位
}
int resultLen = len1 + len2; // 计算结果数组的长度
while (resultLen > 1 && c[resultLen] == 0) // 去除结果数组中多余的前导零
--resultLen;
c[0] = resultLen; // 存储结果数组的长度
return c;
}
int main() {
cout << "Enter the first number: ";
int* array1 = init(); // 初始化第一个长整数数组
cout << "Enter the second number: ";
int* array2 = init(); // 初始化第二个长整数数组
// 进行加法操作
int* additionResult = add(array1, array2);
cout << "Addition result: ";
for (int i = additionResult[0]; i >= 1; --i) {
cout << additionResult[i]; // 输出加法结果
}
cout << endl;
// 进行减法操作
int* subtractionResult = subtract(array1, array2);
cout << "Subtraction result: ";
for (int i = subtractionResult[0]; i >= 1; --i) {
cout << subtractionResult[i]; // 输出减法结果
}
cout << endl;
// 进行乘法操作
int* multiplicationResult = multiply(array1, array2);
cout << "Multiplication result: ";
for (int i = multiplicationResult[0]; i >= 1; --i) {
cout << multiplicationResult[i]; // 输出乘法结果
}
cout << endl;
// 释放动态分配的内存
delete[] array1;
delete[] array2;
delete[] additionResult;
delete[] subtractionResult;
delete[] multiplicationResult;
return 0;
}
- C++ 字符串操作：
- 这段代码使用字符串来表示大整数。
- 输入直接作为字符串读取。
- 通过字符串操作实现了算术运算，仿佛操作的是数字。
- 函数如
add、subtract和multiply直接在字符串上执行相应的算术运算。 - 内存管理是自动的，由字符串类处理。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 实现两个大整数的加法
string add(string num1, string num2) {
int len1 = num1.size();
int len2 = num2.size();
int maxlen = max(len1, len2); // 找到最长的字符串长度
string result(maxlen, '0'); // 初始化结果字符串为最长字符串长度，并填充为 '0'
int carry = 0; // 进位初始化为 0
// 从个位开始逐位相加
for (int i = maxlen - 1; i >= 0; i--) {
int digit1 = (i < len1) ? (num1[i] - '0') : 0; // 如果num1长度不够，用 0 补齐
int digit2 = (i < len2) ? (num2[i] - '0') : 0; // 如果num2长度不够，用 0 补齐
int sum = digit1 + digit2 + carry; // 当前位相加结果加上进位
result[i] = (sum % 10) + '0'; // 取个位数作为当前结果的数字
carry = sum / 10; // 计算进位
}
// 如果最高位有进位，需要在结果前面再加上一位
if (carry > 0) {
result.insert(result.begin(), carry + '0');
}
return result;
}
// 实现两个大整数的减法，假设第一个数大于等于第二个数
string subtract(string num1, string num2) {
int len1 = num1.size();
int len2 = num2.size();
string result(len1, '0'); // 初始化结果字符串为num1的长度，并填充为 '0'
int borrow = 0; // 借位初始化为 0
// 从个位开始逐位相减
for (int i = len1 - 1; i >= 0; i--) {
int digit1 = num1[i] - '0'; // num1当前位的数字
int digit2 = (i >= len1 - len2) ? (num2[i - (len1 - len2)] - '0') : 0; // 如果num2长度不够，用 0 补齐
int diff = digit1 - digit2 - borrow; // 当前位相减结果减去借位
if (diff < 0) { // 需要向前一位借位
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
result[i] = diff + '0'; // 将差值存入结果字符串中
}
// 去除结果中的前导零
result.erase(0, min(result.find_first_not_of('0'), result.size() - 1));
return result;
}
// 实现两个大整数的乘法
string multiply(string num1, string num2) {
int len1 = num1.size();
int len2 = num2.size();
string result(len1 + len2, '0'); // 结果的最大长度为两个乘数的长度之和，初始化为 '0'
for (int i = len1 - 1; i >= 0; i--) {
int carry = 0;
for (int j = len2 - 1; j >= 0; j--) {
int temp = (num1[i] - '0') * (num2[j] - '0') + (result[i + j + 1] - '0') + carry;
carry = temp / 10;
result[i + j + 1] = (temp % 10) + '0';
}
result[i] += carry;
}
// 去除结果中的前导零
result.erase(0, min(result.find_first_not_of('0'), result.size() - 1));
return result;
}
int main() {
string num1, num2;
// 用户输入两个大整数
cout << "请输入第一个数字：";
cin >> num1;
cout << "请输入第二个数字：";
cin >> num2;
// 执行加法
string sum = add(num1, num2);
cout << "加法结果：" << sum << endl;
// 执行减法（假设num1大于等于num2）
string difference = subtract(num1, num2);
cout << "减法结果：" << difference << endl;
// 执行乘法
string product = multiply(num1, num2);
cout << "乘法结果：" << product << endl;
return 0;
}
# 4. 商和余数的求法
商和余数处理：视被除数和除数的位数情况进行处理。
示例相关库函数
# sizeof 函数
所属库：<cstddef> 或者 <stddef.h>
作用：sizeof 函数用于计算数据类型或者变量的字节大小。
函数原型：
size_t sizeof(type);
type：要计算大小的数据类型或者变量。
返回值：返回一个 size_t 类型的值，表示 type 的字节大小。
示例：
size_t size = sizeof(int);
在上面的示例中，size 将会得到 int 类型所占用的字节数大小。
# gets 函数
所属库：<cstdio> 或者 <stdio.h>
作用：gets 函数用于从标准输入流中读取字符串，并将其存储到指定的缓冲区中。
函数原型：
char* gets(char* str);
str：指向存储输入字符串的缓冲区。
返回值：返回读取的字符串的地址，即 str。
示例：
char buffer[50];
gets(buffer);
在上面的示例中，用户输入的字符串将被存储到 buffer 中。
注意
使用 gets() 函数是不安全的，因为它无法防止缓冲区溢出。推荐使用 fgets() 函数代替 gets() 函数，因为 fgets() 允许指定缓冲区大小，从而避免缓冲区溢出的问题。(当前高版本gets()已废弃)
# fgets 函数
所属库：<cstdio> 或者 <stdio.h>
作用：fgets 函数用于从指定的输入流中读取字符串，并将其存储到指定的缓冲区中。
函数原型：
char* fgets(char* str, int num, FILE* stream);
str：指向存储输入字符串的缓冲区。num：要读取的最大字符数（包括空字符），通常为缓冲区的大小。stream：指定的输入流，通常为stdin（标准输入流）或者文件指针。
返回值：若成功，则返回 str；若到达文件末尾或发生错误，则返回 NULL。
示例：
#include <cstdio>
int main() {
char buffer[50];
// 从标准输入流中读取字符串，存储到buffer中，最多读取49个字符（包括空字符）
fgets(buffer, sizeof(buffer), stdin);
return 0;
}
在上面的示例中，用户输入的字符串将被存储到 buffer 中，最多存储49个字符，包括最后的空字符。
# strlen 函数
所属库：<cstring> 或者 <string.h>
作用：strlen 函数用于计算字符串的长度，不包括结尾的空字符 \0。
函数原型：
size_t strlen(const char* str);
str：要计算长度的字符串。
返回值：返回一个 size_t 类型的值，表示 str 的字符数，不包括结尾的空字符 \0。
示例：
char str[] = "Hello, world!";
size_t length = strlen(str);
在上面的示例中，length 将会得到字符串 "Hello, world!" 的字符数。
# memset 函数
所属库：<cstring> 或者 <string.h>
作用：memset 函数用于将指定内存区域的前若干个字节设置为特定的值。
函数原型：
void* memset(void* ptr, int value, size_t num);
ptr：指向要填充的内存区域的指针。value：要设置的值，以int类型表示，但会被转换为unsigned char并填充到内存中。num：要设置为特定值的字节数。
返回值：返回 ptr，即指向内存区域的指针。
示例：
char buffer[50];
memset(buffer, 'A', sizeof(buffer));
在上面的示例中，buffer 中的前 50 个字节将被设置为字符 'A'。
# strcpy函数
所属库：<cstring> 或者 <string.h>
作用：strcpy函数用于将一个字符串复制到另一个字符串中，包括字符串的结尾空字符\0。
函数原型：
char* strcpy(char* destination, const char* source);
destination：目标字符串，即要将源字符串复制到的目标位置。source：源字符串，即要复制的字符串。
返回值：函数返回指向目标字符串的指针，即destination。
示例：假设有两个字符数组source和destination，要将source的内容复制到destination中，可以使用strcpy函数：
char source[] = "Hello, world!";
char destination[20]; // 目标字符串的大小至少要足够大，以容纳源字符串的内容以及结尾空字符
strcpy(destination, source);
在上面的示例中，destination的内容将变为"Hello, world!"。
- 例题： 高精度加法。输入两个正整数,求它们的和。
【算法分析】
输入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在 C++ 语言中任何数据类型都有一定的表示范围。当两个被加数很大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如下图。
856 a3, a2, a1
+ 255 + b3, b2, b1
----- -------------
1111 c4,c3, c2, c1
如果我们用数组 a、b 分别存储加数和被加数，用数组 c 存储结果。则上例有 a[1] = 6, a[2] = 5, a[3] = 8, b[1] = 5, b[2] = 5, b[3] = 2, c[4] = 1, c[3] = 1, c[2] = 1, c[1] = 1，两数相加如上图所示。
因此，算法描述如下：
void add(int a[], int b[]) {
int c[100];
int i = 1, x = 0; // x 是进位
while (i <= a[0] || i <= b[0]) {
c[i] = a[i] + b[i] + x; // 第i位相加并加上次的进位
x = c[i] / 10; // 向高位进位
c[i] %= 10; // 存储第i位的值
i++; // 位置下标变量
}
}
通常，读入的两个整数可用字符串来存储，程序设计如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
char al[100], bl[100];
int a[100] = {0}, b[100] = {0}, c[101] = {0}; // 增加了数组初始化
fgets(al, sizeof(al), stdin); // 使用fgets替代gets，从标准输入中获取一行字符串，存储到字符数组al中
fgets(bl, sizeof(bl), stdin); // 使用fgets替代gets，从标准输入中获取一行字符串，存储到字符数组bl中
int lena = strlen(al) - 1; // 减去换行符
int lenb = strlen(bl) - 1; // 减去换行符
for (int i = 0; i < lena; i++) // 修正索引从0开始
a[lena - i - 1] = al[i] - '0';
for (int i = 0; i < lenb; i++) // 修正索引从0开始
b[lenb - i - 1] = bl[i] - '0';
int lenc = 0; // 初始化结果数组的长度为0
int carry = 0; // 初始化进位为0
while (lenc < lena || lenc < lenb || carry) { // 修改条件，添加进位carry判断
int sum = carry;
if (lenc < lena) sum += a[lenc];
if (lenc < lenb) sum += b[lenc];
c[lenc] = sum % 10;
carry = sum / 10;
lenc++; // 结果数组长度加1
}
for (int i = lenc - 1; i >= 0; i--) // 修正索引从0开始，输出结果
cout << c[i];
cout << endl;
return 0;
}
- 例题： 高精度减法。输入两个正整数，求它们的差。
【算法分析】
类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。高精度减法的参考程序如下：
#include <iostream>
#include <string>
using namespace std;
int main() {
string nl, n2;
cout << "Input minuend: ";
getline(cin, nl); // 获取被减数
cout << "Input subtrahend: ";
getline(cin, n2); // 获取减数
if (nl.length() < n2.length() || (nl.length() == n2.length() && nl < n2)) {
swap(nl, n2);
cout << "-"; // 如果被减数小于减数，则输出负号
}
int carry = 0; // 初始化进位
string result; // 存储结果
for (int i = nl.length() - 1, j = n2.length() - 1; i >= 0 || j >= 0; --i, --j) {
// 从最低位开始逐位相减
int num1 = (i >= 0) ? (nl[i] - '0') : 0; // 被减数当前位的数字
int num2 = (j >= 0) ? (n2[j] - '0') : 0; // 减数当前位的数字
int diff = num1 - num2 - carry; // 计算当前位的差值
if (diff < 0) {
diff += 10; // 如果当前位差值小于0，向高位借位
carry = 1; // 设置进位
} else {
carry = 0; // 没有进位
}
result = char(diff + '0') + result; // 将当前位的差值转换为字符，加入到结果字符串中
}
cout << result << endl; // 输出结果
return 0;
}
- 例题：高精度乘法。输入两个正整数,求它们的积。
【算法分析】
类似于加法，高精度乘法也可以用竖式求解。在进行乘法运算时，每一位的乘积需要进行错位相加，并且同样需要处理进位。
当我们分析乘法运算时，可以观察到一个关系：结果数组中的每一位与输入数组的元素以及上一位的进位相关。具体地，我们可以写出如下关系式：
c[i+j] = c[i+j] + a[i] * b[j] + x
这里，c[i+j] 表示结果数组中的某一位，a[i] * b[j] 表示乘积的一部分，x 表示上一次的进位。这个关系式说明了结果数组中的每一位与当前位置的乘积、上一位的进位以及原来的值有关。
根据这个关系式，我们还可以推导出进位的计算方式：
x = c[i+j-1] / 10
c[i+j-1] %= 10
这里，x 表示当前位置的进位，我们将当前位置的值除以 10 得到进位，然后对当前位置的值取余，确保每一位的值都在 0 到 9 之间。
综上所述，高精度乘法的实现需要考虑每一位的乘积、进位的处理以及结果数组的更新。通过逐位相乘并相加的方式，可以得到正确的结果。
#include <iostream>
#include <cstring>
using namespace std;
int main() {
char al[100], bl[100];
int a[100], b[100], c[200], lena, lenb, lenc, i, j, x;
// 初始化数组
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
// 读取输入字符串
cout << "Enter the first number: ";
cin.getline(al, sizeof(al));
cout << "Enter the second number: ";
cin.getline(bl, sizeof(bl));
// 计算输入字符串的长度
lena = strlen(al);
lenb = strlen(bl);
// 将字符转换为整数存入数组中
for (i = 0; i < lena; i++)
a[lena - i] = al[i] - '0';
for (i = 0; i < lenb; i++)
b[lenb - i] = bl[i] - '0';
// 执行乘法
for (i = 1; i <= lena; i++) {
x = 0;
for (j = 1; j <= lenb; j++) {
c[i + j - 1] += a[i] * b[j] + x;
x = c[i + j - 1] / 10;
c[i + j - 1] %= 10;
}
c[i + lenb] = x;
}
// 计算乘积的长度
lenc = lena + lenb;
while (c[lenc] == 0 && lenc > 1) lenc--;
// 输出乘积
cout << "Product: ";
for (i = lenc; i >= 1; i--)
cout << c[i];
cout << endl;
return 0;
}
- 例题：高精除以低精。输入两个正整数，求它们的商(做整除)
【算法分析】
做除法时，每一次的商的值都在0〜9,每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。 当然，为了程序简洁，可以避免高精度乘法，用0〜9次循环减法取代得到商的值。这里，我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法
按位相除法是一种将高精度数除以单精度数的方法。在这种方法中，我们逐位地计算商的每一位，并利用每次计算得到的余数作为下一轮计算的被除数的一部分。
下面是按位相除法的基本步骤：
- 初始化： 将被除数和除数的首位相除，得到第一位的商和余数。
- 循环： 将余数乘以 10（因为商的每一位都是 0 到 9 之间的数字），然后再与下一位被除数相除，得到下一位的商和余数。重复这个过程直到除数的每一位都被处理完毕。
- 收尾： 最后的余数就是最终的余数，而得到的商就是最终的商。
具体地，按位相除法就是不断将除数乘以 10，然后与被除数相除，得到商和余数，然后将余数作为下一轮计算的被除数的一部分，直到除数的每一位都被处理完毕。
这种方法的优点是简单易懂，不需要实现高精度乘法，但缺点是效率较低，因为每一位都需要进行乘法和除法运算。在实际应用中，如果需要高效的高精度除法运算，可能需要使用其他更复杂的算法。
#include <iostream>
#include <cstring> // 包含C风格字符串处理函数的头文件
using namespace std;
int main() {
char al[100]; // 存储输入的字符串
int a[100], c[100], lena, i, x = 0, lenc, b; // 声明整型数组和变量
memset(a, 0, sizeof(a)); // 初始化数组a
memset(c, 0, sizeof(c)); // 初始化数组c
cin.getline(al, sizeof(al)); // 从标准输入读取一行字符串到数组al，避免使用gets()函数
cin >> b; // 从标准输入读取一个整数b
lena = strlen(al); // 获取字符串al的长度
// 将字符串al中的字符转换为整数存储到数组a中
for (i = 0; i < lena; i++)
a[i + 1] = al[i] - '0';
// 进行长除法，计算商和余数
for (i = 1; i <= lena; i++) {
c[i] = (x * 10 + a[i]) / b; // 计算商
x = (x * 10 + a[i]) % b; // 更新余数
}
lenc = 1;
// 找到第一个非零的商的位置
while (c[lenc] == 0 && lenc <= lena)
lenc++;
// 输出除法的结果
for (i = lenc; i <= lena; i++)
cout << c[i]; // 输出商
cout << endl;
return 0;
}
实质上，在进行两个高精度数的运算时，存储高精度数的数组元素可以不仅仅只保留一位数字，而可以采取保留多位数的方式，比如使用整型或长整型数据等。这样，在进行运算时（特别是乘法运算），可以减少很多操作次数。采用4位保存的除法运算，其他运算也类似。
示例：
123456789 ÷ 45 = 1,234,567,789 ÷ 45
= 274,3484
余数 1,234,567,789 % 45 = 9
以下是一个示例程序，演示如何使用多位数存储的高精度数进行除法运算：
#include <iostream> // 包含输入输出流头文件
#include <vector> // 包含向量容器头文件
using namespace std; // 使用标准命名空间
// 多位数高精度除法函数
vector<int> divide(vector<int>& dividend, int divisor, int& remainder) {
vector<int> result; // 存储商的向量
remainder = 0; // 初始化余数为0
for (int i = 0; i < dividend.size(); ++i) {
int current = remainder * 10 + dividend[i]; // 计算当前位数值
result.push_back(current / divisor); // 计算当前商并存入结果向量
remainder = current % divisor; // 更新余数
}
// 去除结果中前导0
while (!result.empty() && result[0] == 0) {
result.erase(result.begin()); // 删除前导0
}
return result; // 返回商的向量
}
int main() {
// 示例高精度被除数
vector<int> dividend = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 示例除数
int divisor = 45;
int remainder; // 余数变量
vector<int> result = divide(dividend, divisor, remainder); // 调用除法函数
// 输出商
cout << "商：";
for (int i = 0; i < result.size(); ++i) {
cout << result[i]; // 输出商的每一位
}
cout << endl;
// 输出余数
cout << "余数：" << remainder << endl; // 输出余数
return 0; // 返回执行成功
}
这个示例程序中，我们使用了一个 vector<int> 来存储高精度数，其中每个元素代表数的一位。divide 函数实现了多位数高精度除法，将被除数每次乘以10并除以除数得到商和余数，直到被除数的所有位都处理完毕。
在 main 函数中，我们给出了一个示例被除数和除数，并调用 divide 函数进行除法运算，然后输出商和余数。
- 例题： 高精除以高精。求它们的商和余数
【算法分析】
高精除以低精是对被除数的每一位(这里的“一位”包含前面的余数，以下都是如此)都除以除数，而高精除以高精则是用减法模拟除法，对被除数的每一位都减去除数，一直减到 当前位置的数字（包含前面的余数）小于除数（由于每一位的数字小于10,所以对于每一位最多进行10次计算）
#include <iostream> // 包含输入输出流头文件
#include <cstring> // 包含字符串处理函数头文件
#include <cstdio> // 包含输入输出函数头文件
using namespace std; // 使用标准命名空间
int a[101], b[101], c[101], d, i; // 定义数组和变量
void init(int a[]) {
string s; // 定义字符串s
cin >> s; // 从输入流读取字符串s
a[0] = s.length(); // 记录字符串s的长度
for(i = 1; i <= a[0]; i++)
a[i] = s[a[0] - i] - '0'; // 将数串s转换为数组a，并倒序存储
}
void print(int a[]) {
int i;
if (a[0] == 0) {
cout << 0 << endl; // 如果数组长度为0，则输出0
return;
}
for (i = a[0]; i > 0; i--)
cout << a[i]; // 逆序输出数组a
cout << endl;
}
int compare(int a[], int b[]) {
int i;
if (a[0] > b[0]) return 1; // 如果a的长度大于b的长度，返回1
if (a[0] < b[0]) return -1; // 如果a的长度小于b的长度，返回-1
for (i = a[0]; i > 0; i--) {
if (a[i] > b[i]) return 1; // 如果a的当前位大于b的当前位，返回1
if (a[i] < b[i]) return -1; // 如果a的当前位小于b的当前位，返回-1
}
return 0; // 否则返回0
}
void jian(int a[], int b[]) {
int flag;
flag = compare(a, b); // 比较a和b的大小
if (flag == 0) {
a[0] = 0; // 如果a等于b，将a的长度设为0
return;
}
if (flag == 1) {
for (i = 1; i <= a[0]; i++) {
if (a[i] < b[i]) {
a[i + 1]--;
a[i] += 10;
}
a[i] -= b[i];
}
while (a[0] > 0 && a[a[0]] == 0)
a[0]--; // 去除结果中前导0
return;
}
}
void numcpy(int p[], int q[], int det) {
for (int i = 1; i <= p[0]; i++)
q[i + det - 1] = p[i]; // 复制数组p到数组q的指定位置
q[0] = p[0] + det - 1; // 更新数组q的长度
}
void chugao(int a[], int b[], int c[]) {
int i, tmp[101];
c[0] = a[0] - b[0] + 1; // 计算商数组c的长度
for (i = c[0]; i > 0; i--) {
memset(tmp, 0, sizeof(tmp)); // 清空临时数组tmp
numcpy(b, tmp, i); // 复制数组b到tmp的指定位置
while (compare(a, tmp) >= 0) {
c[i]++; // 商数组当前位加1
jian(a, tmp); // 执行减法操作
}
}
while (c[0] > 0 && c[c[0]] == 0)
c[0]--; // 去除商数组中前导0
}
int main() {
memset(a, 0, sizeof(a)); // 初始化数组a
memset(b, 0, sizeof(b)); // 初始化数组b
memset(c, 0, sizeof(c)); // 初始化数组c
init(a); // 初始化数组a
init(b); // 初始化数组b
chugao(a, b, c); // 执行除法操作
print(c); // 输出商数组
print(a); // 输出余数数组
return 0; // 返回执行成功
}
- 例题： 回文数（Noipl999）
【问题描述】 若一个数（首位不为零）从左向右读与从右向左读都是一样的，我们就称其为回文数。例如：给定一个十进制数56，将56加65（即把56从右向左读），得到121是一个回文数。又如，对于十进制数87，
STEP1：87 + 78 = 165
STEP2：165 + 561 = 726
STEP3：726 + 627 = 1353
STEP4：1353 + 3531 = 4884
在这里的一步是指进行了一次n进制的加法，上例最少用了4步得到回文数4884。编写一个程序，给定一个n（2<n<=10或n=16）进制数m，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible”。
【输入样例】
10 87
【算法分析】
n进制运算：
- 当前位规范由%10改为%n
- 进位处理由/10改为/n
- 其他运算规则不变
#include <iostream> // 包含输入输出流头文件
#include <cstring> // 包含字符串处理头文件
using namespace std; // 使用标准命名空间
const int MAX_LENGTH = 101; // 定义最大长度常量
int n, a[MAX_LENGTH], b[MAX_LENGTH], ans, i; // 声明全局变量
// 初始化函数，将输入的字符串转换为数组表示的数字
void init(int a[]) {
string s;
cin >> n >> s; // 输入n和字符串s
memset(a, 0, sizeof(int) * MAX_LENGTH); // 使用sizeof(int) * MAX_LENGTH来获取数组a的大小
a[0] = s.length(); // 数组第一个元素存储长度
for (i = 1; i <= a[0]; i++) {
if (s[a[0] - i] >= '0' && s[a[0] - i] <= '9')
a[i] = s[a[0] - i] - '0'; // 转换数字字符为数字
else
a[i] = s[a[0] - i] - 'A' + 10; // 转换字母字符为数字
}
}
// 检查回文数
bool check(int a[]) {
int len = a[0];
for (i = 1; i <= len / 2; i++) {
if (a[i] != a[len - i + 1])
return false; // 不是回文数，返回false
}
return true; // 是回文数，返回true
}
// 数字相加函数
void jia(int a[]) {
int x = 0;
for (i = 1; i <= a[0]; i++) {
b[i] = a[i] + a[a[0] - i + 1] + x; // 对应位数字相加
x = b[i] / n; // 计算进位
b[i] %= n; // 求余数
}
if (x > 0) {
b[0] = a[0] + 1; // 结果长度+1
b[b[0]] = x; // 最高位赋值
} else {
b[0] = a[0]; // 结果长度不变
}
memcpy(a, b, sizeof(int) * MAX_LENGTH); // 将b的内容复制到a中
}
int main() {
init(a); // 初始化数组a
if (check(a)) {
cout << 0 << endl; // 若为回文数，输出0
return 0;
}
ans = 0; // 初始化ans为0
while (ans <= 30) {
ans++; // ans自增
jia(a); // 调用数字相加函数
if (check(a)) {
cout << ans << endl; // 若为回文数，输出ans
return 0;
}
}
cout << "Impossible" << endl; // 未找到回文数，输出"Impossible"
return 0; // 返回执行成功
}