题目地址: PAT 乙级 1017
题解
粗看是一道大数除法题, 实际上只不过是通过字符数组模拟除法过程, 理解之后还是比较简单的;
具体分析一下本题;
因为题设中的除数 (n) 是一位整数, 因此大幅简化了整个运算过程; 在整个运算中最为重要的就是中间变量(sum), 判断中间变量 sum 是否足够大能被除数 n 整除, 这也是本题的关键所在;
通过是否判断 sum 是否能被整除, 可以分为以下两种情况:
1. sum == 0 && num[i] <n (当前运算位 num[i]小于除数)
2. 其余情况(sum == 0 && num[i]>= n sum != 0 && num[i] <n sum != 0 && num[i]>= n)
第一种情况, sum 当前值不够除被除数, 因此要作为一种情况单独处理;
第二种情况, sum 的值无论怎样都够除除数 n, 因此可以全部作为一类情况处理;(如果 sum 不为 0, 说明是上一次运算没有除尽的部分, 又因为是上一位的剩余, 所以要乘以 10, 那么无论怎样都够除)
之后我们再来分析一下两种不同情况下的处理方式:
1. 因为中间变量不够除, 也就是说, 当前操作位在不是首位的情况下会商 0; 接下来需要改变中间变量 sum 的值, 因此操作位后移一位加到 sum;(特别注意, 因为要后移一位, 所以需要判断边界防止越界操作)
2. 无论上一位是否有剩余, 都把上一位的值乘以 10, 加上当前操作位的值;
代码
- #include <iostream>
- #include <string>
- using namespace std;
- int main() {
- string num;
- int n = 0, sum = 0;
- cin>> num>> n;
- for (int i = 0; i < num.size(); i++) {
- if (sum == 0 && int(num[i]) - 48 < n && i != num.size() - 1) {
- if (i != 0)
- cout << '0';
- sum += (int(num[i]) - 48) * 10;
- i++;
- sum += int(num[i]) - 48;
- }
- else {
- sum *= 10;
- sum += int(num[i]) - 48;
- }
- cout << sum / n;
- sum %= n;
- }
- cout << ' ' << sum << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2851380.html