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

如：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都大。

给出m/n(0<m<n<1000),编程计算最好的表达方式。

//把真分数m/n(m,m互质)k(k>2)个埃及分数,最大的一个埃及分数的分母t必然满足1/t<m/n<k/t

#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;
}

//把m/n分解为k个埃及分数
void EgyptFraction(int m, int n, int k)
{
    int i,t,low,high;

    if (n<=0 || m<=0)  //溢出
        return;
    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
    {
        //第k个埃及分数分母的上下限low,high
        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;
            // m/n-1/t后的剩余部分分解为k-1个埃及分数
            EgyptFraction(m*t-n,n*t,k-1);

        }
    }
}


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

    while (1)
    {
        printf("Please enter a proper fraction m/n (n<1000):");
        scanf("%d/%d",&m,&n);
        if (m==0)  
            break;
        if (m>=n || n>=1000 || 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;
}

[ 本帖最后由 hwdwow 于 2009-9-10 23:32 编辑 ]

难道发在这里不合适？没个评论的。

zhddragon的解释完全正确，我就是这么想的。