在古埃及，人们使用单位分数的和(形如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 编辑 ]

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

照着算法艺术上面的框架写了个很垃圾的IDA*，发现居然跟你的是一样快的= =还要复杂了好多，哎，算法导论上面不是说限制上下界的深搜对于后面几个数据要几分钟才能出解的么？怎么你的也是瞬出？看来你的上下界估计不简单阿不简单~~~能解释一下么？

这个IDA*还有点问题，具体是关于分数上下界的取值，算法艺术上面没有详解，我就直接用估价函数取值了，暂时效果还不错，不过心里没底。

等等，答案有点不对，我调调再说。


[ 本帖最后由 StarWing83 于 2009-9-12 09:51 编辑 ]

跟踪一步步走了一遍你的程序，觉得你的算法很好，直接算最优的，不用几次就能给出结果，这算法主要还是要明白上下限怎么求得的，我只是不明白这点，可以解说一下吗。
·
“把真分数m/n(m,m互质)k(k>2)个埃及分数,最大的一个埃及分数的分母t必然满足1/t<m/n<k/t ”这段可以说的再详细些吗？
·
还有，你的程序运行11/999结果是：1/94 + 1/833 + 1/50
跟这结果：1/216 + 1/296 + 1/333 比，算哪个结果最优？不是分母小的最优吗？
·
最后，结果直接算最优，算不出其它种组合，也显示不出来，不能让人直观上感觉结果就是最优。

奋斗了一上午，终于让IDA*相比迭代加深搜索有了一点微弱的优势= =

#include <stdio.h>
#include <stdlib.h>
#define N 1000000
#define FLOOR(a, b) ((a) / (b) + ((a) % (b) != 0))
#define GET_LOW(a, b) FLOOR(b, a)
#define GET_HIGH(a, b, k) FLOOR((k) * (b), (a))
#define GET_H(c, d, e) FLOOR((c) * (e), (d))
struct
{
    int c, d, e, deep;
} stack[N];
int last, a, b, ans[N], cur[N], clen, limit;
void simply(int *a, int *b)
{
    int c = *a, d = *b;
    while (d != 0)
    {
        int t = d;
        d = c % d;
        c = t;
    }
    *a /= c;
    *b /= c;
}
void push_child(int c, int d, int k, int g)
{
    int i, b, e;
    b = GET_HIGH(c, d, k);
    e = GET_LOW(c, d);
    if (clen != -1 && e <= cur[clen])
        e = cur[clen] + 1;
    for (i = b; i >= e; --i)
    {
        stack[last].c = c * i - d;
        stack[last].d = i * d;
        simply(&stack[last].c, &stack[last].d);
        if (stack[last].c > 0 && stack[last].d > 0
                && stack[last].d < 0xFFFF)
        {
            stack[last].e = i;
            stack[last].deep = g;
            if (last == N)
                exit(2);
            ++last;
        }
    }
}
int idastar(void)
{
    int i;
    simply(&a, &b);
    ans[0] = -1;
    last = 0;
    limit = GET_H(a, b, GET_LOW(a, b)) - 1;
    while (ans[0] == -1 && ++limit < N)
    {
        clen = -1;
        push_child(a, b, limit + 1, 0);
        while (last > 0)
        {
            --last;
            clen = stack[last].deep;
            cur[clen] = stack[last].e;
            if (stack[last].c == 1)
            {
                if (cur[clen] < stack[last].d
                            && (ans[0] == -1 || stack[last].d < ans[clen + 1]))
                {
                    for (i = 0; i <= clen; ++i)
                        ans[i] = cur[i];
                    ans[clen + 1] = stack[last].d;
                }
            }
            else if (limit >= clen
                    + GET_H(stack[last].c, stack[last].d, cur[clen]))
                push_child(stack[last].c,
                        stack[last].d, limit - clen, clen + 1);
        }
    }
    return ans[0] != -1;
}
int main(void)
{
    int i;
    while (scanf("%d%d", &a, &b) != EOF)
    {
        if (!idastar())
            puts("can't find answer");
        else
        {
            for (i = 0; i <= limit; ++i)
                printf("%d%c", ans[i], i == limit ? '\n' : ' ');
        }
    }
    return 0;
}

这次问题少多了。手头有一份完全没问题的IDA*代码，可惜效率比较差，遍历的节点数比IDFS还要多。这一份比IDFS快，但是总有几个小数据有点毛病。目前这个是通过了大部分数据的了（真奇怪为什么判定0就可以忽略掉那些溢出错误，而判定1却没法忽略……）。其实就是某些地方的加一减一的问题，有时间的话推一下上下界公式，这样会比较好一点。

回LS某人的问题，11 999 是返回216 296 333没错，因为是要求分数自大向小排列的，因此333是三个分数在中最小的一个，而他比其他的解（比如你提出的）最小的要大，因此它是最优解。注意这个分数序列是有顺序的。


[ 本帖最后由 StarWing83 于 2009-9-12 16:23 编辑 ]

回去找你的工作吧，

别去写那个没什么意义的code

= =我做什么干你什么事？我是因为这题是算法艺术的例题才写的。

上面的代码还是有问题，直接在1的时候就收割虽然减少了节点数，但是导致WA，等我改改再说。

因为1/t是表示m/n的加式中一个元素，而且式子中的所有元素均为正数且相加，所以1/t<m/n，又因为1/t是式子中最大的数，所以其他（k-1）个元素每一个都必然小于1/t,那么k个元素的和就必然小于k*1/t,所以m/n<k/t.合起来就是1/t<m/n<k/t。

这题有点难,不过搂住出这道题时我我是第一个做出来的,哈哈~~虽然代码很乱,而且有错误,但我稍微改下运行就再没出错过,哈哈~~~~