论坛 › 算法交流 › 埃及分数问题

mathe 发表于 2008-3-7 13:01:44

记忆中好像有人发过很类似的ACM题目，不过感觉这种题目基本上就是靠搜索(技巧就在于如何更好的缩小搜索范围)
无心人发的这三个题目中应该这个最复杂

liangbch 发表于 2008-3-7 13:43:25

报个到先，准备写个程序。
如果想搞个比赛的话，可以这样，大家可以将你的程序打包并加密码，并以附件形式贴出。到了约定期限，告知密码，这样大家就可以拿到程序并测评。

无心人 发表于 2008-3-7 13:55:05

不要忒复杂了
想到代码你就发

这个题目要求技巧高些而已
还有输出多点
应该超过10万吧
：）

liangbch 发表于 2008-3-7 16:09:11

搜索 8个分数（7115组解）， 就需要 不少时间，如果指定16个分数，时间太长了。下面是我的源代码，如果需要搜索到16个，请修改 全局变量 max_level的值为16.#include "stdafx.h"
#include "math.h"

int maxN=256;
double maxN_r= 1/256.00;
int max_level=8;   //共有7115组解
//int max_level=16;
int count=0;

void printfArr(int arr[],int len)
{
        for (int i=0;i<len-1;i++)
        {
                printf("1/%d +",arr);
        }
        printf("1/%d =1\n",arr);
}

bool check(int arr[],int len)
{
        intn=arr;
        bool ret=true;
        for (int i=0;i<len-1;i++)
        {
                if (n % arr !=0)
                {
                        ret=false;
                        break;
                }
        }
        return ret;
}

void search(int arr[], int level, double rem)
{
        int i;
        double newRem;
       
        if (level==0)
        {
                for (i=2;i<=maxN;i++)
                {
                        arr=i;
                        newRem= 1- 1.0 /(double)i;
                        search(arr,level+1,newRem);
                }
        }
        else if (level<max_level-1)
        {
                if ( rem * arr - 1e-12 > max_level-level)
                {
                        return;

                }
                else if ( rem * maxN + 1e-12< 1)
                {
                        return;
                }


                int from= (int)(ceil(1.0/rem));
                if ( from<arr)
                        from =arr;

                for (i=from;i<=maxN;i++)
                {
                        arr=i;
                        newRem= rem - 1.0 /(double)i;
                        search(arr,level+1,newRem);
                }

        }
        else if (level==max_level-1)//level+1个数
        {
                int from= (int)(ceil(1.0/rem));
                if( from<=maxN && from>=arr && fabs( 1/(double)from - rem) <1e-15 )
                {
                       
                        arr= from;
                        if ( check( arr, max_level) )
                        {
                                count++;
                                printfArr(arr,level+1);
                        }
                }

        }

}

int main(int argc, char* argv[])
{
        int arr;
        count=0;
        search(arr,0,1.0);
        printf("总共 %d 组解\n",count);
        return 0;
}

liangbch 发表于 2008-3-7 16:29:37

有想到一种更快的算法，假定其中的某一组解是

1/N1 + 1/N2 + 1/N16=1
2<= N1 <= N2.. N15 < = N16

    我们只需关注N16即可， N16 一定大于等于16,且小于等于256, 对每个可能的N16,我们求其所有约数，如果约束个数小于16，则不予考虑。如果N16的约数个数大于等于16，则
求出N16 的所有约数，若他的所有约数的集合为S,我们只需要从这个结合S中去取数，并搜索即可。这样由于数的集合大为缩小，搜索速度也快的多。

   1-256中，240的约数做多，有20个。因此，在最坏情况下，需搜索的数从 255个降到20个。有望迅速解出。

gxqcn 发表于 2008-3-7 16:53:02

回复 14# 的帖子

不知先建一个倒数表是否可加速？一点小建议。

风云剑 发表于 2008-3-7 17:08:07

原帖由 无心人 于 2008-3-7 13:55 发表 http://bbs.emath.ac.cn/images/common/back.gif
不要忒复杂了
想到代码你就发

这个题目要求技巧高些而已
还有输出多点
应该超过10万吧
：）
我估计会远远超过10万的，记得以前做的2－100，选10个，就6万多了。

mathe 发表于 2008-3-7 17:37:41

原帖由 liangbch 于 2008-3-7 16:29 发表 http://bbs.emath.ac.cn/images/common/back.gif
有想到一种更快的算法，假定其中的某一组解是

1/N1 + 1/N2 + 1/N16=1
2
这种方法只能找出部分解，不能找到所有解。

mathe 发表于 2008-3-7 17:38:27

原帖由 gxqcn 于 2008-3-7 16:53 发表 http://bbs.emath.ac.cn/images/common/back.gif
不知先建一个倒数表是否可加速？一点小建议。
这种方法可以提高速度一些，但是不会有明显的改善，这种优化应该在最后才考虑。

liangbch 发表于 2008-3-7 17:40:28

按照上面的思路，重写编写程序，15秒可解除 4220074组解（不打出每组解）。
to 18#， 能否举个反例？
代码如下：#include "stdafx.h"
#include "math.h"


int maxN=256;
double maxN_r= 1/256.00;
int max_level=16;   //共有7115组解
//int max_level=16;
int count=0;

void printfArr(int arr[],int len)
{
#ifdef _DEBUG
        for (int i=0;i<len-1;i++)
        {
                printf("1/%d +",arr);
        }
        printf("1/%d =1\n",arr);
#endif
       
}

bool check(int arr[],int len)
{
        intn=arr;
        bool ret=true;
        for (int i=0;i<len-1;i++)
        {
                if (n % arr !=0)
                {
                        ret=false;
                        break;
                }
        }
        return ret;
}




void search(int arr[], int level, double rem)
{
        int i;
        double newRem;
       
        if (level==0)
        {
                for (i=2;i<=maxN;i++)
                {
                        arr=i;
                        newRem= 1- 1.0 /(double)i;
                        search(arr,level+1,newRem);
                }
        }
        else if (level<max_level-1)
        {
                if ( rem * arr - 1e-12 > max_level-level)
                {
                        return;

                }
                else if ( rem * maxN + 1e-12< 1)
                {
                        return;
                }


                int from= (int)(ceil(1.0/rem));
                if ( from<arr)
                        from =arr;

                for (i=from;i<=maxN;i++)
                {
                        arr=i;
                        newRem= rem - 1.0 /(double)i;
                        search(arr,level+1,newRem);
                }

        }
        else if (level==max_level-1)//level+1个数
        {
                int from= (int)(ceil(1.0/rem));
                if( from<=maxN && from>=arr && fabs( 1/(double)from - rem) <1e-15 )
                {
                       
                        arr= from;
                        if ( check( arr, max_level) )
                        {
                                count++;
                                printfArr(arr,level+1);
                        }
                }

        }
}


bool check2(int arr[],int len)
{
        intn=arr;
        int s=0;
        for (int i=0;i<len;i++)
        {
                s+= n / arr;
        }
        return (s==n);
}

void search2(int fac[], int facLen, int arr[], int level, double rem,int lastIdx,int n)
{
        int i;
        double newRem;
       
        if (level==0)
        {
                for (i=0;i<facLen;i++)
                {
                        arr=fac;
                        newRem= 1- 1.0 /(double)(fac);
                        search2(fac,facLen,arr,level+1,newRem,i,n);
                }
        }
        else if (level<max_level-1)
        {
               
                if ( rem * arr - 1e-12 > max_level-level)
                {
                        return;

                }
                else if ( rem * fac + 1e-12< 1)
                {
                        return;
                }

                for (i=lastIdx;i< facLen;i++)
                {
                        arr=fac;
                        newRem= rem - 1.0 /(double)(fac);
                        search2(fac,facLen,arr,level+1,newRem,i,n);
                }
        }
        else if (level== max_level-1)
        {
                arr=n;
                level++;
                rem-= 1.0/(double)n;

                if ( check2( arr, level) && fabs(rem)<1e-15 )
                {
                        count++;
                        printfArr(arr,level);
                }
               
        }

}


int getFacNums(int n, int arr[])
{
        int c=0;
        for (int i=2;i<=n; i++)
        {
                if (n % i==0)
                {
                        arr=i;
                        c++;
                }
        }
        return c;
}

void test2()
{
        int i;
        int fac;
        int arr;
        int c;

        for (i=max_level;i<=256;i++)
        {
                c= getFacNums(i,fac);
                search2(fac, c, arr, 0, 1.0, 0,i);
        }
}

int main(int argc, char* argv[])
{
        int arr;
        count=0;
        //search(arr,0,1.0);
        test2();
        printf("总共 %d 组解\n",count);
        return 0;
}

查看完整版本: 埃及分数问题