题解 | #将真分数分解为埃及分数#
一种是按照数学方法,辗转推算,知道新的A等于1。
思路:取每个最大埃及分数
B/A 的商:D,余数为:k
B = A*D + K;
B/A = D+K/A < D+1
所以 A/B > 1/(D+1);
那么最大的埃及分数:D = D+1,然后计算下一个埃及分数 A/B - 1/D
下一个 A/B =(AD - B ) /BD --> A =AD - B ,B=BD
若B/A == 0, 可以整除,直接整除可以拿到 1/(B/A),置 A ==1;
循环判断条件 A!=1;
因为计算过大:可以使用 long
B/A 的商:D,余数为:k
B = A*D + K;
B/A = D+K/A < D+1
所以 A/B > 1/(D+1);
那么最大的埃及分数:D = D+1,然后计算下一个埃及分数 A/B - 1/D
下一个 A/B =(AD - B ) /BD --> A =AD - B ,B=BD
若B/A == 0, 可以整除,直接整除可以拿到 1/(B/A),置 A ==1;
循环判断条件 A!=1;
因为计算过大:可以使用 long
还有一种卡bug的方法,直接每个都是1/x的形式,A为多大就有多少个1/x。
import java.util.*; public class Main { public static void main(String[] args) { /** * 思路:取每个最大埃及分数 * B/A 的商:D,余数为:k * B = A*D + K; * B/A = D+K/A < D+1 * 所以 A/B > 1/(D+1); * 那么最大的埃及分数:D = D+1,然后计算下一个埃及分数 A/B - 1/D * 下一个 A/B =(AD - B ) /BD --> A =AD - B ,B=BD * 若B/A == 0, 可以整除,直接整除可以拿到 1/(B/A),置 A ==1; * 循环判断条件 A!=1; * 因为计算过大:可以使用 long */ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String input = sc.nextLine(); long A = Integer.parseInt(input.split("/")[0]); long B = Integer.parseInt(input.split("/")[1]); long D = B / A +1 ; StringBuilder sb = new StringBuilder(); while(A!=1){ sb.append("1/" + D + "+"); A = A * D -B; B = B * D; D= B / A + 1; if(B % A == 0){ sb.append("1/" + B/A); A = 1; } } System.out.println(sb.toString()); } } } // import java.util.Scanner; // public class Main { // public static void main(String[] args) { // Scanner in = new Scanner(System.in); // // 注意 hasNext 和 hasNextLine 的区别 // while (in.hasNext()) { // 注意 while 处理多个 case // String s = in.next(); // String[] split = s.split("/"); // StringBuilder builder = new StringBuilder(); // int n = Integer.parseInt(split[0]); // for (int i = 0; i < n - 1; i++) { // builder.append("1/" + split[1] + "+"); // } // builder.append("1/" + split[1]); // System.out.println(builder); // } // } // }