数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[讨论] 埃及分数问题

[复制链接]
发表于 2008-3-7 13:01:44 | 显示全部楼层
记忆中好像有人发过很类似的ACM题目,不过感觉这种题目基本上就是靠搜索(技巧就在于如何更好的缩小搜索范围)
无心人发的这三个题目中应该这个最复杂
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-7 13:43:25 | 显示全部楼层
报个到先,准备写个程序。
如果想搞个比赛的话,可以这样,大家可以将你的程序打包并加密码,并以附件形式贴出。到了约定期限,告知密码,这样大家就可以拿到程序并测评。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-7 13:55:05 | 显示全部楼层
不要忒复杂了
想到代码你就发

这个题目要求技巧高些而已
还有输出多点
应该超过10万吧
:)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-7 16:09:11 | 显示全部楼层
搜索 8个分数(7115组解), 就需要 不少时间,如果指定16个分数,时间太长了。下面是我的源代码,如果需要搜索到16个,请修改 全局变量 max_level的值为16.
  1. #include "stdafx.h"
  2. #include "math.h"

  3. int maxN=256;
  4. double maxN_r= 1/256.00;
  5. int max_level=8;     //共有7115组解
  6. //int max_level=16;
  7. int count=0;

  8. void printfArr(int arr[],int len)
  9. {
  10.         for (int i=0;i<len-1;i++)
  11.         {
  12.                 printf("1/%d +",arr[i]);
  13.         }
  14.         printf("1/%d =1\n",arr[len-1]);
  15. }

  16. bool check(int arr[],int len)
  17. {
  18.         int  n=arr[len-1];
  19.         bool ret=true;
  20.         for (int i=0;i<len-1;i++)
  21.         {
  22.                 if (n % arr[i] !=0)
  23.                 {
  24.                         ret=false;
  25.                         break;
  26.                 }
  27.         }
  28.         return ret;
  29. }

  30. void search(int arr[], int level, double rem)
  31. {
  32.         int i;
  33.         double newRem;
  34.        
  35.         if (level==0)
  36.         {
  37.                 for (i=2;i<=maxN;i++)
  38.                 {
  39.                         arr[level]=i;
  40.                         newRem= 1- 1.0 /(double)i;
  41.                         search(arr,level+1,newRem);
  42.                 }
  43.         }
  44.         else if (level<max_level-1)
  45.         {
  46.                 if ( rem * arr[level-1] - 1e-12 > max_level-level)
  47.                 {
  48.                         return;

  49.                 }
  50.                 else if ( rem * maxN + 1e-12  < 1)
  51.                 {
  52.                         return;
  53.                 }


  54.                 int from= (int)(ceil(1.0/rem));
  55.                 if ( from<arr[level-1])
  56.                         from =arr[level-1];

  57.                 for (i=from;i<=maxN;i++)
  58.                 {
  59.                         arr[level]=i;
  60.                         newRem= rem - 1.0 /(double)i;
  61.                         search(arr,level+1,newRem);
  62.                 }

  63.         }
  64.         else if (level==max_level-1)  //level+1个数
  65.         {
  66.                 int from= (int)(ceil(1.0/rem));
  67.                 if  ( from<=maxN && from>=arr[level-1] && fabs( 1/(double)from - rem) <1e-15 )
  68.                 {
  69.                        
  70.                         arr[level]= from;
  71.                         if ( check( arr, max_level) )
  72.                         {
  73.                                 count++;
  74.                                 printfArr(arr,level+1);
  75.                         }
  76.                 }

  77.         }

  78. }

  79. int main(int argc, char* argv[])
  80. {
  81.         int arr[16];
  82.         count=0;
  83.         search(arr,0,1.0);
  84.         printf("总共 %d 组解\n",count);
  85.         return 0;
  86. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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个。有望迅速解出。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-7 16:53:02 | 显示全部楼层

回复 14# 的帖子

不知先建一个倒数表是否可加速?一点小建议。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-7 17:08:07 | 显示全部楼层
原帖由 无心人 于 2008-3-7 13:55 发表
不要忒复杂了
想到代码你就发

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

我估计会远远超过10万的,记得以前做的2-100,选10个,就6万多了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-7 17:37:41 | 显示全部楼层
原帖由 liangbch 于 2008-3-7 16:29 发表
有想到一种更快的算法,假定其中的某一组解是

1/N1 + 1/N2 + 1/N16=1
2

这种方法只能找出部分解,不能找到所有解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-7 17:38:27 | 显示全部楼层
原帖由 gxqcn 于 2008-3-7 16:53 发表
不知先建一个倒数表是否可加速?一点小建议。

这种方法可以提高速度一些,但是不会有明显的改善,这种优化应该在最后才考虑。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-7 17:40:28 | 显示全部楼层
按照上面的思路,重写编写程序,15秒可解除 4220074组解(不打出每组解)。
to 18#, 能否举个反例?
代码如下:
  1. #include "stdafx.h"
  2. #include "math.h"


  3. int maxN=256;
  4. double maxN_r= 1/256.00;
  5. int max_level=16;     //共有7115组解
  6. //int max_level=16;
  7. int count=0;

  8. void printfArr(int arr[],int len)
  9. {
  10. #ifdef _DEBUG
  11.         for (int i=0;i<len-1;i++)
  12.         {
  13.                 printf("1/%d +",arr[i]);
  14.         }
  15.         printf("1/%d =1\n",arr[len-1]);
  16. #endif
  17.        
  18. }

  19. bool check(int arr[],int len)
  20. {
  21.         int  n=arr[len-1];
  22.         bool ret=true;
  23.         for (int i=0;i<len-1;i++)
  24.         {
  25.                 if (n % arr[i] !=0)
  26.                 {
  27.                         ret=false;
  28.                         break;
  29.                 }
  30.         }
  31.         return ret;
  32. }




  33. void search(int arr[], int level, double rem)
  34. {
  35.         int i;
  36.         double newRem;
  37.        
  38.         if (level==0)
  39.         {
  40.                 for (i=2;i<=maxN;i++)
  41.                 {
  42.                         arr[level]=i;
  43.                         newRem= 1- 1.0 /(double)i;
  44.                         search(arr,level+1,newRem);
  45.                 }
  46.         }
  47.         else if (level<max_level-1)
  48.         {
  49.                 if ( rem * arr[level-1] - 1e-12 > max_level-level)
  50.                 {
  51.                         return;

  52.                 }
  53.                 else if ( rem * maxN + 1e-12  < 1)
  54.                 {
  55.                         return;
  56.                 }


  57.                 int from= (int)(ceil(1.0/rem));
  58.                 if ( from<arr[level-1])
  59.                         from =arr[level-1];

  60.                 for (i=from;i<=maxN;i++)
  61.                 {
  62.                         arr[level]=i;
  63.                         newRem= rem - 1.0 /(double)i;
  64.                         search(arr,level+1,newRem);
  65.                 }

  66.         }
  67.         else if (level==max_level-1)  //level+1个数
  68.         {
  69.                 int from= (int)(ceil(1.0/rem));
  70.                 if  ( from<=maxN && from>=arr[level-1] && fabs( 1/(double)from - rem) <1e-15 )
  71.                 {
  72.                        
  73.                         arr[level]= from;
  74.                         if ( check( arr, max_level) )
  75.                         {
  76.                                 count++;
  77.                                 printfArr(arr,level+1);
  78.                         }
  79.                 }

  80.         }
  81. }


  82. bool check2(int arr[],int len)
  83. {
  84.         int  n=arr[len-1];
  85.         int s=0;
  86.         for (int i=0;i<len;i++)
  87.         {
  88.                 s+= n / arr[i];
  89.         }
  90.         return (s==n);
  91. }

  92. void search2(int fac[], int facLen, int arr[], int level, double rem,int lastIdx,int n)
  93. {
  94.         int i;
  95.         double newRem;
  96.        
  97.         if (level==0)
  98.         {
  99.                 for (i=0;i<facLen;i++)
  100.                 {
  101.                         arr[level]=fac[i];
  102.                         newRem= 1- 1.0 /(double)(fac[i]);
  103.                         search2(fac,facLen,arr,level+1,newRem,i,n);
  104.                 }
  105.         }
  106.         else if (level<max_level-1)
  107.         {
  108.                
  109.                 if ( rem * arr[level-1] - 1e-12 > max_level-level)
  110.                 {
  111.                         return;

  112.                 }
  113.                 else if ( rem * fac[facLen-1] + 1e-12  < 1)
  114.                 {
  115.                         return;
  116.                 }

  117.                 for (i=lastIdx;i< facLen;i++)
  118.                 {
  119.                         arr[level]=fac[i];
  120.                         newRem= rem - 1.0 /(double)(fac[i]);
  121.                         search2(fac,facLen,arr,level+1,newRem,i,n);
  122.                 }
  123.         }
  124.         else if (level== max_level-1)
  125.         {
  126.                 arr[level]=n;
  127.                 level++;
  128.                 rem-= 1.0/(double)n;

  129.                 if ( check2( arr, level) && fabs(rem)<1e-15 )
  130.                 {
  131.                         count++;
  132.                         printfArr(arr,level);
  133.                 }
  134.                
  135.         }

  136. }


  137. int getFacNums(int n, int arr[])
  138. {
  139.         int c=0;
  140.         for (int i=2;i<=n; i++)
  141.         {
  142.                 if (n % i==0)
  143.                 {
  144.                         arr[c]=i;
  145.                         c++;
  146.                 }
  147.         }
  148.         return c;
  149. }

  150. void test2()
  151. {
  152.         int i;
  153.         int fac[256];
  154.         int arr[16];
  155.         int c;

  156.         for (i=max_level;i<=256;i++)
  157.         {
  158.                 c= getFacNums(i,fac);
  159.                 search2(fac, c, arr, 0, 1.0, 0,i);
  160.         }
  161. }

  162. int main(int argc, char* argv[])
  163. {
  164.         int arr[16];
  165.         count=0;
  166.         //search(arr,0,1.0);
  167.         test2();
  168.         printf("总共 %d 组解\n",count);
  169.         return 0;
  170. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-6-28 20:40 , Processed in 0.078448 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表