埃及分数问题

mathe

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

liangbch

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

无心人

不要忒复杂了 想到代码你就发 这个题目要求技巧高些而已 还有输出多点 应该超过10万吧 ：）

liangbch

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

1. #include "stdafx.h"
2. #include "math.h"
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;
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. }
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. }
34. void search(int arr[], int level, double rem)
35. {
36. int i;
37. double newRem;
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;
54. }
55. else if ( rem * maxN + 1e-12 < 1)
56. {
57. return;
58. }
61. int from= (int)(ceil(1.0/rem));
62. if ( from<arr[level-1])
63. from =arr[level-1];
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. }
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. {
79. arr[level]= from;
80. if ( check( arr, max_level) )
81. {
82. count++;
83. printfArr(arr,level+1);
84. }
85. }
87. }
89. }
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"
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;
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
21. }
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. }
41. void search(int arr[], int level, double rem)
42. {
43. int i;
44. double newRem;
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;
61. }
62. else if ( rem * maxN + 1e-12 < 1)
63. {
64. return;
65. }
68. int from= (int)(ceil(1.0/rem));
69. if ( from<arr[level-1])
70. from =arr[level-1];
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. }
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. {
86. arr[level]= from;
87. if ( check( arr, max_level) )
88. {
89. count++;
90. printfArr(arr,level+1);
91. }
92. }
94. }
95. }
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. }
109. void search2(int fac[], int facLen, int arr[], int level, double rem,int lastIdx,int n)
110. {
111. int i;
112. double newRem;
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. {
126. if ( rem * arr[level-1] - 1e-12 > max_level-level)
127. {
128. return;
130. }
131. else if ( rem * fac[facLen-1] + 1e-12 < 1)
132. {
133. return;
134. }
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;
149. if ( check2( arr, level) && fabs(rem)<1e-15 )
150. {
151. count++;
152. printfArr(arr,level);
153. }
155. }
157. }
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. }
174. void test2()
175. {
176. int i;
177. int fac[256];
178. int arr[16];
179. int c;
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. }
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. }

复制代码