回归数

无心人

我想了 如果淘汰，必然要用浮点运算，是否合算，并不是很确定 另外，40位的候选并不是很多，4亿左右

medie2005

原帖由 无心人 于 2009-1-7 14:33 发表 另外，40位的候选并不是很多，4亿左右

怎么算出来的?

无心人

终于正确了，在计算中

1. #include <stdlib.h>
2. #include <stdio.h>
3. #include <sys/time.h>
5. #define base 100000000
6. #define ds 5
8. int powD[10][ds];
9. int sum[ds];
10. int num[10];
11. int N;
12. struct timeval start, end;
14. void init(void)
15. {
16. int i, j, k;
18. for (i = 0; i <= 9; i ++)
19. for (j = 0; j < ds; j ++)
20. powD[i][j] = 0;
22. for (i = 0; i <= 9; i ++)
23. num[i] = 0;
25. for (i = 1; i <= 9; i ++)
26. powD[i][0] = i;
27. }
29. void nextPower(void)
30. {
31. int i, j, t;
32. for (i = 2; i <= 9; i ++)
33. {
34. t = 0;
35. for (j = 0; j < ds; j ++)
36. {
37. t = powD[i][j] * i + t;
38. if (t >= base)
39. {
40. powD[i][j] = t % base;
41. t /= base;
42. }
43. else
44. {
45. powD[i][j] = t;
46. t = 0;
47. }
48. }
49. }
50. }
52. int circle(int n, int b)
53. {
54. int i, j, k;
55. double tm;
57. if (n == 0)
58. {
59. if (sort())
60. {
61. k = ds - 1;
62. while ((sum[k] == 0) && (k >= 0))
63. k --;
64. gettimeofday(&end, NULL);
65. tm = (end.tv_sec - start.tv_sec) * 1000000.0 + (end.tv_usec - start.tv_usec);
66. tm /= 1000000.0;
67. printf("%4.4f ", tm);
68. printf("%2d: ", N);
69. printf("%d", sum[k]);
70. if (k > 0)
71. for (i = k - 1; i >= 0; i --)
72. printf("%08d", sum[i]);
73. printf("\n");
74. }
75. }
76. else
77. for (i = 0; i <= b; i ++)
78. {
79. num[i] ++;
80. circle(n-1, i);
81. num[i] --;
82. }
83. }
86. int sort(void)
87. {
88. int i, j, t;
89. int temp[ds], d[10];
91. for (i = 0; i < ds; i ++)
92. temp[i] = sum[i] = 0;
94. for (i = 0; i <= 9; i ++)
95. d[i] = 0;
97. for (i = 1; i <= 9; i ++)
98. if (num[i])
99. {
100. t = 0;
101. for (j = 0; j < ds; j ++)
102. {
103. t = powD[i][j] * num[i] + t;
104. if (t >= base)
105. {
106. temp[j] = t % base;
107. t /= base;
108. }
109. else
110. {
111. temp[j] = t;
112. t = 0;
113. }
114. }
116. t = 0;
117. for (j = 0; j < ds; j++)
118. {
119. t = temp[j] + sum[j] + t;
120. if (t >= base)
121. {
122. sum[j] = t - 100000000;
123. t = 1;
124. }
125. else
126. {
127. sum[j] = t;
128. t = 0;
129. }
130. }
131. }
133. for (i = ds - 1; i >= 0; i --)
134. {
135. t = sum[i];
136. if (t > 0)
137. while (t > 0)
138. {
139. d[t % 10] ++;
140. t /= 10;
141. }
142. }
144. for (i = 1; i <= 9; i ++)
145. if (num[i] != d[i]) return 0;
146. return 1;
147. }
149. int main(void)
150. {
151. int i, j;
153. gettimeofday(&start, NULL);
154. init();
155. nextPower(); //是平方
156. for (i = 2; i <= 40; i ++)
157. {
158. N = i;
159. printf("Search %d...\n", i);
160. circle(N, 9);
161. nextPower();
162. }
163. return 0;
164. }

复制代码

无心人

完全的结果 ======================= E:\MinGW\MSYS\math>hg Search 2... 0.0000 2: 0 0.0000 2: 1 Search 3... 0.0000 3: 0 0.0000 3: 1 0.0000 3: 153 0.0000 3: 370 0.0000 3: 371 0.0000 3: 407 Search 4... 0.0000 4: 0 0.0000 4: 1 0.0000 4: 1634 0.0000 4: 8208 0.0000 4: 9474 Search 5... 0.0000 5: 0 0.0000 5: 1 0.0000 5: 4150 0.0000 5: 4151 0.0000 5: 54748 0.0000 5: 92727 0.0000 5: 93084 Search 6... 0.0000 6: 0 0.0000 6: 1 0.0000 6: 548834 Search 7... 0.0000 7: 0 0.0000 7: 1 0.0000 7: 1741725 0.0000 7: 4210818 0.0000 7: 9800817 0.0000 7: 9926315 Search 8... 0.0000 8: 0 0.0000 8: 1 0.0000 8: 24678050 0.0000 8: 24678051 0.0000 8: 88593477 Search 9... 0.0156 9: 0 0.0156 9: 1 0.0156 9: 146511208 0.0156 9: 472335975 0.0156 9: 534494836 0.0156 9: 912985153 Search 10... 0.0313 10: 0 0.0313 10: 1 0.0469 10: 4679307774 Search 11... 0.0625 11: 0 0.0625 11: 1 0.0938 11: 32164049650 0.0938 11: 32164049651 0.0938 11: 40028394225 0.0938 11: 42678290603 0.0938 11: 44708635679 0.0938 11: 49388550606 0.1094 11: 82693916578 0.1094 11: 94204591914 Search 12... 0.1250 12: 0 0.1250 12: 1 Search 13... 0.2344 13: 0 0.2344 13: 1 0.2656 13: 564240140138 Search 14... 0.4219 14: 0 0.4219 14: 1 0.5781 14: 28116440335967 Search 15... 0.7344 15: 0 0.7344 15: 1 Search 16... 1.3125 16: 0 1.3125 16: 1 1.9375 16: 4338281769391370 1.9375 16: 4338281769391371 Search 17... 2.2031 17: 0 2.2031 17: 1 2.2500 17: 233411150132317 2.8906 17: 21897142587612075 3.0781 17: 35641594208964132 3.0938 17: 35875699062250035 Search 18... 3.5625 18: 0 3.5625 18: 1 Search 19... 5.6563 19: 0 5.6563 19: 1 6.9532 19: 1517841543307505039 7.8125 19: 3289582984443187032 8.1719 19: 4498128791164624869 8.2188 19: 4929273885928088826 Search 20... 8.8282 20: 0 8.8282 20: 1 13.0157 20: 63105425988599693916 Search 21... 13.4845 21: 0 13.4845 21: 1 16.2814 21: 128468643043731391252 19.0939 21: 449177399146038697307 Search 22... 20.3126 22: 0 20.3126 22: 1 Search 23... 30.1877 23: 0 30.1877 23: 1 39.2503 23: 21887696841122916288858 40.4378 23: 27879694893054074471405 40.4690 23: 27907865009977052567814 40.5315 23: 28361281321319229463398 41.1253 23: 35452590104031691935943 Search 24... 44.7659 24: 0 44.7815 24: 1 56.4379 24: 174088005938065293023722 57.1254 24: 188451485447897896036875 57.5004 24: 239313664430041569350093 Search 25... 64.6098 25: 0 64.6098 25: 1 69.0786 25: 114735624485461118832514 75.2505 25: 832662335985815242605070 75.2505 25: 832662335985815242605071 80.1255 25: 1550475334214501539088894 80.3286 25: 1553242162893771850669378 88.6099 25: 3706907995955475988644380 88.6099 25: 3706907995955475988644381 89.9225 25: 4422095118095899619457938 Search 26... 92.7662 26: 0 92.7662 26: 1 Search 27... 131.3602 27: 0 131.3602 27: 1 139.1728 27: 7584178683470015004720746 153.0322 27: 77888878776432530886487094 157.3760 27: 121204998563613372405438066 157.5635 27: 121270696006801314328439376 160.1729 27: 128851796696487777842012787 162.3292 27: 174650464499531377631639254 163.8917 27: 177265453171792792366489765 Search 28... 182.7824 28: 0 182.7824 28: 1 Search 29... 254.6579 29: 0 254.6579 29: 1 267.3298 29: 477144170826130800418527003 277.3612 29: 4716716265341543230394614213 283.3924 29: 5022908050052864745436221003 313.8458 29: 14607640612971980372614873089 320.5177 29: 19008174136254279995012734740 320.5177 29: 19008174136254279995012734741 328.8146 29: 23866716435523975980390369295 Search 30... 347.9085 30: 0 347.9085 30: 1 Search 31... 470.2218 31: 0 470.2218 31: 1 547.8629 31: 793545620525277858657607629822 558.9880 31: 1145037275765491025924292050346 596.5194 31: 1927890457142960697580636236639 606.2539 31: 2309092682616190307509695338915 Search 32... 634.3791 32: 0 634.3791 32: 1 793.6770 32: 17333509997782249308725103962772 Search 33... 841.5054 33: 0 841.5054 33: 1 916.8965 33: 32186410459473623435614002227248 1062.1787 33: 186709961001538790100634132976990 1062.6943 33: 186709961001538790100634132976991 Search 34... 1114.2884 34: 0 1114.2884 34: 1 1348.1180 34: 1122763285329372541592822900204593 Search 35... 1471.1032 35: 0 1471.1032 35: 1 1676.9639 35: 5250083909873201044638631458484846 1722.9954 35: 7673249664848285722449710136138169 1796.6990 35: 12639369517103790328947807201478392 1799.6990 35: 12679937780272278566303885594196922 Search 36... 1910.9341 36: 0 1910.9341 36: 1 2276.0302 36: 91097771122214850683543503173498149 Search 37... 2475.5627 37: 0 2475.5627 37: 1 2790.0022 37: 418510620208153136884574959404115822 2869.4246 37: 618670315011216949642642321868915308 3027.4881 37: 1219167219625434121569735803609966019 Search 38... 3200.9736 38: 0 3200.9736 38: 1 3736.1645 38: 7320233109580046612992702336326619665 3772.9148 38: 7403697806790834730831423191927508283 3927.6814 38: 12815792078366059955099770545296129367 Search 39... 4088.8074 39: 0 4088.8074 39: 1 4307.5588 39: 16427762135335641330720936105651700735 4904.6408 39: 83281823928125880164896079973522049472 4904.7814 39: 83281830613691836766959173718984508549 4999.6257 39: 115132219018763992565095597973971522400 4999.6257 39: 115132219018763992565095597973971522401 Search 40... 5223.6428 40: 0 5223.6428 40: 1 ==================================================== 可惜没输出最终时间 呵呵

无心人

呵呵 打算修改下 连扩展的一起算 从41算到64，是否可行呢？

无心人

好像核验的结果不对？？ 谁能提供第三方核验

medie2005

3 digits search start! 153 407 370 371 4 digits search start! 1634 8208 9474 5 digits search start! 54748 93084 92727 6 digits search start! 548834 7 digits search start! 1741725 4210818 9926315 9800817 8 digits search start! 24678050 24678051 88593477 9 digits search start! 146511208 912985153 534494836 472335975 10 digits search start! 4679307774 11 digits search start! 82693916578 94204591914 40028394225 44708635679 42678290603 49388550606 32164049651 32164049650 12 digits search start! 13 digits search start! 14 digits search start! 28116440335967 15 digits search start! 16 digits search start! 4338281769391371 4338281769391370 17 digits search start! 35875699062250035 35641594208964132 21897142587612075 18 digits search start! 19 digits search start! 3289582984443187032 4498128791164624869 4929273885928088826 1517841543307505039 20 digits search start! 63105425988599693916 21 digits search start! 449177399146038697307 128468643043731391252 22 digits search start! 23 digits search start! 21887696841122916288858 35452590104031691935943 28361281321319229463398 27907865009977052567814 27879694893054074471405 24 digits search start! 188451485447897896036875 174088005938065293023722 239313664430041569350093 25 digits search start! 1550475334214501539088894 1553242162893771850669378 4422095118095899619457938 3706907995955475988644380 3706907995955475988644381 26 digits search start! 27 digits search start! 121270696006801314328439376 121204998563613372405438066 128851796696487777842012787 177265453171792792366489765 174650464499531377631639254 28 digits search start! 29 digits search start! 19008174136254279995012734741 19008174136254279995012734740 23866716435523975980390369295 14607640612971980372614873089 30 digits search start! 31 digits search start! 2309092682616190307509695338915 1927890457142960697580636236639 1145037275765491025924292050346 32 digits search start! 17333509997782249308725103962772 33 digits search start! 186709961001538790100634132976990 186709961001538790100634132976991 34 digits search start! 1122763285329372541592822900204593 35 digits search start! 12639369517103790328947807201478392 12679937780272278566303885594196922 36 digits search start! 37 digits search start! 1219167219625434121569735803609966019 38 digits search start! 12815792078366059955099770545296129367 39 digits search start! 115132219018763992565095597973971522401 115132219018763992565095597973971522400 time : 3830016 ms press any key to continue...

无心人

似乎和 我的一致 但我找到的扩展回归数你没有搜索 我的不知道是否对 给出你的程序吧

medie2005

扩展回归数? 定义是什么?

mathe

这个题目可优化的机会应该很小,只是位数比较大的时候,可以事先淘汰掉很多组合. 比如如果发现某种组合计算结果太大了(比如一个含有30个数字的组合结果之和大于30位数),那么同样数目数字的组合中,每个数字都不小于这个组合的那些就可以淘汰掉了.