登录以参加训练计划

高精度算法实现（数组版） - CSP-J 竞赛必备

使用普通数组实现高精度算法，避免vector依赖，适合CSP-J竞赛环境

目录

1. 数组倒装函数
2. 高精度加法
3. 高精度减法
4. 高精度乘法
5. 高精度除法
6. 综合应用

---

1. 数组倒装函数

原理与实现

将字符串表示的数字转换为低位在前的数组存储格式

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_LEN = 1005; // 最大位数

// 字符串转数组（低位在前）
void str2num(char s[], int num[]) {
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        num[i] = s[len-1-i] - '0'; // 倒序存储
    }
}

// 数组转字符串（高位在前）
void num2str(int num[], int len, char s[]) {
    int index = 0;
    for (int i = len-1; i >= 0; i--) {
        s[index++] = num[i] + '0';
    }
    s[index] = '\0'; // 字符串结束符
}

// 打印数组（测试用）
void printNum(int num[], int len, bool reverse = true) {
    if (reverse) {
        for (int i = len-1; i >= 0; i--) {
            cout << num[i];
        }
    } else {
        for (int i = 0; i < len; i++) {
            cout << num[i];
        }
    }
    cout << endl;
}

int main() {
    char numStr[] = "123456789";
    int numArr[MAX_LEN] = {0}; // 初始化为0
    int len = strlen(numStr);
    
    str2num(numStr, numArr);
    
    cout << "原始字符串: " << numStr << endl;
    cout << "数组存储（低位在前）: ";
    printNum(numArr, len, false);
    cout << "正常显示: ";
    printNum(numArr, len);
    
    // 转换回字符串
    char result[MAX_LEN];
    num2str(numArr, len, result);
    cout << "转换回字符串: " << result << endl;
    
    return 0;
}

输出效果

原始字符串: 123456789
数组存储（低位在前）: 987654321
正常显示: 123456789
转换回字符串: 123456789

---

2. 高精度加法

算法原理

1. 低位在前存储
2. 逐位相加
3. 处理进位
4. 计算最终长度

// 高精度加法
int addBigInt(int a[], int b[], int c[], int lenA, int lenB) {
    int lenC = 0;
    int carry = 0;
    
    // 计算公共长度部分
    while (lenC < lenA || lenC < lenB || carry) {
        int sum = carry;
        if (lenC < lenA) sum += a[lenC];
        if (lenC < lenB) sum += b[lenC];
        
        c[lenC] = sum % 10;
        carry = sum / 10;
        lenC++;
    }
    
    return lenC; // 返回结果长度
}

int main() {
    char s1[] = "99999999999999999999";
    char s2[] = "1";
    
    int a[MAX_LEN] = {0}, b[MAX_LEN] = {0}, c[MAX_LEN] = {0};
    int lenA = strlen(s1);
    int lenB = strlen(s2);
    
    str2num(s1, a);
    str2num(s2, b);
    
    int lenC = addBigInt(a, b, c, lenA, lenB);
    
    cout << "加法结果: ";
    printNum(c, lenC);
    // 输出: 100000000000000000000
    
    return 0;
}

---

3. 高精度减法

算法原理

1. 确保被减数 ≥ 减数
2. 逐位相减
3. 处理借位
4. 去除前导零

// 比较两个大数（绝对值）a >= b
bool greaterEqual(int a[], int b[], int lenA, int lenB) {
    if (lenA != lenB) return lenA > lenB;
    for (int i = lenA-1; i >= 0; i--) {
        if (a[i] != b[i]) 
            return a[i] > b[i];
    }
    return true; // 相等
}

// 高精度减法 (a - b)，要求a >= b
int subBigInt(int a[], int b[], int c[], int lenA, int lenB) {
    int borrow = 0;
    int lenC = 0;
    
    for (int i = 0; i < lenA; i++) {
        int digitA = a[i];
        int digitB = (i < lenB) ? b[i] : 0;
        
        int diff = digitA - digitB - borrow;
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        
        c[lenC++] = diff;
    }
    
    // 去除前导零
    while (lenC > 1 && c[lenC-1] == 0) {
        lenC--;
    }
    
    return lenC;
}

int main() {
    char s1[] = "100000000000000000000";
    char s2[] = "99999999999999999999";
    
    int a[MAX_LEN] = {0}, b[MAX_LEN] = {0}, c[MAX_LEN] = {0};
    int lenA = strlen(s1);
    int lenB = strlen(s2);
    
    str2num(s1, a);
    str2num(s2, b);
    
    // 确保 a >= b
    if (!greaterEqual(a, b, lenA, lenB)) {
        cout << "-";
        swap(a, b);
        swap(lenA, lenB);
    }
    
    int lenC = subBigInt(a, b, c, lenA, lenB);
    
    cout << "减法结果: ";
    printNum(c, lenC);
    // 输出: 1
    
    return 0;
}

---

4. 高精度乘法

算法原理

1. 双重循环计算乘积
2. 处理进位
3. 计算最终长度

// 高精度乘法
int mulBigInt(int a[], int b[], int c[], int lenA, int lenB) {
    // 初始化结果为0
    memset(c, 0, sizeof(int) * MAX_LEN);
    
    // 双重循环计算乘积
    for (int i = 0; i < lenA; i++) {
        int carry = 0;
        for (int j = 0; j < lenB; j++) {
            int pos = i + j;
            int product = a[i] * b[j] + carry + c[pos];
            c[pos] = product % 10;
            carry = product / 10;
        }
        
        // 处理剩余进位
        if (carry > 0) {
            c[i + lenB] += carry;
        }
    }
    
    // 计算结果长度
    int lenC = lenA + lenB;
    while (lenC > 1 && c[lenC-1] == 0) {
        lenC--;
    }
    
    return lenC;
}

int main() {
    char s1[] = "123456789123456789";
    char s2[] = "987654321987654321";
    
    int a[MAX_LEN] = {0}, b[MAX_LEN] = {0}, c[MAX_LEN] = {0};
    int lenA = strlen(s1);
    int lenB = strlen(s2);
    
    str2num(s1, a);
    str2num(s2, b);
    
    int lenC = mulBigInt(a, b, c, lenA, lenB);
    
    cout << "乘法结果: ";
    printNum(c, lenC);
    // 输出: 12193263113702179522374638011112635269
    
    return 0;
}

---

5. 高精度除法（除以低精度整数）

算法原理

1. 从高位到低位处理
2. 当前值 = 余数 * 10 + 当前位
3. 计算商位和余数
4. 去除前导零

// 高精度除法（除以低精度整数）
int divBigInt(int a[], int b, int c[], int lenA) {
    long long remainder = 0; // 使用long long防止溢出
    int lenC = 0;
    
    // 从高位到低位处理（注意：a是低位在前）
    for (int i = lenA-1; i >= 0; i--) {
        long long current = remainder * 10 + a[i];
        c[lenC++] = current / b;
        remainder = current % b;
    }
    
    // 反转结果数组（变为低位在前）
    for (int i = 0; i < lenC/2; i++) {
        swap(c[i], c[lenC-1-i]);
    }
    
    // 去除前导零
    while (lenC > 1 && c[lenC-1] == 0) {
        lenC--;
    }
    
    return lenC;
}

int main() {
    char s1[] = "123456789123456789";
    int divisor = 123;
    
    int a[MAX_LEN] = {0}, c[MAX_LEN] = {0};
    int lenA = strlen(s1);
    
    str2num(s1, a);
    
    int lenC = divBigInt(a, divisor, c, lenA);
    
    cout << "除法结果: ";
    printNum(c, lenC);
    // 输出: 1003713732702900
    
    return 0;
}

---

6. 综合应用：阶乘计算

算法实现

使用高精度乘法计算大数阶乘

// 高精度乘低精度（优化版）
void mul(int a[], int &lenA, int b) {
    int carry = 0;
    for (int i = 0; i < lenA || carry; i++) {
        if (i < lenA) carry += a[i] * b;
        a[i] = carry % 10;
        carry /= 10;
        if (i >= lenA) lenA++;
    }
}

// 计算阶乘 n!
void factorial(int n, int result[], int &len) {
    result[0] = 1; // 初始值为1
    len = 1;       // 初始长度
    
    for (int i = 2; i <= n; i++) {
        mul(result, len, i);
    }
}

int main() {
    int n = 100;
    int result[MAX_LEN] = {0};
    int len = 0;
    
    factorial(n, result, len);
    
    cout << n << "! = ";
    printNum(result, len);
    cout << "位数: " << len << endl;
    
    return 0;
}

阶乘结果示例

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
位数: 158

---

总结与要点

数组存储规则

操作	存储方式	处理方向
加减法	低位在前	从低位到高位
乘法		双重循环
除法	高位在前	从高位到低位

关键函数说明

函数名	功能	参数说明
str2num	字符串转数组	(字符串, 数组)
num2str	数组转字符串	(数组, 长度, 字符串)
addBigInt	高精度加法	(a, b, c, lenA, lenB) → lenC
subBigInt	高精度减法
mulBigInt	高精度乘法
divBigInt	高精度除法	(a, b, c, lenA) → lenC
factorial	阶乘计算	(n, result, len)

使用注意事项

1. 数组初始化：使用前用memset或循环初始化为0
2. 长度管理：每个操作返回结果的实际长度
3. 前导零处理：结果数组需要去除前导零
4. 边界检查：确保不超过数组最大长度MAX_LEN
5. 进位/借位：正确处理进位和借位逻辑

性能优化建议

1. 压位存储：使用10000进制代替10进制

   // 示例：10000进制
   #define BASE 10000
   

2. 预处理长度：预先计算可能的最大长度
3. 减少数组操作：避免不必要的数组复制
4. 优化乘法：使用Karatsuba算法等高级方法

"高精度算法是CSP-J竞赛的核心技能，掌握数组实现方式能让你在竞赛中游刃有余！"

综合练习

1. 计算斐波那契数列第100项
2. 实现大整数幂运算（如2^1000）
3. 计算组合数C(100,50)
4. 实现RSA算法中的大数运算
5. 解决CSP-J历年高精度相关真题

斐波那契数列实现示例

void fibonacci(int n, int fib[], int &len) {
    if (n < 1) return;
    
    int a[MAX_LEN] = {1}, b[MAX_LEN] = {1}, c[MAX_LEN] = {0};
    int lenA = 1, lenB = 1;
    
    if (n == 1 || n == 2) {
        memcpy(fib, a, sizeof(a));
        len = 1;
        return;
    }
    
    for (int i = 3; i <= n; i++) {
        len = addBigInt(a, b, c, lenA, lenB);
        memcpy(a, b, sizeof(b));
        memcpy(b, c, sizeof(c));
        lenA = lenB;
        lenB = len;
    }
    
    memcpy(fib, c, sizeof(c));
}

int main() {
    int n = 100;
    int fib[MAX_LEN] = {0};
    int len = 0;
    
    fibonacci(n, fib, len);
    
    cout << "斐波那契数列第" << n << "项: ";
    printNum(fib, len);
    
    return 0;
}