本文共 972 字，大约阅读时间需要 3 分钟。

贪心入门之——埃及分数问题

问题描述:

古埃及人喜欢用最少的分子为1的真分数来表示一个真分数，比如7/8=1/2+1/3+1/24

那么算法上应该怎么实现呢？

import org.junit.Test;public class Main {
       void  EgyptFraction(int A,int B){
           System.out.print(A+"/"+B+"=");        int E,R;        while(A!=1){
               E = B/A+1;            System.out.print("1/"+E+"+");            A = A*E-B;            B = B*E;            R = Gcd(A,B);            if(R>1){
                   A/=R;                B/=R;            }        }        System.out.println("1/"+B);    }    int Gcd(int A,int B){
           while(B!=0){
               int temp = A;            A=B;            B=temp%B;        }        return  A;    }    @Test    public void Test(){
           EgyptFraction(7,8);    }}

O(B)(按最坏情况看，必须A/B分解为A个1/B)

转载地址：http://qvlzi.baihongyu.com/