资源描述：
《埃及其分数问答题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、.*埃及分数问题:在古埃及,人们用单位分数的和(形如1／a,a是自然数)表示一切有理数。如:2／3＝1／2＋1／6,但不允许2／3＝1／3＋1／3,加数中有相同的。对于一个分数a／b,表示方法有很多种,但是哪种最好呢?1.加数少的比加数多的好2.加数个数相同的,最小的分数越大越好。如:19／45＝1／3＋1／12＋1／18019／45＝1／3＋1／15＋1／4519／45＝1／3＋1／18＋1／3019／45＝1／4＋1／6＋1／18019／45＝1／5＋1／6＋1／18最好的是最后一种即19／45＝1／5＋1／6＋1／18,因为1／18比1／180、1／45、1／30、1／18
2、0都大。给定两个整数a、b(0＜a＜b＜1000),编程计算出最好的表达方式。本算法出自ACM程序设计与分析P258。【贪心法】解析:本算法出自吕国英版算法设计与分析P149(旧),P160(新)。由于书上算法只使用了int类型变量进行计算,而当分数比较大时(如:0＜a＜b＜1000),那么则会溢出,导致计算结果错误,故此本算法将使用高精度计算进行求解。其算法思想不变,只是在计算时使用高精度计算,这样便可以求出0＜a＜b＜1000.*范围内的解。根据书中说明,贪心法求解思想是:逐步选择分数所包含的最大埃及分数,这些埃及分数之和就是问题的一个解。但是这样求出的解在决大多数情况下,不
3、是最佳表示法。只是问题的一个解而已。下面我们利用IDA*算法求得问题的最佳解。【IDA*法】解析:在进行本算法解析之前,我们先分析几个问题。上面我们利用贪心法进行了求解,在贪心法逐步选择当前分数所包含的最大埃及分数时,是按照如下方法计算的,例如:7／8内所包含的最大埃及分数是什么呢?7／8包含最大埃及分数分母＝8／7＋1＝27／8－1／2＝3／8,寻找3／8内的最大埃及分数如下:3／8包含最大埃及分数分母＝8／3＋1＝3得到3／8－1／3＝1／24,此时1／24已经是埃及分数,则不再进行计算,得到解7／8＝1／2＋1／3＋1／24。这样,我们总结得到每次当前被求解的分数的下界如下
4、:1／(当前分数的分母／当前分数的分子＋1)那么上界是什么呢?在进行IDA*.*算法求解之前,我利用了一般的搜索技术进行了求解,下面先说明一般搜索算法的思想。上面我们可以利用(分母／分子＋1)的方法求得当前分数的下界,由于这个下界是当前分数内所包含的最大埃及分数,那么从当前分数内减掉这个最大埃及分数后,假设得到的一个分数还不是埃及分数,将进入下一层的计算(同样求得下界)。那么这个下界一定是小于上一层的下界值的(原因很简单,分数越减越小),而由于本问题求解的是分数问题,那么逐层下降的下界涉及到分数的分母上则是递增的,例如:19／45＝1／3＋1／12＋1／1807／8＝1／2＋1／
5、3＋1／24其解的分母递增。那么要保证其分母递增,其每次的减数则不应超过被减数(即:小于被减数),否则得到的结果是降序的。这样我们得到一个求解上界的方法,下面举例说明:19／45－1／3＝4／45,则得到4／45为下界,那么上界是多少呢?根据上面的分析结果,要保证升序则减数应不超过被减数,而不超过19／45的减数是多少呢?我们将19／45乘以1／2即可(例如:被减数为5那么保证升序的结果时,最大减数为2,也就是将5×1／2－1)。不过这里面还有一个小问题需要说明:1.当分子是1时则上界是:1／(被减数分母×2－1)2.当分子非1时则上界是:被减数×1／2(通过比较)例如:19／4
6、5－1／3＝4／45,则3×2－1＝5(即:最小将1／3缩减至1／5,可以保证升序)将1／3的分母逐步扩大如下:19／45－1／4＝31／180(31／180＜1／5)19／45－1／5＝2／9(2／9＞1／5)19／45－1／6＝23／90(23／90＞1／5).*下面我们看一下后两种继续计算的结果:19／45－1／5＝2／92／9－1／5(本层下界)＝1／45从而得到一个解19／45＝1／5＋1／5＋1／45,但是问题中不允许出现加数相同的解,故这个解是要被舍掉的。再看一下另一个计算结果:19／45－1／6＝23／9023／90×1／4(本层下界)＝1／180从而得到一个解1
7、9／45＝1／6＋1／4＋1／180,显然解中出现了降序的分母排列,这个解也要被舍掉(原因是前面我们搜索的升序解时已经出现了一个1／4＋1／6＋1／180,而题目中并未对每个加数的出现位置做规定,为了过滤掉重复出现的解,并减少搜索空间,故此我们只按照升序的方向进行搜索,这样就保证了不出现重复的解,及不出现加数重复的解,也不会漏掉解)。上面说明了当分子是1的情况。当分子非1时,我们要将减数×1／2,然后通过比较大小确定是否再进行深度搜索。再看下面的例子:首先19／45－1／3＝4／
