PAT (Basic Level) Practice 1017 A除以B

PAT (Basic Level) Practice 1017 A除以B

cx天王盖地虎

• PAT (Basic Level) Practice 1017 A除以B
• • 1.题目描述
  • 2.思路及代码
  • • 注意事项
    • ① 模拟除法过程
    • ②与库函数比较

PAT (Basic Level) Practice 1017 A除以B 1.题目描述

2.思路及代码 注意事项

①大数要采用BufferedReader接收 ②频繁的字符串增删要考虑StringBuffer
一开始用scanner接收，全部超时，一个劲的想是不是算法不够高效，但是想半天也不知道怎么优化for循环。去看了下别人做法，发现要采用BufferedReader接收，恍然大悟。
（但是也发现很多人采用BigInteger类直接计算，我：？？？）

① 模拟除法过程

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		
		//采用BufferedReader输入
		BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in)); 
		String strs[] = buffer.readLine().split(" ");
		char a[] = strs[0].toCharArray();
		int b = strs[1].charAt(0) - '0';
		
		
		
		
		//由于除数b只是一位数，因此模拟除法时每次至少取两位然后除以b，取两位最方便
		StringBuffer Q = new StringBuffer("");		//由于需要频繁进行字符串添加 *** 作，采用StringBuffer记录商
		int  pre = 0, twoNumber;					//pre记录上一次运算的余数，初始为0
		for(char c : a) {
			twonumber = pre * 10 + c - '0';			//pre与当前位结合，生成一个两位数
			Q.append(twonumber / b);				//本次运算的商添加到Q尾部
			pre = twonumber % b;					//记录新的余数
		}
		
		String ret = Q.toString();					
		if(ret.startsWith("0") && ret.length() != 1)//可能会以‘0’开始，去掉‘0’再输出
			System.out.print(ret.substring(1) + " " + pre);
		else										
			System.out.print(Q.toString() + " " + pre);
	}	
	
}

②与库函数比较

我又去试了试库函数，测了测速度

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

	public static void main(String[] args) throws IOException {
		
		//采用BufferedReader输入
		BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in)); 
		String strs[] = buffer.readLine().split(" ");		
		
		
		BigInteger a,b,q,r;
		a = new BigInteger(strs[0]);
		b = new BigInteger(strs[1]);
		q = a.divide(b);
		r = a.mod(b);
		System.out.print(q.toString() + " " + r.toString());
	}	
	
}

发现速度差距不大：