织女的六把黄金尺子问题

mathe

普通个人电脑

毒酒滴冻鸭

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. const int N = 6;   //number of rulers
   
5. const int MAX = N*(N+1)*(N+2)/6;   //number of lengths
   
6. 
   
7. int i, j;          //indexes for traversing array
   
8. int temp[N+1];     //temp lengths for current ruler
   
9. int b[MAX+1];      //for checking repeat lengths
   
10. int a[N+1][N+1];   //answer array
    
11. 
    
12. int back()   //back one section
    
13. {
    
14.   a[i][j] = 0;
    
15.   j--;
    
16.   if (j == 0) {i++; j = i;}
    
17.   return 0;
    
18. }
    
19. 
    
20. int next()   //forward to next section
    
21. {
    
22.   j++;
    
23.   if (j > i) {i--; j = 1;}
    
24.   return 0;   
    
25. }
    
26. 
    
27. int showAnswer()   //show an anwser
    
28. {
    
29.   int i, j;
    
30. 
    
31.   for (i = N; i > 0; i--)
    
32.   {
    
33.      for (j = i; j > 1; j--) cout << a[i][j] << ",";
    
34.      cout << a[i][1] << "|";
    
35.   }
    
36.   cout << endl;
    
37.   return 0;
    
38. }
    
39. 
    
40. int check()   //check for duplicated or invalid lengths
    
41. {
    
42.   int m;
    
43. 
    
44.   if (a[i][i] > a[i][1]) return 1;   //ruler in wrong direction
    
45.   temp[0] = a[i][j];
    
46.   for (m = 1; m < j; m++)
    
47.   {
    
48.     temp[m] = temp[m-1] + a[i][j-m];
    
49.     if (temp[m] > MAX) return 1;   //length exceeds MAX
    
50.     if (b[temp[m]]) return 2;   //length exists already
    
51.   }
    
52.   for (m = 0; m < j; m++) b[temp[m]] = 1;
    
53.   return 0;
    
54. }
    
55. 
    
56. int cancel()   //cancel and rollback current section
    
57. {
    
58.   int m;
    
59. 
    
60.   temp[0] = a[i][j];
    
61.   b[temp[0]] = 0;
    
62.   for (m = 1; m < j; m++)
    
63.   {
    
64.     temp[m] = temp[m-1] + a[i][j-m];
    
65.     b[temp[m]] = 0;
    
66.   }
    
67.   return 0;
    
68. }
    
69. 
    
70. int main()
    
71. {
    
72.   int flag, count = 0;
    
73. 
    
74.   // initialisation
    
75.   for (i = 0; i <= N; i++) for (j = 0; j <= N; j++) a[i][j] = 0;
    
76.   for (i = 0; i <= MAX; i++) b[i] = 0;
    
77. 
    
78.   i = N, j = 1;   // start at last ruler, first section
    
79.   while (1)
    
80.   {
    
81.     if (a[i][j] && b[a[i][j]]) cancel();   // rollback previous actions
    
82.     a[i][j]++;
    
83.     if (i == N && j == 1) cout << "[" << a[i][j] << "]" << endl;   //track progress
    
84.     while (b[a[i][j]] && a[i][j] + a[i][j-1] <= MAX) a[i][j]++;
    
85.     if (a[i][j] + a[i][j-1] > MAX)
    
86.     {
    
87.       back();
    
88.       if (i > N) break;
    
89.     }
    
90.     else
    
91.     {
    
92.       flag = check();
    
93.       if (flag == 0)
    
94.       {
    
95.         if (i == 1)
    
96.         {
    
97.           count++;
    
98.           showAnswer();
    
99.         }
    
100.         else next();
     
101.       }
     
102.       else if (flag == 1)
     
103.       {
     
104.         back();
     
105.         if (i > N) break;
     
106.       }
     
107.     }
     
108.   }
     
109.   cout << "\nThe number of answers is: " << count << endl;
     
110.   return 0;
     
111. } //rulers.cpp

复制代码

这个C++程序是根据几年前百度贴吧一位吧友的算法改编而成，可能不及mathe站主的C程序有效率，在我的core-i7手提电脑上也要运行接近十分钟才完成穷搜。。。

mathe

我的台式机性能应该比笔记本好。core i7 3.7GHz

mathe

我运行了下你的代码，在我机器上4分多一点

毒酒滴冻鸭

mathe 发表于 2014-12-16 21:47
我运行了下你的代码，在我机器上4分多一点

可能我的compiler不好，不能尽用四核CPU的威力。。。另外我的2.9GHz CPU的确不及你的快。。。

mathe

编译器我是g++ -O3

liangbch

我的结果也出来了。搜索6把尺子，在我的笔记本电脑上用时3分钟。
我的运行环境：
CPU i7-4700HQ 2.4GH，编译器：VS 2010.

我们程序可搜1-8把尺子的方案。目前只计算了前6把尺子。下面我的程序的运行结果。

1. 
   
2. Is searching the soultion when rule count is 1
   
3. (1,)
   
4. 
   
5. It take 0 ms and find 1 solution
   
6. 
   
7. Is searching the soultion when rule count is 2
   
8. (4,)
   
9. (1,2,)
   
10. 
    
11. (2,)
    
12. (1,3,)
    
13. 
    
14. It take 0 ms and find 2 solution
    
15. 
    
16. Is searching the soultion when rule count is 3
    
17. (9,)
    
18. (4,6,)
    
19. (1,2,5,)
    
20. 
    
21. (8,)
    
22. (2,5,)
    
23. (1,3,6,)
    
24. 
    
25. (6,)
    
26. (4,5,)
    
27. (2,1,7,)
    
28. 
    
29. (7,)
    
30. (2,8,)
    
31. (3,1,5,)
    
32. 
    
33. (10,)
    
34. (1,7,)
    
35. (3,2,4,)
    
36. 
    
37. It take 0 ms and find 5 solution
    
38. 
    
39. Is searching the soultion when rule count is 4
    
40. (19,)
    
41. (6,8,)
    
42. (4,7,9,)
    
43. (1,2,10,5,)
    
44. 
    
45. (15,)
    
46. (8,10,)
    
47. (4,5,7,)
    
48. (1,2,11,6,)
    
49. 
    
50. (16,)
    
51. (9,10,)
    
52. (5,2,13,)
    
53. (1,3,8,6,)
    
54. 
    
55. (13,)
    
56. (6,12,)
    
57. (7,2,8,)
    
58. (1,3,11,5,)
    
59. 
    
60. (18,)
    
61. (6,14,)
    
62. (2,7,10,)
    
63. (1,4,8,3,)
    
64. 
    
65. (20,)
    
66. (6,8,)
    
67. (7,3,9,)
    
68. (1,4,11,2,)
    
69. 
    
70. (8,)
    
71. (6,14,)
    
72. (7,3,9,)
    
73. (1,4,11,2,)
    
74. 
    
75. (20,)
    
76. (4,14,)
    
77. (2,9,8,)
    
78. (1,5,7,3,)
    
79. 
    
80. (11,)
    
81. (8,10,)
    
82. (3,2,12,)
    
83. (1,6,9,4,)
    
84. 
    
85. (14,)
    
86. (3,13,)
    
87. (4,5,6,)
    
88. (1,7,10,2,)
    
89. 
    
90. (9,)
    
91. (4,14,)
    
92. (5,7,8,)
    
93. (2,1,10,6,)
    
94. 
    
95. (7,)
    
96. (8,10,)
    
97. (6,5,9,)
    
98. (2,1,12,4,)
    
99. 
    
100. (10,)
     
101. (8,9,)
     
102. (6,1,12,)
     
103. (2,3,11,4,)
     
104. 
     
105. (12,)
     
106. (6,13,)
     
107. (7,1,9,)
     
108. (2,3,11,4,)
     
109. 
     
110. (19,)
     
111. (7,11,)
     
112. (3,5,12,)
     
113. (2,4,9,1,)
     
114. 
     
115. (16,)
     
116. (9,10,)
     
117. (1,7,5,)
     
118. (2,4,11,3,)
     
119. 
     
120. (14,)
     
121. (9,11,)
     
122. (5,3,7,)
     
123. (2,4,12,1,)
     
124. 
     
125. (14,)
     
126. (5,10,)
     
127. (3,4,9,)
     
128. (2,6,11,1,)
     
129. 
     
130. (10,)
     
131. (4,12,)
     
132. (5,1,13,)
     
133. (2,7,8,3,)
     
134. 
     
135. (19,)
     
136. (8,12,)
     
137. (1,6,10,)
     
138. (3,2,9,4,)
     
139. 
     
140. (17,)
     
141. (6,10,)
     
142. (1,7,12,)
     
143. (3,2,9,4,)
     
144. 
     
145. (9,)
     
146. (8,12,)
     
147. (6,4,7,)
     
148. (3,2,13,1,)
     
149. 
     
150. (16,)
     
151. (9,11,)
     
152. (1,5,13,)
     
153. (3,4,8,2,)
     
154. 
     
155. (18,)
     
156. (4,10,)
     
157. (2,7,6,)
     
158. (3,5,11,1,)
     
159. 
     
160. (10,)
     
161. (4,14,)
     
162. (2,7,6,)
     
163. (3,5,11,1,)
     
164. 
     
165. (12,)
     
166. (4,14,)
     
167. (2,5,8,)
     
168. (3,6,10,1,)
     
169. 
     
170. (10,)
     
171. (7,12,)
     
172. (6,3,8,)
     
173. (4,1,13,2,)
     
174. 
     
175. (8,)
     
176. (6,11,)
     
177. (7,3,9,)
     
178. (4,1,13,2,)
     
179. 
     
180. (8,)
     
181. (5,15,)
     
182. (3,7,9,)
     
183. (4,2,11,1,)
     
184. 
     
185. (15,)
     
186. (5,7,)
     
187. (1,8,10,)
     
188. (4,2,11,3,)
     
189. 
     
190. (10,)
     
191. (7,11,)
     
192. (5,3,9,)
     
193. (4,2,13,1,)
     
194. 
     
195. (9,)
     
196. (5,12,)
     
197. (7,3,8,)
     
198. (4,2,13,1,)
     
199. 
     
200. (15,)
     
201. (2,18,)
     
202. (5,6,8,)
     
203. (4,3,9,1,)
     
204. 
     
205. (9,)
     
206. (4,16,)
     
207. (3,7,8,)
     
208. (5,1,11,2,)
     
209. 
     
210. (14,)
     
211. (9,11,)
     
212. (1,15,3,)
     
213. (5,2,6,4,)
     
214. 
     
215. (19,)
     
216. (9,11,)
     
217. (1,14,2,)
     
218. (5,3,4,6,)
     
219. 
     
220. (9,)
     
221. (2,16,)
     
222. (4,6,7,)
     
223. (5,3,11,1,)
     
224. 
     
225. (12,)
     
226. (2,16,)
     
227. (4,3,10,)
     
228. (5,6,8,1,)
     
229. 
     
230. (18,)
     
231. (8,11,)
     
232. (2,3,12,)
     
233. (6,1,9,4,)
     
234. 
     
235. (15,)
     
236. (5,14,)
     
237. (4,3,13,)
     
238. (6,2,9,1,)
     
239. 
     
240. (17,)
     
241. (6,10,)
     
242. (1,14,4,)
     
243. (7,2,3,8,)
     
244. 
     
245. (16,)
     
246. (6,12,)
     
247. (4,1,14,)
     
248. (7,2,8,3,)
     
249. 
     
250. (12,)
     
251. (4,13,)
     
252. (1,14,5,)
     
253. (7,3,6,2,)
     
254. 
     
255. (19,)
     
256. (2,16,)
     
257. (3,10,4,)
     
258. (8,1,6,5,)
     
259. 
     
260. (20,)
     
261. (6,12,)
     
262. (1,13,3,)
     
263. (8,2,5,4,)
     
264. 
     
265. (13,)
     
266. (3,14,)
     
267. (4,11,5,)
     
268. (10,2,6,1,)
     
269. 
     
270. (17,)
     
271. (3,13,)
     
272. (4,10,5,)
     
273. (11,1,6,2,)
     
274. 
     
275. It take 0 ms and find 47 solution
     
276. 
     
277. Is searching the soultion when rule count is 5
     
278. (34,)
     
279. (14,18,)
     
280. (5,20,8,)
     
281. (9,7,15,4,)
     
282. (1,2,10,11,6,)
     
283. 
     
284. (33,)
     
285. (5,22,)
     
286. (7,12,16,)
     
287. (4,9,11,10,)
     
288. (1,2,15,8,6,)
     
289. 
     
290. (22,)
     
291. (9,23,)
     
292. (5,15,14,)
     
293. (7,10,16,2,)
     
294. (1,3,8,13,6,)
     
295. 
     
296. (35,)
     
297. (16,17,)
     
298. (6,14,12,)
     
299. (10,5,8,11,)
     
300. (1,3,18,7,2,)
     
301. 
     
302. (30,)
     
303. (12,19,)
     
304. (2,9,15,)
     
305. (10,8,14,3,)
     
306. (1,4,16,7,6,)
     
307. 
     
308. (32,)
     
309. (16,18,)
     
310. (7,15,13,)
     
311. (8,11,12,2,)
     
312. (1,5,4,17,3,)
     
313. 
     
314. (27,)
     
315. (4,18,)
     
316. (8,16,9,)
     
317. (7,10,11,2,)
     
318. (1,5,14,12,3,)
     
319. 
     
320. (20,)
     
321. (4,28,)
     
322. (2,15,10,)
     
323. (11,5,13,6,)
     
324. (1,7,14,9,3,)
     
325. 
     
326. (23,)
     
327. (12,22,)
     
328. (6,20,7,)
     
329. (4,13,15,3,)
     
330. (1,8,2,14,5,)
     
331. 
     
332. (26,)
     
333. (4,25,)
     
334. (12,3,20,)
     
335. (6,10,11,7,)
     
336. (1,8,5,17,2,)
     
337. 
     
338. (29,)
     
339. (5,22,)
     
340. (4,14,12,)
     
341. (3,8,13,7,)
     
342. (1,9,6,17,2,)
     
343. 
     
344. (29,)
     
345. (6,25,)
     
346. (7,13,8,)
     
347. (3,9,14,4,)
     
348. (1,10,5,17,2,)
     
349. 
     
350. (32,)
     
351. (9,15,)
     
352. (8,13,14,)
     
353. (3,2,20,6,)
     
354. (1,10,7,12,4,)
     
355. 
     
356. (22,)
     
357. (8,19,)
     
358. (3,12,13,)
     
359. (5,4,20,6,)
     
360. (1,10,7,14,2,)
     
361. 
     
362. (28,)
     
363. (4,27,)
     
364. (6,13,11,)
     
365. (5,9,12,8,)
     
366. (2,1,15,7,10,)
     
367. 
     
368. (18,)
     
369. (10,22,)
     
370. (7,6,17,)
     
371. (9,11,14,1,)
     
372. (2,3,16,8,4,)
     
373. 
     
374. (32,)
     
375. (14,20,)
     
376. (1,12,17,)
     
377. (9,7,8,11,)
     
378. (2,3,18,4,6,)
     
379. 
     
380. (24,)
     
381. (14,20,)
     
382. (1,16,11,)
     
383. (7,6,9,10,)
     
384. (2,3,18,8,4,)
     
385. 
     
386. (21,)
     
387. (16,17,)
     
388. (11,7,13,)
     
389. (8,1,14,12,)
     
390. (2,3,19,6,4,)
     
391. 
     
392. (25,)
     
393. (9,22,)
     
394. (1,20,7,)
     
395. (10,5,8,11,)
     
396. (2,4,12,14,3,)
     
397. 
     
398. (27,)
     
399. (15,20,)
     
400. (11,10,13,)
     
401. (16,3,9,5,)
     
402. (2,4,18,7,1,)
     
403. 
     
404. (25,)
     
405. (15,17,)
     
406. (4,8,18,)
     
407. (10,1,20,3,)
     
408. (2,5,9,13,6,)
     
409. 
     
410. (34,)
     
411. (6,22,)
     
412. (13,4,16,)
     
413. (9,3,15,8,)
     
414. (2,5,14,10,1,)
     
415. 
     
416. (22,)
     
417. (6,28,)
     
418. (13,4,16,)
     
419. (9,3,15,8,)
     
420. (2,5,14,10,1,)
     
421. 
     
422. (26,)
     
423. (15,17,)
     
424. (3,16,11,)
     
425. (13,1,8,12,)
     
426. (2,5,18,6,4,)
     
427. 
     
428. (31,)
     
429. (10,18,)
     
430. (11,5,19,)
     
431. (8,4,21,1,)
     
432. (2,7,6,14,3,)
     
433. 
     
434. (33,)
     
435. (16,19,)
     
436. (4,20,6,)
     
437. (10,5,12,1,)
     
438. (2,7,14,8,3,)
     
439. 
     
440. (21,)
     
441. (1,29,)
     
442. (5,15,13,)
     
443. (9,3,19,4,)
     
444. (2,8,6,11,7,)
     
445. 
     
446. (35,)
     
447. (13,20,)
     
448. (4,12,14,)
     
449. (6,1,21,3,)
     
450. (2,9,8,10,5,)
     
451. 
     
452. (31,)
     
453. (4,20,)
     
454. (3,23,6,)
     
455. (7,8,10,9,)
     
456. (2,11,1,16,5,)
     
457. 
     
458. (25,)
     
459. (5,26,)
     
460. (7,10,18,)
     
461. (12,9,11,2,)
     
462. (3,1,15,8,6,)
     
463. 
     
464. (17,)
     
465. (5,26,)
     
466. (7,18,10,)
     
467. (12,9,11,2,)
     
468. (3,1,15,8,6,)
     
469. 
     
470. (28,)
     
471. (5,26,)
     
472. (10,7,18,)
     
473. (12,9,11,2,)
     
474. (3,1,15,8,6,)
     
475. 
     
476. (24,)
     
477. (13,22,)
     
478. (7,16,9,)
     
479. (15,5,6,8,)
     
480. (3,1,17,10,2,)
     
481. 
     
482. (26,)
     
483. (12,23,)
     
484. (5,15,7,)
     
485. (8,6,10,9,)
     
486. (3,1,17,11,2,)
     
487. 
     
488. (23,)
     
489. (11,24,)
     
490. (4,16,14,)
     
491. (12,6,7,8,)
     
492. (3,2,17,9,1,)
     
493. 
     
494. (33,)
     
495. (5,21,)
     
496. (2,20,12,)
     
497. (10,8,11,6,)
     
498. (3,4,9,14,1,)
     
499. 
     
500. (26,)
     
501. (10,19,)
     
502. (13,1,20,)
     
503. (2,6,16,9,)
     
504. (3,4,11,12,5,)
     
505. 
     
506. (21,)
     
507. (10,16,)
     
508. (1,24,9,)
     
509. (11,6,12,2,)
     
510. (3,4,15,8,5,)
     
511. 
     
512. (20,)
     
513. (10,19,)
     
514. (2,16,15,)
     
515. (8,1,13,12,)
     
516. (3,4,17,6,5,)
     
517. 
     
518. (29,)
     
519. (16,19,)
     
520. (5,12,15,)
     
521. (13,1,9,11,)
     
522. (3,4,18,6,2,)
     
523. 
     
524. (19,)
     
525. (13,16,)
     
526. (5,10,17,)
     
527. (14,9,11,1,)
     
528. (3,4,18,6,2,)
     
529. 
     
530. (23,)
     
531. (10,21,)
     
532. (2,9,15,)
     
533. (4,12,17,1,)
     
534. (3,5,14,6,7,)
     
535. 
     
536. (29,)
     
537. (8,26,)
     
538. (4,20,11,)
     
539. (10,5,17,1,)
     
540. (3,6,7,12,2,)
     
541. 
     
542. (30,)
     
543. (15,16,)
     
544. (2,21,12,)
     
545. (8,1,19,6,)
     
546. (3,7,4,13,5,)
     
547. 
     
548. (30,)
     
549. (9,17,)
     
550. (1,14,19,)
     
551. (5,6,16,2,)
     
552. (3,7,13,8,4,)
     
553. 
     
554. (29,)
     
555. (6,17,)
     
556. (5,16,9,)
     
557. (7,12,14,1,)
     
558. (3,8,2,18,4,)
     
559. 
     
560. (17,)
     
561. (6,23,)
     
562. (5,16,9,)
     
563. (7,12,14,1,)
     
564. (3,8,2,18,4,)
     
565. 
     
566. (21,)
     
567. (8,23,)
     
568. (1,26,7,)
     
569. (11,2,17,5,)
     
570. (3,9,6,10,4,)
     
571. 
     
572. (32,)
     
573. (1,23,)
     
574. (8,11,14,)
     
575. (7,2,20,6,)
     
576. (3,10,5,12,4,)
     
577. 
     
578. (29,)
     
579. (5,26,)
     
580. (9,6,19,)
     
581. (4,7,16,1,)
     
582. (3,10,8,12,2,)
     
583. 
     
584. (31,)
     
585. (7,17,)
     
586. (1,15,11,)
     
587. (5,4,19,6,)
     
588. (3,10,8,12,2,)
     
589. 
     
590. (17,)
     
591. (7,24,)
     
592. (1,15,11,)
     
593. (5,4,19,6,)
     
594. (3,10,8,12,2,)
     
595. 
     
596. (26,)
     
597. (10,24,)
     
598. (2,23,8,)
     
599. (1,6,13,9,)
     
600. (3,11,4,12,5,)
     
601. 
     
602. (33,)
     
603. (10,13,)
     
604. (2,22,7,)
     
605. (8,1,19,6,)
     
606. (3,11,4,12,5,)
     
607. 
     
608. (13,)
     
609. (10,23,)
     
610. (2,22,7,)
     
611. (8,1,19,6,)
     
612. (3,11,4,12,5,)
     
613. 
     
614. (30,)
     
615. (12,19,)
     
616. (9,2,23,)
     
617. (8,10,14,3,)
     
618. (4,1,15,6,7,)
     
619. 
     
620. (21,)
     
621. (15,19,)
     
622. (6,8,16,)
     
623. (3,7,13,12,)
     
624. (4,1,17,9,2,)
     
625. 
     
626. (31,)
     
627. (15,17,)
     
628. (7,11,16,)
     
629. (12,2,8,13,)
     
630. (4,1,19,6,3,)
     
631. 
     
632. (29,)
     
633. (13,19,)
     
634. (8,14,12,)
     
635. (16,2,9,6,)
     
636. (4,1,20,3,7,)
     
637. 
     
638. (23,)
     
639. (11,17,)
     
640. (1,19,13,)
     
641. (9,3,15,7,)
     
642. (4,2,8,16,5,)
     
643. 
     
644. (15,)
     
645. (9,23,)
     
646. (3,16,11,)
     
647. (8,5,20,1,)
     
648. (4,2,12,10,7,)
     
649. 
     
650. (21,)
     
651. (11,15,)
     
652. (10,9,14,)
     
653. (5,3,17,7,)
     
654. (4,2,16,12,1,)
     
655. 
     
656. (21,)
     
657. (11,14,)
     
658. (3,16,15,)
     
659. (5,7,10,13,)
     
660. (4,2,18,8,1,)
     
661. 
     
662. (20,)
     
663. (12,18,)
     
664. (3,16,15,)
     
665. (8,2,11,14,)
     
666. (4,5,17,6,1,)
     
667. 
     
668. (26,)
     
669. (6,25,)
     
670. (7,16,12,)
     
671. (5,3,14,10,)
     
672. (4,9,2,18,1,)
     
673. 
     
674. (20,)
     
675. (8,22,)
     
676. (6,11,12,)
     
677. (7,2,24,1,)
     
678. (4,10,5,13,3,)
     
679. 
     
680. (23,)
     
681. (9,22,)
     
682. (2,14,10,)
     
683. (3,5,20,7,)
     
684. (4,11,6,12,1,)
     
685. 
     
686. (28,)
     
687. (10,14,)
     
688. (8,9,16,)
     
689. (3,2,21,6,)
     
690. (4,11,7,12,1,)
     
691. 
     
692. (18,)
     
693. (14,15,)
     
694. (2,21,11,)
     
695. (9,10,12,4,)
     
696. (5,1,7,17,3,)
     
697. 
     
698. (27,)
     
699. (7,19,)
     
700. (3,14,18,)
     
701. (2,8,12,11,)
     
702. (5,1,15,9,4,)
     
703. 
     
704. (24,)
     
705. (2,30,)
     
706. (7,11,15,)
     
707. (4,10,13,8,)
     
708. (5,1,16,3,9,)
     
709. 
     
710. (24,)
     
711. (7,14,)
     
712. (4,15,16,)
     
713. (3,10,12,8,)
     
714. (5,1,17,9,2,)
     
715. 
     
716. (27,)
     
717. (14,16,)
     
718. (2,20,13,)
     
719. (11,4,8,9,)
     
720. (5,1,18,7,3,)
     
721. 
     
722. (32,)
     
723. (12,16,)
     
724. (8,13,14,)
     
725. (1,10,19,4,)
     
726. (5,2,15,3,6,)
     
727. 
     
728. (27,)
     
729. (11,14,)
     
730. (9,8,13,)
     
731. (3,12,19,1,)
     
732. (5,2,16,6,4,)
     
733. 
     
734. (22,)
     
735. (10,24,)
     
736. (8,12,11,)
     
737. (15,1,13,4,)
     
738. (5,2,19,6,3,)
     
739. 
     
740. (27,)
     
741. (16,18,)
     
742. (2,12,17,)
     
743. (8,3,21,1,)
     
744. (5,4,6,13,7,)
     
745. 
     
746. (26,)
     
747. (14,16,)
     
748. (3,17,15,)
     
749. (10,2,11,8,)
     
750. (5,4,18,6,1,)
     
751. 
     
752. (31,)
     
753. (13,15,)
     
754. (4,22,8,)
     
755. (10,9,14,2,)
     
756. (5,6,1,17,3,)
     
757. 
     
758. (28,)
     
759. (4,27,)
     
760. (14,2,17,)
     
761. (8,3,15,6,)
     
762. (5,7,13,9,1,)
     
763. 
     
764. (14,)
     
765. (15,17,)
     
766. (3,16,9,)
     
767. (2,4,20,7,)
     
768. (5,8,10,11,1,)
     
769. 
     
770. (22,)
     
771. (6,26,)
     
772. (4,13,12,)
     
773. (3,8,16,7,)
     
774. (5,9,1,18,2,)
     
775. 
     
776. (23,)
     
777. (7,22,)
     
778. (11,8,13,)
     
779. (6,3,24,1,)
     
780. (5,10,2,14,4,)
     
781. 
     
782. (24,)
     
783. (8,23,)
     
784. (10,3,19,)
     
785. (9,5,16,4,)
     
786. (6,1,11,15,2,)
     
787. 
     
788. (30,)
     
789. (10,22,)
     
790. (12,9,14,)
     
791. (16,2,11,4,)
     
792. (6,1,19,5,3,)
     
793. 
     
794. (22,)
     
795. (12,18,)
     
796. (2,14,17,)
     
797. (11,4,9,10,)
     
798. (6,1,20,5,3,)
     
799. 
     
800. (25,)
     
801. (15,17,)
     
802. (4,14,16,)
     
803. (10,1,12,8,)
     
804. (6,3,19,5,2,)
     
805. 
     
806. (31,)
     
807. (13,22,)
     
808. (3,17,9,)
     
809. (2,5,14,11,)
     
810. (6,4,8,15,1,)
     
811. 
     
812. (33,)
     
813. (3,23,)
     
814. (7,11,17,)
     
815. (2,13,14,5,)
     
816. (6,4,12,8,1,)
     
817. 
     
818. (20,)
     
819. (8,26,)
     
820. (1,17,13,)
     
821. (4,3,16,9,)
     
822. (6,5,10,12,2,)
     
823. 
     
824. (21,)
     
825. (2,28,)
     
826. (4,16,11,)
     
827. (1,8,15,10,)
     
828. (6,7,5,14,3,)
     
829. 
     
830. (32,)
     
831. (14,20,)
     
832. (1,15,11,)
     
833. (3,2,19,9,)
     
834. (6,7,10,8,4,)
     
835. 
     
836. (22,)
     
837. (3,29,)
     
838. (2,15,8,)
     
839. (4,12,14,5,)
     
840. (6,7,11,9,1,)
     
841. 
     
842. (33,)
     
843. (15,17,)
     
844. (1,24,5,)
     
845. (9,3,19,4,)
     
846. (6,8,2,11,7,)
     
847. 
     
848. (35,)
     
849. (5,22,)
     
850. (4,21,8,)
     
851. (1,10,13,7,)
     
852. (6,9,3,14,2,)
     
853. 
     
854. (30,)
     
855. (8,26,)
     
856. (5,12,11,)
     
857. (7,3,21,1,)
     
858. (6,9,4,14,2,)
     
859. 
     
860. (31,)
     
861. (10,22,)
     
862. (4,17,13,)
     
863. (6,3,15,5,)
     
864. (7,1,11,14,2,)
     
865. 
     
866. (20,)
     
867. (4,28,)
     
868. (2,21,10,)
     
869. (5,11,13,6,)
     
870. (7,1,14,3,9,)
     
871. 
     
872. (33,)
     
873. (13,18,)
     
874. (3,12,17,)
     
875. (11,5,9,10,)
     
876. (7,1,20,2,4,)
     
877. 
     
878. (29,)
     
879. (15,16,)
     
880. (5,13,17,)
     
881. (11,3,9,10,)
     
882. (7,1,20,4,2,)
     
883. 
     
884. (23,)
     
885. (15,20,)
     
886. (1,26,6,)
     
887. (4,12,13,5,)
     
888. (7,2,8,11,3,)
     
889. 
     
890. (30,)
     
891. (13,20,)
     
892. (4,22,5,)
     
893. (6,10,18,1,)
     
894. (7,2,12,3,8,)
     
895. 
     
896. (35,)
     
897. (16,17,)
     
898. (1,26,4,)
     
899. (10,5,13,6,)
     
900. (7,2,12,8,3,)
     
901. 
     
902. (12,)
     
903. (13,18,)
     
904. (5,16,6,)
     
905. (4,10,19,1,)
     
906. (7,2,15,8,3,)
     
907. 
     
908. (26,)
     
909. (6,18,)
     
910. (5,14,15,)
     
911. (2,9,21,1,)
     
912. (7,3,13,4,8,)
     
913. 
     
914. (31,)
     
915. (6,26,)
     
916. (1,16,12,)
     
917. (14,8,11,2,)
     
918. (7,3,15,5,4,)
     
919. 
     
920. (26,)
     
921. (14,16,)
     
922. (2,18,13,)
     
923. (11,4,8,9,)
     
924. (7,3,19,5,1,)
     
925. 
     
926. (21,)
     
927. (6,26,)
     
928. (2,15,14,)
     
929. (3,10,12,8,)
     
930. (7,4,5,18,1,)
     
931. 
     
932. (21,)
     
933. (1,28,)
     
934. (9,6,19,)
     
935. (5,13,14,3,)
     
936. (7,4,12,8,2,)
     
937. 
     
938. (25,)
     
939. (5,29,)
     
940. (1,22,9,)
     
941. (3,10,11,6,)
     
942. (7,8,4,14,2,)
     
943. 
     
944. (27,)
     
945. (11,22,)
     
946. (1,17,13,)
     
947. (3,9,16,7,)
     
948. (8,2,4,15,5,)
     
949. 
     
950. (19,)
     
951. (11,23,)
     
952. (1,16,15,)
     
953. (4,5,21,3,)
     
954. (8,2,12,6,7,)
     
955. 
     
956. (31,)
     
957. (4,17,)
     
958. (7,12,11,)
     
959. (1,13,15,5,)
     
960. (8,2,16,6,3,)
     
961. 
     
962. (26,)
     
963. (4,28,)
     
964. (1,20,13,)
     
965. (6,9,14,2,)
     
966. (8,3,7,12,5,)
     
967. 
     
968. (12,)
     
969. (13,19,)
     
970. (5,23,6,)
     
971. (10,4,16,1,)
     
972. (8,3,15,7,2,)
     
973. 
     
974. (31,)
     
975. (13,14,)
     
976. (3,20,9,)
     
977. (5,2,17,11,)
     
978. (8,4,6,15,1,)
     
979. 
     
980. (29,)
     
981. (1,24,)
     
982. (2,21,10,)
     
983. (5,13,14,3,)
     
984. (8,4,7,9,6,)
     
985. 
     
986. (19,)
     
987. (4,28,)
     
988. (7,11,12,)
     
989. (2,13,14,6,)
     
990. (9,1,16,5,3,)
     
991. 
     
992. (18,)
     
993. (4,28,)
     
994. (7,12,11,)
     
995. (2,13,14,6,)
     
996. (9,1,16,5,3,)
     
997. 
     
998. (23,)
     
999. (4,28,)
     
1000. (11,7,12,)
      
1001. (2,13,14,6,)
      
1002. (9,1,16,5,3,)
      
1003. 
      
1004. (29,)
      
1005. (8,26,)
      
1006. (11,5,14,)
      
1007. (3,12,13,7,)
      
1008. (9,1,17,4,2,)
      
1009. 
      
1010. (25,)
      
1011. (11,20,)
      
1012. (1,17,16,)
      
1013. (2,6,21,3,)
      
1014. (9,4,10,5,7,)
      
1015. 
      
1016. (21,)
      
1017. (15,16,)
      
1018. (7,10,18,)
      
1019. (2,4,23,3,)
      
1020. (9,5,8,11,1,)
      
1021. 
      
1022. (32,)
      
1023. (12,17,)
      
1024. (8,13,10,)
      
1025. (3,2,22,6,)
      
1026. (9,7,4,14,1,)
      
1027. 
      
1028. (19,)
      
1029. (13,15,)
      
1030. (1,20,11,)
      
1031. (4,3,22,5,)
      
1032. (9,8,6,10,2,)
      
1033. 
      
1034. (31,)
      
1035. (3,27,)
      
1036. (4,15,13,)
      
1037. (5,9,12,8,)
      
1038. (10,1,6,16,2,)
      
1039. 
      
1040. (22,)
      
1041. (14,17,)
      
1042. (12,8,13,)
      
1043. (2,5,23,4,)
      
1044. (10,1,15,3,6,)
      
1045. 
      
1046. (25,)
      
1047. (16,17,)
      
1048. (8,13,14,)
      
1049. (1,5,23,3,)
      
1050. (10,2,7,11,4,)
      
1051. 
      
1052. (30,)
      
1053. (4,29,)
      
1054. (3,17,11,)
      
1055. (6,8,13,5,)
      
1056. (10,2,7,15,1,)
      
1057. 
      
1058. (27,)
      
1059. (9,20,)
      
1060. (5,6,19,)
      
1061. (4,13,15,3,)
      
1062. (10,2,14,7,1,)
      
1063. 
      
1064. (24,)
      
1065. (6,28,)
      
1066. (2,16,11,)
      
1067. (5,9,17,4,)
      
1068. (10,3,12,7,1,)
      
1069. 
      
1070. (27,)
      
1071. (11,20,)
      
1072. (6,17,12,)
      
1073. (3,4,21,5,)
      
1074. (10,8,1,13,2,)
      
1075. 
      
1076. (32,)
      
1077. (16,17,)
      
1078. (7,14,13,)
      
1079. (2,4,22,3,)
      
1080. (11,1,8,10,5,)
      
1081. 
      
1082. (31,)
      
1083. (14,20,)
      
1084. (10,9,13,)
      
1085. (3,4,21,5,)
      
1086. (11,1,15,2,6,)
      
1087. 
      
1088. (18,)
      
1089. (8,25,)
      
1090. (5,23,6,)
      
1091. (4,10,16,1,)
      
1092. (11,2,7,12,3,)
      
1093. 
      
1094. It take 265 ms and find 136 solution
      
1095. 
      
1096. Is searching the soultion when rule count is 6
      
1097. (39,)
      
1098. (15,27,)
      
1099. (7,33,11,)
      
1100. (13,19,22,2,)
      
1101. (8,10,16,12,9,)
      
1102. (3,14,6,25,4,1,)
      
1103. 
      
1104. It take 182256 ms and find 1 solution
      

复制代码

liangbch

这是我编写的代码。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. #include <windows.h>
   
5. 
   
6. /* 说明：
   
7. 我们定义尺子编号为i,(i>=0), 尺子i总是有i+1段。
   
8. 我们首先搜索编号最大的尺子，然后搜索编号次小的尺子，最后搜索编号为0的尺子，在本程序尺子编号用rule_idx来表示
   
9. */
   
10. 
    
11. #define MAX_RULES_COUNT 8                //最多可搜索8把尺子
    
12. #define MAX_SEG_COUNT  120                //最多可覆盖120种不同的长度
    
13. int g_used[MAX_SEG_COUNT+1];        //used[i]=1表示长度i可被尺子测量
    
14. int g_maxSegArr[]={1,4,10,20,35,56,84,120}; //maxSegArr[i]表示尺子i可测量的不同长度的总数
    
15. int g_result[MAX_RULES_COUNT][MAX_RULES_COUNT]; // result[i][j]表示尺子i第j+1段的长度
    
16. int g_count;
    
17. void output_result( int rule_count)
    
18. {
    
19.         int i,j;
    
20.         for(i=0;i<rule_count;i++)
    
21.         {
    
22.                 printf("(");
    
23.                 for(j=0;j<=i;j++)
    
24.                         printf("%d,",g_result[i][j]);
    
25.                 printf(")\n");     
    
26.         }
    
27.         printf("\n");
    
28.         g_count++;
    
29. }
    
30. 
    
31. int check(int rule_idx, int deep, int *pNewSegCount, int newSegs[] )
    
32. {
    
33.         int i,c,sum;
    
34.         for (c=0,sum=0,i=deep-1;i>=0;i--)
    
35.         {
    
36.                 sum += g_result[rule_idx][i];
    
37.                 if ( g_used[sum] )
    
38.                         return 0;
    
39.                 g_used[sum]=1;
    
40.                 newSegs[c++]=sum;
    
41.                 *pNewSegCount=c;
    
42.         }
    
43.         return 1;
    
44. }
    
45. 
    
46. //deep: 表示将要确定尺子第deep+1段的长度
    
47. void new_mark(int rule_count,int seg_count,int rule_idx, int deep)
    
48. {
    
49.         int i,j,mid,flag,sum,new_used_count;
    
50.         int new_used[MAX_SEG_COUNT+1];
    
51. 
    
52.         mid=rule_idx/2; //第rule_idx+1把尺子中间段的编号
    
53.         for (sum=0,i=0;i<deep;i++)
    
54.                 sum += g_result[rule_idx][i];
    
55. 
    
56.         for (i=1;i<=seg_count;i++)
    
57.         {
    
58.                 if ( g_used[i])
    
59.                         continue;
    
60.                
    
61.                 if ( i + sum > seg_count)
    
62.                         break;
    
63. 
    
64.                 if ( deep==mid+1 && i< g_result[rule_idx][rule_idx-deep] )
    
65.                         continue;  //消除重复的结果
    
66. 
    
67.                 g_result[rule_idx][deep]=i;
    
68.                 flag=check(rule_idx,deep+1,&new_used_count,new_used);
    
69.                 if (flag )
    
70.                 {
    
71.                         if ( rule_idx==0)
    
72.                                 output_result(rule_count);
    
73.                         if ( deep==rule_idx)
    
74.                                 new_mark(rule_count,seg_count,rule_idx-1,0);
    
75.                         else
    
76.                                 new_mark(rule_count,seg_count,rule_idx,deep+1);
    
77.                 }
    
78.                 for ( j=0;j<new_used_count;j++)
    
79.                         g_used[new_used[j]]=0;
    
80.         }
    
81. }
    
82. 
    
83. void search(int n)
    
84. {
    
85.         DWORD t;
    
86.         printf("\nIs searching the soultion when rule count is %d\n",n);
    
87.         t=::GetTickCount();
    
88.         g_count=0;memset(g_result,0,sizeof(g_result));
    
89.         new_mark(n,g_maxSegArr[n-1],n-1,0);
    
90.         t=::GetTickCount()-t;
    
91.         printf("It take %d ms and find %d solution\n",t,g_count);
    
92. }
    
93. 
    
94. int main(int argc, char* argv[])
    
95. {
    
96.         int i;
    
97.         for (i=1;i<=6;i++ ) search(i);
    
98.         return 0;
    
99. }
    

复制代码

liangbch

我觉得上楼的58-62行是瓶颈。它需要检查很多次。改用链接来存储尚未可被尺子度量的数应该可加快搜索过程。晚上下班后重写一版，看看速度能否提高。

1. 
   
2. if ( g_used[i])
   
3.         continue;
   
4. if ( i + sum > seg_count)
   
5.         break;
   

复制代码

liangbch

不打算编写新版了。
刚刚测试了下3个程序的在我的电脑 (I7-4700HQ Vs2010) 运行时间，12#，22#和28#，仅仅测试一次。
12# 代码应该是没有消除对称的代码，运行时间为7分35秒
22# 代码的运行时间为5分34秒
28# 代码的的运行时间为2分35秒