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

javalearner

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互质）

1. import java.util.Scanner;
   
2.   public class Test45{
   
3.      public static void main(String args[]){
   
4.         int a,b,c;
   
5.             Scanner in = new Scanner(System.in);
   
6.         a=in.nextInt();//分子
   
7.         b=in.nextInt();//分母
   
8.            System.out.printf("%d/%d It can be decomposed to:",a,b);
   
9.        while(true){      
   
10.         
    
11.         if(a==1){
    
12.            System.out.printf("1/%d
13. ",b);
    
14.             break;
    
15.         }else{
    
16.            System.out.printf("1/%d+",(b/a+1));
    
17.         }
    
18.           c=b/a+1;//把b除以a的商的整数部分加1后的值作为埃及分数的某一个分母(c)；
    
19.            a=a*c-b;//将a乘以c减去b作为新的a
    
20.            b=b*c;//将b乘以c作为新的b
    
21.         
    
22.         if(b%a==0){
    
23.              System.out.printf("1/%d",b/a);
    
24.                break;
    
25.         }
    
26.         if(a==1){
    
27.            System.out.printf("1/%d",b);
    
28.            break;
    
29.         }
    
30.       
    
31.        }
    
32.     }
    
33. }
    

复制代码

运行：

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>
这个算法不能保证以最少项表示，也不能保证展开后的单位分数中的最大分母是最小。
  
   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/18/000609078.zip