题解 | #将真分数分解为埃及分数#

使用回溯法的迭代加深搜索即可，注意计算中的数字类型用int型装不下，所以用long型，另外对于可直接约分为1/x的形式的分数，需额外判断处理一下，否则会出现除零异常

/**
 * 埃及分数
 * 迭代加深搜索
 */
public class Main {
    public static int maxn=100;
    public static long[] v=new long[maxn];
    public static long[] ans=new long[maxn];
    public static int maxd=0;
    public static boolean dfs(int d,long from,long aa,long bb){
        if(maxd==d){
            if(bb%aa!=0){
                return false;
            }
            v[d]=bb/aa;
            if(better(d)){
                for(int i=0;i<=d;i++){
                    ans[i]=v[i];
                }
            }
            return true;
        }
        boolean ok=false;
        from=Math.max(from,getFirst(aa,bb));
        for(long i=from;;i++){
            if((maxd+1-d)*bb<=aa*i)break;
            v[d]=i;
            long a=aa*i-bb;
            long b=i*bb;
            long g=gcd(b,a);
            if(dfs(d+1,i+1,a/g,b/g))ok=true;
        }
        return ok;
    }
    public static long gcd(long a,long b){
        return b==0?a:gcd(b,a%b);
    }
    public static long getFirst(long a,long b){
        long c=b;
        while(b<=a*c){
            c--;
        }
        return c+1;
    }
    public static boolean better(int d){
        for(int i=d;i>=0;i--)if(v[i]!=ans[i]){
            return ans[i]==-1 || v[i]<ans[i];
        }
        return false;
    }
    public static void main(String[] args){
        Scanner sa=new Scanner(System.in);
        while(sa.hasNext()){
            String s=sa.nextLine();
            String[] ss=s.split("/");
            long son=Long.valueOf(ss[0]);
            long fa=Long.valueOf(ss[1]);
            if(fa%son==0){
                long g=gcd(fa,son);
                System.out.println("1/"+fa/g);
            }else{
            int ok=0;
            v=new long[maxn];
            ans=new long[maxn];
            for(maxd=1;;maxd++){
                for(int i=0;i<maxn;i++){
                    ans[i]=-1;
                }
                if(dfs(0,getFirst(son,fa),son,fa)){
                    ok=1;break;
                }
            }
            for(int i=0;i<=maxd;i++){
                System.out.print(i==maxd?"1/"+ans[i]:"1/"+ans[i]+"+");
            }
            System.out.println();
        }
        }
    }
}