USACO - 2.4.5 - Fractions to Decimals

 

原创文章转载请注明出处

摘要：模拟 ， 数论 ， 两星

一. 题目翻译

1. 描述：

写一个程序，输入一个形如N/D的分数(N是分子，D是分母)，输出它的小数形式。 如果小数有循环节的话，把循环节放在一对圆括号中。

例如, 1/3 =0.33333333　写成0.(3), 41/333 = 0.123123123...　写成0.(123), 用xxx.0 等表示整数。 典型的转化例子：

1/3 = 0.(3) 22/5 = 4.4 1/7 = 0.(142857) 2/2 = 1.0 3/8 = 0.375 45/56 = 0.803(571428)

2. 格式：

          INPUT FORMAT:

          单独的一行包括被空格分开的N和D(1 <= N,D <= 100000)。

          OUTPUT FORMAT:

          按照上面规则计算出的小数表达式.如果结果长度大于76,每行输出76个字符。

3. SAMPLE：

          SAMPLE INPUT:

45 56

          SAMPLE OUTPUT:

0.803(571428)

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

           题目的意思是寻找小数部分重复的值，直接进行浮点预算然后找重复是无法解决问题的。其实这个问题等价于寻找曾经出现过的余数，出现了相同的余数，小数部分才会出现重复。（例如：1/3，第一次除的余数是1，第二次也是1所以出现了余数重复，那么小数部分必然也是重复的。1/3=0.(3)）

 

2. 具体实现（具体实现过程中出现的问题）：

          我们使用一个HashMap hm来记录已经出现过的余数。详细请参考代码注释，输出部分我写的比较复杂， 大家简单参考一下吧。

3. 启示:

          很有意思的题目，注意积累。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:fracdec
*/
package session_2_4_5;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class fracdec {

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
//		Scanner in = new Scanner(new BufferedReader(new FileReader(
//		"fracdec.in")));
//		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
//		"fracdec.out")));
		
		int beichushu = in.nextInt();
		int chushu = in.nextInt();
		ArrayList<Integer> al = new ArrayList<Integer>();
		HashMap<Integer, Integer> hm= new HashMap<Integer, Integer>();//记录所有出现过的余数
		int now = 1;
		
		al.add(beichushu/chushu);
		beichushu = beichushu%chushu;
		while (beichushu!=0&&!hm.containsKey(beichushu)){//继续长除直到出现重复的余数或者出现整除的情况
			hm.put(beichushu, now++);
			al.add(10*beichushu/chushu);
			beichushu = 10*beichushu%chushu;
		}
		
		//输出，写得不太好，大家简单参考一下吧。算法主体还是在上面
		if (beichushu == 0){ //整除的情况
			StringBuilder sb = new StringBuilder();
			sb.append(al.get(0));
			if (al.size()>1){ //结果是小数
				sb.append(".");
				for (int i=1;i<al.size();i++){
					sb.append(al.get(i));
				}
			}else{//结果是整数
				sb.append(".0");
			}
			pw.println(sb);
		}else{  //有循环节的情况
			if (hm.containsKey(beichushu)){
				StringBuilder sb = new StringBuilder();
				sb.append(al.get(0));
				sb.append(".");
				int sep = hm.get(beichushu);
				for (int i=1;i<sep;i++){
					if(sb.length()==76){
						pw.println(sb);
						sb = new StringBuilder();
					}
					sb.append(al.get(i));
				}
				sb.append("(");
				for (int i=sep;i<al.size();i++){
					if(sb.length()==76){
						pw.println(sb);
						sb = new StringBuilder();
					}
					sb.append(al.get(i));
				}
				if(sb.length()==76){
					pw.println(sb);
					sb = new StringBuilder();
				}
				sb.append(")");
				pw.println(sb);
			}
		}
		pw.close();
	}

}