华为OJ平台——将真分数分解为埃及分数

奇忠诚

　　题目描述：
　　分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为埃及分数。如：8/11 = 1/2+1/5+1/55+1/110。
　　输入：
　　输入一个真分数，String型
　　输出：
　　输出分解后的string
　　思路：
　　参考http://blog.csdn.net/hnust_xiehonghao/article/details/8682673中的贪心算法求解


设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：

步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b - a*q1）

步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r)/b(q1+1）

步骤三：重复步骤2，直到分解完毕

3/7=1/3+2/21=1/3+1/11+1/231

13/23=1/2+3/46=1/2+1/16+1/368

以上其实是数学家斐波那契提出的一种求解埃及分数的贪心算法，准确的算法表述应该是这样的：

设某个真分数的分子为a，分母为b;

把b除以a的商部分加1后的值作为埃及分数的某一个分母c；

将a乘以c再减去b，作为新的a；

将b乘以c，得到新的b；

如果a大于1且能整除b，则最后一个分母为b/a；算法结束；

或者，如果a等于1，则，最后一个分母为b；算法结束；

否则重复上面的步骤。

备注：事实上，后面判断a是否大于1和a是否等于1的两个判断可以合在一起，及判断b%a是否等于0，最后一个分母为b/a，显然是正确的。








1 import java.util.Scanner;
2
3 public class EgyptFraction {
4
5     public static void main(String[] args) {
6         Scanner cin = new Scanner(System.in) ;   
7         String in = cin.nextLine() ;
8         cin.close() ;
9         
10         String [] strs = in.split("/") ;
11         int  numerator = Integer.parseInt(strs[0]) ;
12         int  denominator = Integer.parseInt(strs[1]) ;
13         
14         System.out.println(resolved(numerator,denominator)) ;
15
16     }
17
18     private static String resolved(int numerator, int denominator) {
19         int a = numerator ;
20         int b = denominator ;
21         
22         int q = b/a ;
23         int r = b%a ;
24         StringBuffer res = new StringBuffer() ;
25         while(a != 1){
26             if(r == 0){
27                 a = 1 ;
28                 b = q ;               
29                 continue ;
30             }else{                                
31                 res.append(1);
32                 res.append('/');
33                 res.append(q + 1);
34                 res.append('+');
35                 
36                 a = a - r ;
37                 b = b*(q+1) ;
38                 q = b/a ;
39                 r = b%a ;
40             }
41         }   
42         
43         if(res.length() != 0){
44             res.append(1) ;
45             res.append('/') ;
46             res.append(q) ;
47         }else{
48             res.append(1) ;
49             res.append('/') ;
50             res.append(q) ;
51         }
52     
53         return res.toString() ;
54            
55     }
56
57 }
Code