这是PTA平台上的PAT编程练习题。
这道题用Java解会超时,要用C语言解。我把Java代码和C语言代码都放在这里,思路是一样的。
作者 CHEN, Yue
单位 浙江大学
本题要求计算 A/B,其中 A 是不超过 1000 位的正整数,B 是 1 位正整数。你需要输出商数 Q 和余数 R,使得 A=B×Q+R 成立。
输入格式:
输入在一行中依次给出 A 和 B,中间以 1 空格分隔。
输出格式:
在一行中依次输出 Q 和 R,中间以 1 空格分隔。
输入样例:
123456789050987654321 7
输出样例:
176366841501410934
题目中给的被除数很大(不超过1000位),要用字符串或者字符数组来处理。如果用字符串的来处理的话,可能会比较耗时,因此可以采用字符数组。计算的大致思路如下。每次循环就进行一次除法,被除数是两位(这两位都可以是0),除数是一位。(相当于模拟手动除法运算。)每次取出被除数的一位作为被除数的低位,与上一次得到的余数作为被除数的高位(这个数值可能是0,另外第一次的高位是初始化值0),共同组成一个两位数的被除数,进行除法运算。得到的商(一位)就存到数组中中去,余数(一位)就留到下一次循环的时候作为被除数的高位(通过乘以10来移到高位)。最后输出结果的时候要注意,商的最高位可能是0,要单独处理一下。
Java代码在我的电脑上测试正确,在PTA平台上运行超时。大概是因为Java本身速度不够快。
- import java.io.*;
- class Main{
- public static void main(String[] args) throws IOException{
- //接收输入
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //获取字符输入流
- String[] arr = br.readLine().split(" +"); //读取输入
- //声明变量
- String a = arr[0]; //被除数a的String
- int b = Integer.parseInt(arr[1]); //除数b的int
- char[] ch = a.toCharArray(); //将被除数String转为char数组
- int n = a.length(); //被除数a的长度
- char[] res = new char[n]; //最终的商char[]
- String q = ""; //q是商String
- int r = 0; //r是余数
- int t = 0; //部分余数
- int m = 0; //临时变量
- //开始计算
- for(int i=0;i
//遍历被除数的每一位 - t = t * 10 + ( ch[i] - 48 ); //将原有余数移位,再取出被除数的最高位,转为int
- m = t; //暂存被除数
- t = t % b; //获取当前余数
- res[i] = (char)(m / b + 48); //把部分商存起来
- //q = q + (int)(m / b); //把部分商附加到最终结果上
- }
- r = t; //把最后一位余数作为最终的余数
- //输出
- for(int i=0;i
- if(i==0 && res[i]=='0') //如果商的第一位是0,就跳过
- continue;
- System.out.print(res[i]); //输出商的每一位
- }
- System.out.print(" " + r); //再输出余数
- }
- }
- /*测试的值
- String a = "123456789050987654321";
- int b = 7;
- */
C语言代码
C语言代码与上面的Java代码思路一致,只不过C语言代码运行更快一些,在PTA平台上所有测试点都通过。
- #include
- #include
-
- int main(){
- char a[1000], res[1000]; //a是被除数的字符数组,res是商的字符数组
- int b, n = 0, r = 0; //b是除数,n是记录商的字符数组长度,r是余数
- scanf("%s %d", a, &b); //读取输入
- for(int i=0; a[i]!='\0'; i++){ //遍历被除数
- r = r * 10 + (a[i] - '0'); //计算余数
- res[n++] = r / b + '0'; //计算商,把商加入到商的字符数组中
- r %= b; //计算余数
- }
- int i = 0;
- while(res[i]=='0') i++; //去除前导0
- if(i == n) printf("0"); //如果商为0,则输出0和余数
- while(i < n) printf("%c", res[i++]); //输出商的每一位
- printf(" %d", r); //输出余数
- return 0;
- }