跳至正文
View Categories

3 min read

主要内容 #

  1. 商和余数的求法
  2. 高精度 / 高精度

1. 商和余数的求法 #

要分两种情况讨论：

  • 高精度 / 低精度
  • 高精度 / 高精度

2. 高精度 / 高精度 #

也就是说：假设 a 是一个高精度整数，b 也是一个高精度整数。

【算法分析】

  • 方法：使用减法模拟除法

将被除数，不断减去除数，直到余数小于除数。

  • 1. 需要用到高精度减法
  • 2. 需要用到高精度比较大小
  • 3. 需要用到高精度加法

【例程】

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

int zero[] = { 0 };
int one[] = { 1 };
//赋值过程，将数组a[]中的数据赋值给b[],并将a的长度a_len赋值给b_len
void assign(int a[], int a_len, int* b, int& b_len)
{
    for (int i=0; i < a_len; ++i)
        b[i] = a[i];
    b_len = a_len;
}
//高精度加法计算函数
void add(int a[], int a_len, int b[], int b_len, int* result, int& result_len)
{
    int i = 0, x = 0;
    result_len = 0;
    int max_a_b = a_len > b_len ? a_len : b_len;
    while (i< max_a_b)
    {
        int sub_a = i < a_len ? a[i] : 0;
        int sub_b = i < b_len ? b[i] : 0;
        result[i] = sub_a + sub_b + x;
        x = result[i] / 10;
        result[i] %= 10;
        result_len++;
        i++;
    }
    if (x != 0)
    {
        result[i] = x;
        ++result_len;
    }
}
//高精度减法计算函数
void jianfa(int a[], int a_len, int b[], int b_len, int* result, int& result_len)
{
    int i = 0, x = 0;
    result_len = 0;
    int max_a_b = a_len > b_len ? a_len : b_len;
    while (i < max_a_b)
    {
        int sub_a = i < a_len ? a[i] : 0;
        int sub_b = i < b_len ? b[i] : 0;
        // 减法
        if (sub_a < sub_b)
        {
            --a[i + 1];
            sub_a += 10;
        }
        result[i] = sub_a - sub_b;
        result_len++;
        i++;
    }
    if (x != 0)
    {
        result[i] = x;
        ++result_len;
    }

    // 假如结果全都是0，输出一个0
    int sum(0);
    for (int i = 0; i < result_len; ++i)
    {
        sum += result[i];
        if (sum != 0)
            break;
    }

    if (sum == 0)
        result_len = 1;

}

// 如果 a==b 返回 0; 如果 a > b, 返回 1; 如果 a < b, 返回 -1;
int compare_a_b(int a[], int a_len, int b[], int b_len)
{
    if (a_len > b_len)
        return 1;
    else if (a_len < b_len)
        return -1;
    else
    {
        for (int i= a_len-1; i>=0; --i) // 加减的结果，是倒过来的，所以这里的比较也要倒着比较
        {
            if (a[i] > b[i])
                return 1;
            else if (a[i] < b[i])
                return -1;
            else
                continue;
        }
    }

    return 0; // 相等
}

void divide(int a[], int a_len, int b[], int b_len, int* shang, int& shang_len, int* yushu, int& yushu_len)
{
    if (0 == compare_a_b(zero, 1, a, a_len))
    {
        shang_len = 1;
        yushu_len = 1;
        return; // 0是被除数，则商为0
    }

    for (;;)
    {
        jianfa(a, a_len, b, b_len, a, a_len); // 相当于 a -= b;

        add(shang, shang_len, one, 1, shang, shang_len);
        assign(a, a_len, yushu, yushu_len);// 将最终减法剩余的结果，赋值给余数

        if (-1 == compare_a_b(a, a_len, b, b_len))  // 
            break; // 当余数a小于除数b的时候，退出循环。
    }
}

int main()
{
    // 从屏幕获得输入
    string astr, bstr;
    cin >> astr;
    cin >> bstr;
    int lena = astr.size(), lenb = bstr.size();
    int a[100] = { 0 }, b[100] = { 0 };

    for (int i = 0; i< lena; ++i)
        a[lena - i - 1] = astr[i] - '0'; // 将数字倒过来

    for (int i = 0; i< lenb; ++i)
        b[lenb - i - 1] = bstr[i] - '0';

    if (0 == compare_a_b(zero, 1, b, lenb))
        return -1; // 被除数不能是 0


    // 计算除法
    int shang[100] = { 0 }, yushu[100] = { 0 }, shang_len(0), yushu_len(0);
    divide(a, lena, b, lenb, shang, shang_len, yushu, yushu_len); // a 是被除数，是高精度值。b是低精度值，用 int 即可存储


    // 输出
    cout << "商:";
    for (int i=0; i < shang_len; ++i)
        cout << shang[shang_len - i - 1]; // 再将数字倒过来输出
    cout << endl;

    cout << "余数:";
    for (int i = 0; i < yushu_len; ++i)
        cout << yushu[yushu_len - i - 1]; // 再将数字倒过来输出
    cout << endl;
    
    return 0;
}

习题 #

请将上面的例题，独立完成一遍。要求必须掌握。下节课要求每个人都能够独立写出上面的代码。
课后练习

What are your Feelings