C++少儿编程（16）高精度算法（加减法）_100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

当前位置：首页 > 教程 > C/C++

一高精度计算概述

1、什么是高精度计算：
C++中，int类型的有效范围：-2^31 ~ 2^31-1（约±21亿），最多10位；long long类型的有效范围：-2^63 ~ 2^63-1（约±922亿亿），最多19位。
处理超出基本数据类型范围的大整数的运算，称作“高精度计算”。
高精度计算常见于处理几十位甚至几百位数字的场景。

2、高精度计算的实现方式：

使用数组或字符串存储大整数，模拟手工竖式计算过程，按位进行计算并处理进位。

二高精度加法计算

【描述】输入两个数位不超过100的正整数a、b，计算并输出它俩的和。

【输入】输入两行，第一行输入a，第二行输入b。

【输出】输出一行，a+b的和。

（在计算高精度加法之前，先回忆一下竖式加法的计算过程，此处略过）

【高精度加法 - 计算过程】

1、准备工作：

使用字符串类型变量存储a、b两个加数，使用整型数组A、B、C，分别存储加数a、加数b与a+b之和的数位。

2、预处理：

将a、b的字符串长度分别存入数组A、B的0号元素里，然后分离出字符串中的每个数字，并分别倒序存入A、B数组中。

3、模拟竖式计算：

依次取出A、B的相同数位进行加法计算，还要加上前一位的进位数，将三数之和的个位数字存入数组C的相应数位中，十位数字作为下一位计算的进位数。

4、输出结果：

倒序输出数组C的每个数位。

以上就是高精度加法的具体计算步骤。

【高精度加法 - 示例程序】

# include <bits/stdc++.h>

using namespace std;

// 使用字符串存储大整数a、b

string a, b;

// 使用一维数组模拟竖式计算，注意数组长度要+2（可能有进位）

int A[102], B[102], C[102];

// 预处理：记录数位、分离数字、倒序存储

void fen_li(string s, int a[]) {

    // 将字符串长度存入数组的0号元素里

    a[0] = s.size();

    // 倒序遍历字符串，分离出数字，正序存入数组中

    for (int i = 1; i <= a[0]; i++) a[i] = s[a[0]-i] - '0';

    return;

}

//声明加法运算函数（执行具体的竖式运算）

void big_plus() {

    // C[0]存储加数的最高数位

    C[0] = max(A[0], B[0]);

    // 声明变量j存储进位数字，默认为0

    int j = 0;

    // 遍历加数的每个数位，逐位相加

    for (int i = 1; i <= C[0]; i++) {

        // 计算当前数位两个加数与进位之和

        C[i] = A[i] + B[i] + j;

        // 先计算新的进位

        j = C[i] / 10;

        // 再处理结果（和）的当前数位

        C[i] %= 10;

    }

    // 如果最后的进位数字大于0

    if (j > 0) {

        // 结果的数位加1

        C[0]++;

        // 结果的最高数位设为进位数字

        C[C[0]] = j;

    }

    return;

}

int main() {

    cin >> a >> b;

    // 预处理：记录数位、分离数字、倒序存储

    fen_li(a, A);

    fen_li(b, B);

    // 模拟竖式计算

    big_plus();

    // 输出结果：倒序输出数组C中的元素

    for (int i = C[0]; i > 0; i--) cout << C[i];

    cout << endl;

    return 0;

}

二

高精度加法计算

【描述】输入两个数位不超过100的正整数a、b，计算并输出它俩的和。

【输入】输入两行，第一行输入a，第二行输入b。

【输出】输出一行，a+b的和。

（在计算高精度加法之前，先回忆一下竖式加法的计算过程，此处略过）

【高精度加法 - 计算过程】

1、准备工作：

使用字符串类型变量存储a、b两个加数，使用整型数组A、B、C，分别存储加数a、加数b与a+b之和的数位。

2、预处理：

将a、b的字符串长度分别存入数组A、B的0号元素里，然后分离出字符串中的每个数字，并分别倒序存入A、B数组中。

3、模拟竖式计算：

4、输出结果：

倒序输出数组C的每个数位。

以上就是高精度加法的具体计算步骤。

【高精度加法 - 示例程序】

# include <bits/stdc++.h>

using namespace std;

// 使用字符串存储大整数a、b

string a, b;

// 使用一维数组模拟竖式计算，注意数组长度要+2（可能有进位）

int A[102], B[102], C[102];

// 预处理：记录数位、分离数字、倒序存储

void fen_li(string s, int a[]) {

    // 将字符串长度存入数组的0号元素里

    a[0] = s.size();

    // 倒序遍历字符串，分离出数字，正序存入数组中

    for (int i = 1; i <= a[0]; i++) a[i] = s[a[0]-i] - '0';

    return;

}

//声明加法运算函数（执行具体的竖式运算）

void big_plus() {

    // C[0]存储加数的最高数位

    C[0] = max(A[0], B[0]);

    // 声明变量j存储进位数字，默认为0

    int j = 0;

    // 遍历加数的每个数位，逐位相加

    for (int i = 1; i <= C[0]; i++) {

        // 计算当前数位两个加数与进位之和

        C[i] = A[i] + B[i] + j;

        // 先计算新的进位

        j = C[i] / 10;

        // 再处理结果（和）的当前数位

        C[i] %= 10;

    }

    // 如果最后的进位数字大于0

    if (j > 0) {

        // 结果的数位加1

        C[0]++;

        // 结果的最高数位设为进位数字

        C[C[0]] = j;

    }

    return;

}

int main() {

    cin >> a >> b;

    // 预处理：记录数位、分离数字、倒序存储

    fen_li(a, A);

    fen_li(b, B);

    // 模拟竖式计算

    big_plus();

    // 输出结果：倒序输出数组C中的元素

    for (int i = C[0]; i > 0; i--) cout << C[i];

    cout << endl;

    return 0;

}

三

高精度减法计算

【描述】输入两个数位不超过100的正整数a、b，计算并输出它俩的差。

【输入】输入两行，第一行输入a，第二行输入b。

【输出】输出一行，a-b的查。

（在计算高精度减法之前，先回忆一下竖式减法的计算过程，此处略过）

【高精度减法- 计算过程】

1、准备工作：

使用字符串类型变量存储a、b两个加数，使用整型数组A、B、C，分别存储被减数a、减数b与a-b之差的数位。

2、判断大小：

在计算之前，先判断一下a、b的大小，如果a<b，计算结果为负数，将a、b两数交换，确保被减数不小于减数。

3、预处理：

将a、b的字符串长度分别存入数组A、B的0号元素里，然后分离出字符串中的每个数字，并分别倒序存入A、B数组中。

4、模拟竖式计算：

依次取出A、B的相同数位进行减法计算，如果不够减，向高位借1；注意，计算结果有可能为0，所以计算完毕之后，要去掉开头的0。

5、输出结果：

（1）如果结果为负数，先输出一个负号；

（2）再倒序输出数组C中的数位。

以上就是高精度减法的具体计算步骤。

【高精度减法 - 示例程序】

# include <bits/stdc++.h>

using namespace std;

// 使用字符串存储大整数a、b

string a, b;

// 使用一维数组模拟竖式计算，注意数组长度要+1

int A[101], B[101], C[101];

// 比较a、b的大小，确定结果的符号

bool a_dayu_b(string a, string b) {

    // 如果a的长度小于b的长度，说明a<b

    if (a.size() < b.size()) return false;

    else if (a.size() == b.size()) {

        // 当a、b的长度相等时，再比较a、b字符串的大小

        if (a < b) return false;

    }

    // 只要不返回false，就返回true

    return true;

}

// 预处理：记录数位、分离数字、倒序存储

void fen_li(string s, int a[]) {

    // 将字符串长度存入数组的0号元素里

    a[0] = s.size();

    // 倒序遍历字符串，分离出数字，正序存入数组中

    for (int i = 1; i <= a[0]; i++) a[i] = s[a[0]-i] - '0';

    return;

}

// 声明减法运算函数（执行具体的竖式运算）

void big_minus() {

    // C[0]默认为被减数A的数位

    C[0] = A[0];

    // 遍历被减数的每个数位，逐位相减

    for (int i = 1; i <= C[0]; i++) {

        // 如果不够减，向高位借1，当前数位加10

        if (A[i] < B[i]) {

            A[i+1]--;

            A[i] += 10;

        }

        // 当前数位相减

        C[i] = A[i] - B[i];

    }

    // 去除开头的0

    while (C[C[0]] == 0 && C[0] > 1) C[0]--;

    return;

}

int main() {

    cin >> a >> b;

    // 比较大小：确定结果符号

    bool flag = a_dayu_b(a, b);

    if (!flag) swap(a, b);

    // 预处理：记录数位、分离数字、倒序存储

    fen_li(a, A);

    fen_li(b, B);

    // 模拟竖式计算

    big_minus();

    // 输出结果：先根据情况输出负号，再倒序输出C中的数位

    if (!flag) cout << "-";

    for (int i = C[0]; i > 0; i--) cout << C[i];

    cout << endl;

    return 0;

}

四课后习题

输出斐波那契数列的第n项。（n<1000）

【参考代码】斐波那契数列（高精度加法）

【方法一】使用字符串型一维数组存储每一项

# include <bits/stdc++.h>

using namespace std;

// 使用字符串型一维数组存储斐波那契数列每一项

string s[1000] = {"0", "1"};

// 使用一维数组模拟竖式计算，注意数组长度要+2（可能有进位）

int A[1002], B[1002], C[1002];

// 预处理：记录数位、分离数字、倒序存储

void fen_li(string s, int a[]) {

    // 将字符串长度存入数组的0号元素里

    a[0] = s.size();

    // 倒序遍历字符串，分离出数字，正序存入数组中

    for (int i = 1; i <= a[0]; i++) a[i] = s[a[0]-i] - '0';

    return;

}

//声明加法运算函数（执行具体的竖式运算）

void big_plus() {

    // C[0]存储加数的最高数位

    C[0] = max(A[0], B[0]);

    // 声明变量j存储进位数字，默认为0

    int j = 0;

    for (int i = 1; i <= C[0]; i++) {

        // 计算当前数位两个加数与进位之和

        C[i] = A[i] + B[i] + j;

        // 先计算新的进位

        j = C[i] / 10;

        // 再处理结果（和）的当前数位

        C[i] %= 10;

    }

    // 如果最后的进位数字大于0

    if (j > 0) {

        // 结果的数位加1

        C[0]++;

        // 结果的最高数位设为进位数字

        C[C[0]] = j;

    }

    return;

}

int main() {

    int n;

    cin >> n;

    // 如果n小于2，直接输出

    if (n < 2) cout << n << endl;

    else {

        // 否则，循环计算每一项，并将结果存入数组中

        for (int i = 2; i <= n; i++) {

            // 预处理：记录数位、分离数字、倒序存储

            fen_li(s[i-2], A);

            fen_li(s[i-1], B);

            // 模拟竖式计算

            big_plus();

            // 将数组C中的元素倒序转成字符串存入s中

            string ss = "";

            for (int j = C[0]; j > 0; j--) {    // 倒序遍历

                char ch = C[j] + '0';   // 将数字转成字符

                ss += ch;       // 将字符合并到字符串中

            }

            s[i] = ss;  // 将合并好的字符串存入字符串数组中

        }

        // 输出结果：直接输出s数组中的最后一个元素即可

        cout << s[n] << endl;

    }

    return 0;

}

【方法二】使用二维整型数组存储每一项

# include <bits/stdc++.h>

using namespace std;

// 使用二维整型数组存储斐波那契数列每一项

// 每一行表示一项斐波那契数（倒序存储的数位）

int a2[1000][1000] = {

    {1, 0},     // 第0号元素

    {1, 1}      // 第1号元素

};

// 只需声明一个一维整型数组C用来存储和

int C[1002];

// A、B两个数组作为参数传入运算函数

void big_plus(int A[], int B[]) {

    // C[0]存储加数的最高数位

    C[0] = max(A[0], B[0]);

    // 声明变量j存储进位数字，默认为0

    int j = 0;

    for (int i = 1; i <= C[0]; i++) {

        // 计算当前数位两个加数与进位之和

        C[i] = A[i] + B[i] + j;

        // 先计算新的进位

        j = C[i] / 10;

        // 再处理结果（和）的当前数位

        C[i] %= 10;

    }

    // 如果最后的进位数字大于0

    if (j > 0) {

        // 结果的数位加1

        C[0]++;

        // 结果的最高数位设为进位数字

        C[C[0]] = j;

    }

    return;

}

int main() {

    int n;

    cin >> n;

    // 如果n大于1

    if (n > 1) {

        // 循环计算（更新）每一项

        for (int i = 2; i <= n; i++) {

            // 模拟竖式计算：将前两项传入计算函数

            big_plus(a2[i-2], a2[i-1]);

            // 更新a2的第i项：将数组C的元素正序存入a2[i]中

            for (int j = 0; j <= C[0]; j++) a2[i][j] = C[j];

        }

    }

    // 输出结果：倒序输出a2[n]的所有数位

    for (int i = a2[n][0]; i > 0; i--) cout << a2[n][i];

    cout << endl;

    return 0;

}

关键词

高精度算法

提示声明

免责声明：本站资源均来自网络或者用户投稿，仅供用于学习和交流：如有侵权联系删除!

C++少儿编程（16）高精度算法（加减法）

关键词

相关教程

提示声明

猜你喜欢

©2016-2021 100150.com

帮助中心

C++少儿编程（16）高精度算法（加减法）

关 键 词

相关教程

提示声明

猜你喜欢

©2016-2021 100150.com

帮助中心

关键词