信息学奥赛一本通T1308-高精除（C++代码解析和详细题解）

716 阅读 0 评论 0 点赞

代码解析：
1. isSmaller函数用于判断一个字符串是否比另一个字符串更小。它首先比较两个字符串的长度，如果长度不同，则较短的字符串更小。如果长度相同，则从左到右逐个比较字符的大小，直到找到一个不同的字符为止。

3. subtractStrings函数用于实现高精度减法。它接收两个字符串作为参数，先删除它们的前导零，然后根据两个字符串的大小关系来确定被减数和减数。接着，从右到左逐位相减，根据借位的情况计算差值，并将差值添加到结果字符串的开头。最后，删除结果字符串的前导零并返回。

5. divideStrings函数用于实现高精度除法。它接收两个字符串作为参数，首先检查被除数是否小于除数。如果是，直接返回商为0，余数为被除数。否则，通过一个循环，逐步计算出商和余数。在每次循环中，将被除数的一部分与除数相除，得到商和余数，将商添加到结果字符串的末尾，并更新被除数的值。最后，返回商和余数。

7. 在main函数中，从输入中读取两个高精度整数，并调用divideStrings函数来计算商和余数。然后，通过删除商和余数的前导零，并根据是否为空，输出最终的商和余数。

##### AC代码：

```cpp
#include <iostream>
#include <string>

using namespace std;
//判断字符串a是否小于字符串b
bool isSmaller(string a, string b) {
    int lenA = a.length(), lenB = b.length();
    if (lenA < lenB)
        return true;
    if (lenA > lenB)
        return false;
    for (int i = 0; i < lenA; i++) {
        if (a[i] < b[i])
            return true;
        else if (a[i] > b[i])
            return false;
    }
    return false;
}
//高精度减法，计算字符串a减去字符串b的结果
//处理进位和借位
string subtractStrings(string a, string b) {
    string result;
    int borrow = 0;
    //删除前导零
    while (a.length() > 1 && a[0] == '0')
        a.erase(a.begin());
    while (b.length() > 1 && b[0] == '0')
        b.erase(b.begin());
    
    if (isSmaller(a, b))
        swap(a, b);
    
    int lenA = a.length(), lenB = b.length();
    
    while (lenA >= 1 && lenB >= 1) {
        int digitA = a[lenA - 1] - '0';
        int digitB = b[lenB - 1] - '0';
        
        int diff = (digitA - borrow) - digitB;
        
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        
        result = to_string(diff) + result;
        
        lenA--;
        lenB--;
    }
    
    while (lenA >= 1) {
        int digitA = a[lenA - 1] - '0';
        int diff = digitA - borrow;
        
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        
        result = to_string(diff) + result;
        
        lenA--;
    }
    //删除结果中的前导零
    while (result.length() > 1 && result[0] == '0')
        result.erase(result.begin());
    
    return result;
}
//高精度除法，计算字符串num除以字符串den的商和余数
pair<string, string> divideStrings(string num, string den) {
    pair<string, string> quotientAndRemainder;
    quotientAndRemainder.first = "";
    quotientAndRemainder.second = "";
    
    if (isSmaller(num, den)) {
        quotientAndRemainder.first = "0";
        quotientAndRemainder.second = num;
        return quotientAndRemainder;
    }
    
    int lenNum = num.length(), lenDen = den.length();
    
    string temp = num.substr(0, lenDen);
    int idx = lenDen;
    
    while (idx <= lenNum) {
        int count = 0;
        
        while (!isSmaller(temp, den)) {
            temp = subtractStrings(temp, den);
            count++;
        }
        
        quotientAndRemainder.first += to_string(count);
        
        if (idx < lenNum) {
            temp += num[idx];
			//删除临时字符串中的前导零
            while (temp.length() > 1 && temp[0] == '0')
                temp.erase(temp.begin());
        }
        
        idx++;
    }
    
    quotientAndRemainder.second = temp;
    
    return quotientAndRemainder;
}

int main() {
    string num, den;
    cin >> num >> den;
    //计算商和余数
    pair<string, string> result = divideStrings(num, den);
	//删除商和余数中的前导零
    result.first.erase(0, min(result.first.find_first_not_of('0'), result.first.size() - 1));
    result.second.erase(0, min(result.second.find_first_not_of('0'), result.second.size() - 1));

cout << (result.first.empty() ? "0" : result.first) << endl;
    cout  << (result.second.empty() ? "0" : result.second) << endl;
    
    return 0;
}
```

还是有改进的点，还请大家一起讨论讨论

0.0分

0 人评分

本文分类：题解列表
浏览次数：716 次浏览
发布日期：2023-07-21 14:51:59
本文链接：https://blog.dotcpp.com/a/97665

上一篇 > 有规律的数列求和.数组法
下一篇 > 自由下落的距离计算(这题题目会有点让人误解，对理解循环很有帮助)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

信息学奥赛一本通T1308-高精除（C++代码解析和详细题解）

评论列表共有 0 条评论

发表评论取消回复

信息学奥赛一本通T1308-高精除（C++代码解析和详细题解）

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复