ACM ICPC 給循環小數求最簡分數

今天跑去隔壁學校比ICPC的Regional Contest

其中有一題是給循環小數，求它的最簡分數

以數學邏輯的解法來看

就是把該循環小數設為x

看它循環幾位就讓小數點往右偏移幾位(乘10、乘100之類的)

接著把兩式子相減就可以消掉循環的部位算出分數了

例如：

題目範例測資

1.6 1

所以是1.666…;

令x = 1.666…，得10x= 16.666…

接著兩式子相減

9x = 15，得出x = 15/9 = 5/3

 

明明比賽當下只花10分鐘就想出的邏輯

結果在coding上因為3個人share一台電腦思緒一直被打斷

到最後還是沒能debug完提交 T^T

 

補上回家後不甘心重寫一次的code

奇怪，回家寫就超順利，不到20分鐘就寫好…

import java.util.Scanner;

public class ProblemC {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		StringBuilder num = new StringBuilder(scanner.next());
		int repeat = scanner.nextInt();

		StringBuilder num10x = new StringBuilder(num.toString());
		shiftDecimalPoint(num10x, repeat);

		// 尾端去掉重複字節，如果結尾是'.'也去掉
		num.delete(num.length() - repeat, num.length());
		if (num.indexOf(".") == num.length() - 1)
			num.deleteCharAt(num.indexOf("."));

		int denominator = 1;
		for (int i = 0; i < repeat; i++)
			denominator *= 10;
		denominator -= 1;

		while (num.indexOf(".") != -1 || num10x.indexOf(".") != -1) {
			shiftDecimalPoint(num, 1);
			shiftDecimalPoint(num10x, 1);
			denominator *= 10;
		}

		int numerator = Integer.parseInt(num10x.toString()) - Integer.parseInt(num.toString());

		int gcd = findGCD(numerator, denominator);

		System.out.println(numerator / gcd + "/" + denominator / gcd);
	}

	public static void shiftDecimalPoint(StringBuilder num, int offset) {

		if (num.indexOf(".") == -1) {
			for (int i = 0; i < offset; i++)
				num.append("0");
		} else {
			int lengthAfterDecimalPoint = num.length() - num.indexOf(".") - 1;

			if (offset >= lengthAfterDecimalPoint) {
				num.deleteCharAt(num.indexOf("."));
				for (int i = 0; i < (offset - lengthAfterDecimalPoint); i++)
					num.append("0");
			} else {
				num.insert(num.indexOf(".") + offset + 1, '.');
				num.deleteCharAt(num.indexOf("."));
			}
		}
	}

	public static int findGCD(int num1, int num2) {

		while (num1 != num2) {

			if (num1 > num2)
				num1 -= num2;
			else
				num2 -= num1;
		}
		return num1;
	}
}