Go语言视频零基础入门到精通

编程师兄

C语言趣味程序百例精解之java实现（45）埃及分数


嗯，埃及分数是一个有名的数学问题，上面所讲的算法为数学家菲波那契提出的贪心算法。

设某个真分数的分子为a，分母为b；
1：把b除以a的商的整数部分加1后的值作为埃及分数的某一个分母(c)；
2：将a乘以c减去b作为 新的a；
3：将b乘以c作为新的b；
4：如果a大于1且能整除b，则最后一个分母为b/a；
5：如果a＝1，则最后一个分母为b；否则转步骤（1）.

这种方法的数学根据是：



JAVA程序：（以下假设a,b互质）

import java.util.Scanner;
  public class Test45{
     public static void main(String args[]){
        int a,b,c;
        Scanner in = new Scanner(System.in);
        a=in.nextInt();//分子
        b=in.nextInt();//分母
           System.out.printf("%d/%d It can be decomposed to:",a,b);
       while(true){      
        
        if(a==1){
           System.out.printf("1/%d\n",b);
            break;
        }else{
           System.out.printf("1/%d+",(b/a+1));
        }
          c=b/a+1;//把b除以a的商的整数部分加1后的值作为埃及分数的某一个分母(c)；
           a=a*c-b;//将a乘以c减去b作为新的a
           b=b*c;//将b乘以c作为新的b
        
        if(b%a==0){
             System.out.printf("1/%d",b/a);
               break;
        }
        if(a==1){
           System.out.printf("1/%d",b);
           break;
        }
      
       }
    }
}

运行：

C:\java>java Test45
3
7
3/7 It can be decomposed to:1/3+1/11+1/231
C:\java>java Test45
20
33
20/33 It can be decomposed to:1/2+1/10+1/165
C:\java>java Test45
19
99
19/99 It can be decomposed to:1/6+1/40+1/3960
C:\java>java Test45
8
11
8/11 It can be decomposed to:1/2+1/5+1/37+1/4070
C:\java>


这个算法不能保证以最少项表示，也不能保证展开后的单位分数中的最大分母是最小。