大数除法

高精度除法的主要步骤：
1、以字符串的形式读入一个高精度数和一个单精度数，分别表示被除数和除数。
2、将高精度数按位拆分，存储在数组中，同时定义一个初始值为0的变量x表示余数。
3、模拟竖式除法，从高位到低位，依次计算计算出商的每一位，并更新x。
4、从高位到低位输出数组的值为商。最后的x值为余数。

123456789/45
1/45=0, 1%45=1
12/45=0, 12%45=12
123/45=2, 123%45=33
334/45=7 , 334%45=19
195/45=4, 195%45=15
156/45=3, 156%45=21
217/45=4 217%45=37
378/45=8 378%45=18
189/45=4 189%45=9
最后结果为2743484 余数为9

/**************************************************************** 
 * Description: 大数除法
 * Author: Alex Li
 * Date: 2024-01-31 05:53:52
 * LastEditTime: 2024-01-31 06:07:30
****************************************************************/
#include <string>
#include <iostream>
using namespace std;

const int MaxLen = 110; // 定义最大长度
string a1; // 用于存储输入的大数
int a[MaxLen], c[MaxLen]; // a用于存储大数的每一位，c用于存储计算的结果

int main() {
    int lena, lenc, x = 0, b; // lena是大数的长度，x用于存储余数，b是除数

    cin >> a1 >> b; // 输入大数和除数
    lena = a1.length(); // 获取大数的长度

    // 将大数的每一位转换成整数并存储在数组a中
    for (int i = 0; i < lena; ++i) {
        a[i] = a1[i] - '0';
    }

    // 进行除法运算
    for (int i = 0; i < lena; ++i) {
        c[i] = (x * 10 + a[i]) / b; // 计算当前位的商
        x = (x * 10 + a[i]) % b; // 更新余数
    }

    // 输出结果
    bool leadingZero = true;
    for (int k = 0; k < lena; ++k) {
        // 跳过结果前导0
        if (c[k] != 0 || !leadingZero) {
            leadingZero = false;
            cout << c[k]; // 输出每位的商
        }
    }

    // 如果结果全为0，则输出0
    if (leadingZero) {
        cout << "0";
    }

    cout << " "; // 输出空格分隔
    cout << x; // 输出余数
    return 0;
}

洛谷P1480

Previous Topic

Back to Lesson

Next Lesson

数据结构与算法

大数除法