埃及分数Problem
在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。

如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。

对于一个分数a/b,表示方法有很多种，但是哪种最好呢？

首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。

如：

19/45=1/3 + 1/12 + 1/180

19/45=1/3 + 1/15 + 1/45

19/45=1/3 + 1/18 + 1/30,

19/45=1/4 + 1/6 + 1/180

19/45=1/5 + 1/6 + 1/18.

最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。

给出a,b(0〈a〈b〈1000),编程计算最好的表达方式。

Input
第一行:N 表示有N组测试数据，每组测试数据为一行包含a,b(0〈a〈b〈1000)。

Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。

Sample Input
1
19 45
Sample Output
5 6 18

这是个竞赛题目

参考了沙发的思路，我感觉有门路了。似乎可以用回溯法，递归实现！当确定要分解出的个数时，每一个埃及分数都是有上下限的。

程序中出现double的肯定是错的，古埃及人还没有实数的概念呢

//终极解决方案，参考了沙发的思路，感谢
#include <stdio.h>

#define N 10
int g_best[N],g_temp[N],g_nParts;
int g_found;

int Gcd(int m, int n)
{
    int t;
    while (m>0)
    {
        t=n%m;
        n=m;
        m=t;
    }
    return n;
}


void EgyptFraction(int m, int n, int k)
{
    int i,t,low,high;

    t=Gcd(m,n);
    m/=t;
    n/=t;

    if (k==1)
    {
        if (m==1)
        {
            g_temp[0]=n;
            if (!g_found || (g_found && n<g_best[0]))
            {
                g_found=1;
                for (i=0; i<g_nParts; i++)
                    g_best[i]=g_temp[i];
            }
        }
    }
    else
    {
        low=n/m+1;
        if (k<g_nParts && g_temp[k]+1>low)
            low=g_temp[k]+1;
        high = (k*n%m==0)? k*n/m-1:k*n/m;
        for (t=low; t<=high; t++)
        {
            g_temp[k-1]=t;
            EgyptFraction(m*t-n,n*t,k-1);
        }
    }
}


int main(void)
{
    int i,m,n;

    while (1)
    {
        printf("Please enter a proper fraction(a/b):");
        scanf("%d/%d",&m,&n);
        if (m==0)  
            break;
        if (m>=n || m<=0 || n<=0)
            continue;

        g_found=0;
        g_nParts=0;
        do
        {
            g_nParts++;
            EgyptFraction(m,n,g_nParts);
        }while (!g_found && g_nParts<N);

        if (g_found)
        {
            for (i=g_nParts-1; i>0; i--)
                printf("1/%d+",g_best[i]);
            printf("1/%d\n",g_best[0]);
        }
        else
            printf("Too complex!\n");


    }

    return 0;
}