埃及分数问题

mathe

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

liangbch

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

无心人

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

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

liangbch

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

1. #include "stdafx.h"
   
2. #include "math.h"
   
3. 
   
4. int maxN=256;
   
5. double maxN_r= 1/256.00;
   
6. int max_level=8;     //共有7115组解
   
7. //int max_level=16;
   
8. int count=0;
   
9. 
   
10. void printfArr(int arr[],int len)
    
11. {
    
12.         for (int i=0;i<len-1;i++)
    
13.         {
    
14.                 printf("1/%d +",arr[i]);
    
15.         }
    
16.         printf("1/%d =1\n",arr[len-1]);
    
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. 
    
34. void search(int arr[], int level, double rem)
    
35. {
    
36.         int i;
    
37.         double newRem;
    
38.        
    
39.         if (level==0)
    
40.         {
    
41.                 for (i=2;i<=maxN;i++)
    
42.                 {
    
43.                         arr[level]=i;
    
44.                         newRem= 1- 1.0 /(double)i;
    
45.                         search(arr,level+1,newRem);
    
46.                 }
    
47.         }
    
48.         else if (level<max_level-1)
    
49.         {
    
50.                 if ( rem * arr[level-1] - 1e-12 > max_level-level)
    
51.                 {
    
52.                         return;
    
53. 
    
54.                 }
    
55.                 else if ( rem * maxN + 1e-12  < 1)
    
56.                 {
    
57.                         return;
    
58.                 }
    
59. 
    
60. 
    
61.                 int from= (int)(ceil(1.0/rem));
    
62.                 if ( from<arr[level-1])
    
63.                         from =arr[level-1];
    
64. 
    
65.                 for (i=from;i<=maxN;i++)
    
66.                 {
    
67.                         arr[level]=i;
    
68.                         newRem= rem - 1.0 /(double)i;
    
69.                         search(arr,level+1,newRem);
    
70.                 }
    
71. 
    
72.         }
    
73.         else if (level==max_level-1)  //level+1个数
    
74.         {
    
75.                 int from= (int)(ceil(1.0/rem));
    
76.                 if  ( from<=maxN && from>=arr[level-1] && fabs( 1/(double)from - rem) <1e-15 )
    
77.                 {
    
78.                        
    
79.                         arr[level]= from;
    
80.                         if ( check( arr, max_level) )
    
81.                         {
    
82.                                 count++;
    
83.                                 printfArr(arr,level+1);
    
84.                         }
    
85.                 }
    
86. 
    
87.         }
    
88. 
    
89. }
    
90. 
    
91. int main(int argc, char* argv[])
    
92. {
    
93.         int arr[16];
    
94.         count=0;
    
95.         search(arr,0,1.0);
    
96.         printf("总共 %d 组解\n",count);
    
97.         return 0;
    
98. }

复制代码

liangbch

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

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 13:55 发表
不要忒复杂了
想到代码你就发

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

我估计会远远超过10万的，记得以前做的2－100，选10个，就6万多了。

mathe

原帖由 liangbch 于 2008-3-7 16:29 发表
有想到一种更快的算法，假定其中的某一组解是

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

这种方法只能找出部分解，不能找到所有解。

mathe

原帖由 gxqcn 于 2008-3-7 16:53 发表
不知先建一个倒数表是否可加速？一点小建议。

这种方法可以提高速度一些，但是不会有明显的改善，这种优化应该在最后才考虑。

liangbch

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

1. #include "stdafx.h"
   
2. #include "math.h"
   
3. 
   
4. 
   
5. int maxN=256;
   
6. double maxN_r= 1/256.00;
   
7. int max_level=16;     //共有7115组解
   
8. //int max_level=16;
   
9. int count=0;
   
10. 
    
11. void printfArr(int arr[],int len)
    
12. {
    
13. #ifdef _DEBUG
    
14.         for (int i=0;i<len-1;i++)
    
15.         {
    
16.                 printf("1/%d +",arr[i]);
    
17.         }
    
18.         printf("1/%d =1\n",arr[len-1]);
    
19. #endif
    
20.        
    
21. }
    
22. 
    
23. bool check(int arr[],int len)
    
24. {
    
25.         int  n=arr[len-1];
    
26.         bool ret=true;
    
27.         for (int i=0;i<len-1;i++)
    
28.         {
    
29.                 if (n % arr[i] !=0)
    
30.                 {
    
31.                         ret=false;
    
32.                         break;
    
33.                 }
    
34.         }
    
35.         return ret;
    
36. }
    
37. 
    
38. 
    
39. 
    
40. 
    
41. void search(int arr[], int level, double rem)
    
42. {
    
43.         int i;
    
44.         double newRem;
    
45.        
    
46.         if (level==0)
    
47.         {
    
48.                 for (i=2;i<=maxN;i++)
    
49.                 {
    
50.                         arr[level]=i;
    
51.                         newRem= 1- 1.0 /(double)i;
    
52.                         search(arr,level+1,newRem);
    
53.                 }
    
54.         }
    
55.         else if (level<max_level-1)
    
56.         {
    
57.                 if ( rem * arr[level-1] - 1e-12 > max_level-level)
    
58.                 {
    
59.                         return;
    
60. 
    
61.                 }
    
62.                 else if ( rem * maxN + 1e-12  < 1)
    
63.                 {
    
64.                         return;
    
65.                 }
    
66. 
    
67. 
    
68.                 int from= (int)(ceil(1.0/rem));
    
69.                 if ( from<arr[level-1])
    
70.                         from =arr[level-1];
    
71. 
    
72.                 for (i=from;i<=maxN;i++)
    
73.                 {
    
74.                         arr[level]=i;
    
75.                         newRem= rem - 1.0 /(double)i;
    
76.                         search(arr,level+1,newRem);
    
77.                 }
    
78. 
    
79.         }
    
80.         else if (level==max_level-1)  //level+1个数
    
81.         {
    
82.                 int from= (int)(ceil(1.0/rem));
    
83.                 if  ( from<=maxN && from>=arr[level-1] && fabs( 1/(double)from - rem) <1e-15 )
    
84.                 {
    
85.                        
    
86.                         arr[level]= from;
    
87.                         if ( check( arr, max_level) )
    
88.                         {
    
89.                                 count++;
    
90.                                 printfArr(arr,level+1);
    
91.                         }
    
92.                 }
    
93. 
    
94.         }
    
95. }
    
96. 
    
97. 
    
98. bool check2(int arr[],int len)
    
99. {
    
100.         int  n=arr[len-1];
     
101.         int s=0;
     
102.         for (int i=0;i<len;i++)
     
103.         {
     
104.                 s+= n / arr[i];
     
105.         }
     
106.         return (s==n);
     
107. }
     
108. 
     
109. void search2(int fac[], int facLen, int arr[], int level, double rem,int lastIdx,int n)
     
110. {
     
111.         int i;
     
112.         double newRem;
     
113.        
     
114.         if (level==0)
     
115.         {
     
116.                 for (i=0;i<facLen;i++)
     
117.                 {
     
118.                         arr[level]=fac[i];
     
119.                         newRem= 1- 1.0 /(double)(fac[i]);
     
120.                         search2(fac,facLen,arr,level+1,newRem,i,n);
     
121.                 }
     
122.         }
     
123.         else if (level<max_level-1)
     
124.         {
     
125.                
     
126.                 if ( rem * arr[level-1] - 1e-12 > max_level-level)
     
127.                 {
     
128.                         return;
     
129. 
     
130.                 }
     
131.                 else if ( rem * fac[facLen-1] + 1e-12  < 1)
     
132.                 {
     
133.                         return;
     
134.                 }
     
135. 
     
136.                 for (i=lastIdx;i< facLen;i++)
     
137.                 {
     
138.                         arr[level]=fac[i];
     
139.                         newRem= rem - 1.0 /(double)(fac[i]);
     
140.                         search2(fac,facLen,arr,level+1,newRem,i,n);
     
141.                 }
     
142.         }
     
143.         else if (level== max_level-1)
     
144.         {
     
145.                 arr[level]=n;
     
146.                 level++;
     
147.                 rem-= 1.0/(double)n;
     
148. 
     
149.                 if ( check2( arr, level) && fabs(rem)<1e-15 )
     
150.                 {
     
151.                         count++;
     
152.                         printfArr(arr,level);
     
153.                 }
     
154.                
     
155.         }
     
156. 
     
157. }
     
158. 
     
159. 
     
160. int getFacNums(int n, int arr[])
     
161. {
     
162.         int c=0;
     
163.         for (int i=2;i<=n; i++)
     
164.         {
     
165.                 if (n % i==0)
     
166.                 {
     
167.                         arr[c]=i;
     
168.                         c++;
     
169.                 }
     
170.         }
     
171.         return c;
     
172. }
     
173. 
     
174. void test2()
     
175. {
     
176.         int i;
     
177.         int fac[256];
     
178.         int arr[16];
     
179.         int c;
     
180. 
     
181.         for (i=max_level;i<=256;i++)
     
182.         {
     
183.                 c= getFacNums(i,fac);
     
184.                 search2(fac, c, arr, 0, 1.0, 0,i);
     
185.         }
     
186. }
     
187. 
     
188. int main(int argc, char* argv[])
     
189. {
     
190.         int arr[16];
     
191.         count=0;
     
192.         //search(arr,0,1.0);
     
193.         test2();
     
194.         printf("总共 %d 组解\n",count);
     
195.         return 0;
     
196. }

复制代码