PAT乙级1017 || A除以B（详解，C/C++示例，测试点分析）

Posted on In

A除以B

题目描述

本题要求计算 A/B，其中 A 是不超过 1000 位的正整数，B 是 1 位正整数。你需要输出商数 Q 和余数 R，使得 A=B×Q+R 成立。

输入格式

输入在一行中依次给出 A 和 B，中间以 1 空格分隔。

输出格式

在一行中依次输出 Q 和 R，中间以 1 空格分隔。

输入样例

1
123456789050987654321 7

输出样例

1
17636684150141093474 3

问题解决

解题思想

此题主要需解决一下几个问题：

  • 大数的存储和输入问题。
  • 大数除以一位正整数的具体实施过程
  • 执行除法的过程中特殊情况的处理

由于A 是不超过 1000 位的正整数，因此只能用数组来存储A的每一位数字，因为要将大数的每一位存入数组的每一个元素，因此，我们用字符数组接收输入更方便。当遇到空格时即为大数输入结束。接下来用c来逐步实现大数的除法。c先初始化为0，然后将大数从最高位到最低位逐步赋给c，当c除以b有余数时，余数作为c下一次的十位，大数的下一位作为c下一次的个位，除第一位和最后一位外，其它余数为0且下一位小于除数b时商均需补0（此除法过程就是模拟笔算除法的过程，相应的细节可模拟笔算除法理解）。

除了上面除第一位和最后一位外，其它余数为0且下一位小于除数b时商均需补0这一特殊情况外，还应注意以下两个特殊情况：

  • 测试用例的输入中有大数的最高几位均为0的情况（例如00012345），c被赋值这几位时是不能有输出的，我们用flag来控制即可。
  • 测试用例的输入中有a小于b的情况，此时退出for循环后是没有输出的（此时退出for循环后flag为0），在for循环外需要作额外处理（输出0）。

知识拓展

我们知道在C语言中，所有变量的定义和声明都必须在函数的开头处，而且变量定义和声明的前面不能有任何其它非声明定义的语句。而在C++中，就没有这么严格的规定了，只要在用到变量前对该变量进行定义和声明就可以，定义和声明的位置是比较灵活的（比如下面代码定义变量的位置）。

代码示例（C/C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#define MAXN 1001
using namespace std;
int main()
{
    char a[MAXN];//用字符数组来存输入的大数
    int i = 0;
    //输入大数
    do{
        a[i] = getchar();
        i++;
    }while(a[i-1] != ' ');//遇到空格时大数输入结束,
    int b;                //由于输入之后i自增了1，因此判断时i需减1
    scanf("%d",&b);//输入除数
    int c = 0;//c存当前处理的大数的部分
    int flag = 0;
    for(i = 0; a[i] != ' '; i++){
        c += a[i] - '0';
        if(c >= b){
            printf("%d",c / b);
            c %= b;
            flag = 1;
        }
        if(c == 0&&a[i+1] != ' '&&(a[i+1] - '0') < b&&flag){
            printf("0");//除第一位和最后一位外，其它余数为0
        }               //且下一位小于除数b时均需补0
        c *= 10;
    }
    if(!flag){//如果大数小于b即flag为0也就是上面的for循环没有输出，则在此处输出0
        printf("0");
    }
    int q;
    q = c / 10;//循环退出时，余数多乘了10
    printf(" %d\n",q);
    return 0;
}

题目来源：PAT乙级1017
作者：CHEN, Yue
单位：浙江大学

稀罕作者