找回密码
 欢迎注册
楼主: 毒酒滴冻鸭

[讨论] 织女的六把黄金尺子问题

[复制链接]
发表于 2014-12-16 19:44:29 来自手机 | 显示全部楼层
普通个人电脑
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-12-16 19:51:35 | 显示全部楼层
  1. #include <iostream>
  2. using namespace std;

  3. const int N = 6;   //number of rulers
  4. const int MAX = N*(N+1)*(N+2)/6;   //number of lengths

  5. int i, j;          //indexes for traversing array
  6. int temp[N+1];     //temp lengths for current ruler
  7. int b[MAX+1];      //for checking repeat lengths
  8. int a[N+1][N+1];   //answer array

  9. int back()   //back one section
  10. {
  11.   a[i][j] = 0;
  12.   j--;
  13.   if (j == 0) {i++; j = i;}
  14.   return 0;
  15. }

  16. int next()   //forward to next section
  17. {
  18.   j++;
  19.   if (j > i) {i--; j = 1;}
  20.   return 0;   
  21. }

  22. int showAnswer()   //show an anwser
  23. {
  24.   int i, j;

  25.   for (i = N; i > 0; i--)
  26.   {
  27.      for (j = i; j > 1; j--) cout << a[i][j] << ",";
  28.      cout << a[i][1] << "|";
  29.   }
  30.   cout << endl;
  31.   return 0;
  32. }

  33. int check()   //check for duplicated or invalid lengths
  34. {
  35.   int m;

  36.   if (a[i][i] > a[i][1]) return 1;   //ruler in wrong direction
  37.   temp[0] = a[i][j];
  38.   for (m = 1; m < j; m++)
  39.   {
  40.     temp[m] = temp[m-1] + a[i][j-m];
  41.     if (temp[m] > MAX) return 1;   //length exceeds MAX
  42.     if (b[temp[m]]) return 2;   //length exists already
  43.   }
  44.   for (m = 0; m < j; m++) b[temp[m]] = 1;
  45.   return 0;
  46. }

  47. int cancel()   //cancel and rollback current section
  48. {
  49.   int m;

  50.   temp[0] = a[i][j];
  51.   b[temp[0]] = 0;
  52.   for (m = 1; m < j; m++)
  53.   {
  54.     temp[m] = temp[m-1] + a[i][j-m];
  55.     b[temp[m]] = 0;
  56.   }
  57.   return 0;
  58. }

  59. int main()
  60. {
  61.   int flag, count = 0;

  62.   // initialisation
  63.   for (i = 0; i <= N; i++) for (j = 0; j <= N; j++) a[i][j] = 0;
  64.   for (i = 0; i <= MAX; i++) b[i] = 0;

  65.   i = N, j = 1;   // start at last ruler, first section
  66.   while (1)
  67.   {
  68.     if (a[i][j] && b[a[i][j]]) cancel();   // rollback previous actions
  69.     a[i][j]++;
  70.     if (i == N && j == 1) cout << "[" << a[i][j] << "]" << endl;   //track progress
  71.     while (b[a[i][j]] && a[i][j] + a[i][j-1] <= MAX) a[i][j]++;
  72.     if (a[i][j] + a[i][j-1] > MAX)
  73.     {
  74.       back();
  75.       if (i > N) break;
  76.     }
  77.     else
  78.     {
  79.       flag = check();
  80.       if (flag == 0)
  81.       {
  82.         if (i == 1)
  83.         {
  84.           count++;
  85.           showAnswer();
  86.         }
  87.         else next();
  88.       }
  89.       else if (flag == 1)
  90.       {
  91.         back();
  92.         if (i > N) break;
  93.       }
  94.     }
  95.   }
  96.   cout << "\nThe number of answers is: " << count << endl;
  97.   return 0;
  98. } //rulers.cpp
复制代码

这个C++程序是根据几年前百度贴吧一位吧友的算法改编而成,可能不及mathe站主的C程序有效率,在我的core-i7手提电脑上也要运行接近十分钟才完成穷搜。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 21:38:40 来自手机 | 显示全部楼层
我的台式机性能应该比笔记本好。core i7 3.7GHz
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 21:47:53 来自手机 | 显示全部楼层
我运行了下你的代码,在我机器上4分多一点
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-12-17 02:38:58 | 显示全部楼层
mathe 发表于 2014-12-16 21:47
我运行了下你的代码,在我机器上4分多一点

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

点评

好吧,后来我也发现了这类程序都是单核运行的。。。性能不好指的是内存或缓存的速度不够快?  发表于 2014-12-17 15:06
四核没有用,我们的代码应该都没有使用,都是单线程的。 主要应该是笔记本性能不好  发表于 2014-12-17 06:15
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-17 08:20:59 来自手机 | 显示全部楼层
编译器我是g++ -O3
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-17 09:44:56 | 显示全部楼层
我的结果也出来了。搜索6把尺子,在我的笔记本电脑上用时3分钟。
我的运行环境:
CPU i7-4700HQ 2.4GH,编译器:VS 2010.

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

  1. Is searching the soultion when rule count is 1
  2. (1,)

  3. It take 0 ms and find 1 solution

  4. Is searching the soultion when rule count is 2
  5. (4,)
  6. (1,2,)

  7. (2,)
  8. (1,3,)

  9. It take 0 ms and find 2 solution

  10. Is searching the soultion when rule count is 3
  11. (9,)
  12. (4,6,)
  13. (1,2,5,)

  14. (8,)
  15. (2,5,)
  16. (1,3,6,)

  17. (6,)
  18. (4,5,)
  19. (2,1,7,)

  20. (7,)
  21. (2,8,)
  22. (3,1,5,)

  23. (10,)
  24. (1,7,)
  25. (3,2,4,)

  26. It take 0 ms and find 5 solution

  27. Is searching the soultion when rule count is 4
  28. (19,)
  29. (6,8,)
  30. (4,7,9,)
  31. (1,2,10,5,)

  32. (15,)
  33. (8,10,)
  34. (4,5,7,)
  35. (1,2,11,6,)

  36. (16,)
  37. (9,10,)
  38. (5,2,13,)
  39. (1,3,8,6,)

  40. (13,)
  41. (6,12,)
  42. (7,2,8,)
  43. (1,3,11,5,)

  44. (18,)
  45. (6,14,)
  46. (2,7,10,)
  47. (1,4,8,3,)

  48. (20,)
  49. (6,8,)
  50. (7,3,9,)
  51. (1,4,11,2,)

  52. (8,)
  53. (6,14,)
  54. (7,3,9,)
  55. (1,4,11,2,)

  56. (20,)
  57. (4,14,)
  58. (2,9,8,)
  59. (1,5,7,3,)

  60. (11,)
  61. (8,10,)
  62. (3,2,12,)
  63. (1,6,9,4,)

  64. (14,)
  65. (3,13,)
  66. (4,5,6,)
  67. (1,7,10,2,)

  68. (9,)
  69. (4,14,)
  70. (5,7,8,)
  71. (2,1,10,6,)

  72. (7,)
  73. (8,10,)
  74. (6,5,9,)
  75. (2,1,12,4,)

  76. (10,)
  77. (8,9,)
  78. (6,1,12,)
  79. (2,3,11,4,)

  80. (12,)
  81. (6,13,)
  82. (7,1,9,)
  83. (2,3,11,4,)

  84. (19,)
  85. (7,11,)
  86. (3,5,12,)
  87. (2,4,9,1,)

  88. (16,)
  89. (9,10,)
  90. (1,7,5,)
  91. (2,4,11,3,)

  92. (14,)
  93. (9,11,)
  94. (5,3,7,)
  95. (2,4,12,1,)

  96. (14,)
  97. (5,10,)
  98. (3,4,9,)
  99. (2,6,11,1,)

  100. (10,)
  101. (4,12,)
  102. (5,1,13,)
  103. (2,7,8,3,)

  104. (19,)
  105. (8,12,)
  106. (1,6,10,)
  107. (3,2,9,4,)

  108. (17,)
  109. (6,10,)
  110. (1,7,12,)
  111. (3,2,9,4,)

  112. (9,)
  113. (8,12,)
  114. (6,4,7,)
  115. (3,2,13,1,)

  116. (16,)
  117. (9,11,)
  118. (1,5,13,)
  119. (3,4,8,2,)

  120. (18,)
  121. (4,10,)
  122. (2,7,6,)
  123. (3,5,11,1,)

  124. (10,)
  125. (4,14,)
  126. (2,7,6,)
  127. (3,5,11,1,)

  128. (12,)
  129. (4,14,)
  130. (2,5,8,)
  131. (3,6,10,1,)

  132. (10,)
  133. (7,12,)
  134. (6,3,8,)
  135. (4,1,13,2,)

  136. (8,)
  137. (6,11,)
  138. (7,3,9,)
  139. (4,1,13,2,)

  140. (8,)
  141. (5,15,)
  142. (3,7,9,)
  143. (4,2,11,1,)

  144. (15,)
  145. (5,7,)
  146. (1,8,10,)
  147. (4,2,11,3,)

  148. (10,)
  149. (7,11,)
  150. (5,3,9,)
  151. (4,2,13,1,)

  152. (9,)
  153. (5,12,)
  154. (7,3,8,)
  155. (4,2,13,1,)

  156. (15,)
  157. (2,18,)
  158. (5,6,8,)
  159. (4,3,9,1,)

  160. (9,)
  161. (4,16,)
  162. (3,7,8,)
  163. (5,1,11,2,)

  164. (14,)
  165. (9,11,)
  166. (1,15,3,)
  167. (5,2,6,4,)

  168. (19,)
  169. (9,11,)
  170. (1,14,2,)
  171. (5,3,4,6,)

  172. (9,)
  173. (2,16,)
  174. (4,6,7,)
  175. (5,3,11,1,)

  176. (12,)
  177. (2,16,)
  178. (4,3,10,)
  179. (5,6,8,1,)

  180. (18,)
  181. (8,11,)
  182. (2,3,12,)
  183. (6,1,9,4,)

  184. (15,)
  185. (5,14,)
  186. (4,3,13,)
  187. (6,2,9,1,)

  188. (17,)
  189. (6,10,)
  190. (1,14,4,)
  191. (7,2,3,8,)

  192. (16,)
  193. (6,12,)
  194. (4,1,14,)
  195. (7,2,8,3,)

  196. (12,)
  197. (4,13,)
  198. (1,14,5,)
  199. (7,3,6,2,)

  200. (19,)
  201. (2,16,)
  202. (3,10,4,)
  203. (8,1,6,5,)

  204. (20,)
  205. (6,12,)
  206. (1,13,3,)
  207. (8,2,5,4,)

  208. (13,)
  209. (3,14,)
  210. (4,11,5,)
  211. (10,2,6,1,)

  212. (17,)
  213. (3,13,)
  214. (4,10,5,)
  215. (11,1,6,2,)

  216. It take 0 ms and find 47 solution

  217. Is searching the soultion when rule count is 5
  218. (34,)
  219. (14,18,)
  220. (5,20,8,)
  221. (9,7,15,4,)
  222. (1,2,10,11,6,)

  223. (33,)
  224. (5,22,)
  225. (7,12,16,)
  226. (4,9,11,10,)
  227. (1,2,15,8,6,)

  228. (22,)
  229. (9,23,)
  230. (5,15,14,)
  231. (7,10,16,2,)
  232. (1,3,8,13,6,)

  233. (35,)
  234. (16,17,)
  235. (6,14,12,)
  236. (10,5,8,11,)
  237. (1,3,18,7,2,)

  238. (30,)
  239. (12,19,)
  240. (2,9,15,)
  241. (10,8,14,3,)
  242. (1,4,16,7,6,)

  243. (32,)
  244. (16,18,)
  245. (7,15,13,)
  246. (8,11,12,2,)
  247. (1,5,4,17,3,)

  248. (27,)
  249. (4,18,)
  250. (8,16,9,)
  251. (7,10,11,2,)
  252. (1,5,14,12,3,)

  253. (20,)
  254. (4,28,)
  255. (2,15,10,)
  256. (11,5,13,6,)
  257. (1,7,14,9,3,)

  258. (23,)
  259. (12,22,)
  260. (6,20,7,)
  261. (4,13,15,3,)
  262. (1,8,2,14,5,)

  263. (26,)
  264. (4,25,)
  265. (12,3,20,)
  266. (6,10,11,7,)
  267. (1,8,5,17,2,)

  268. (29,)
  269. (5,22,)
  270. (4,14,12,)
  271. (3,8,13,7,)
  272. (1,9,6,17,2,)

  273. (29,)
  274. (6,25,)
  275. (7,13,8,)
  276. (3,9,14,4,)
  277. (1,10,5,17,2,)

  278. (32,)
  279. (9,15,)
  280. (8,13,14,)
  281. (3,2,20,6,)
  282. (1,10,7,12,4,)

  283. (22,)
  284. (8,19,)
  285. (3,12,13,)
  286. (5,4,20,6,)
  287. (1,10,7,14,2,)

  288. (28,)
  289. (4,27,)
  290. (6,13,11,)
  291. (5,9,12,8,)
  292. (2,1,15,7,10,)

  293. (18,)
  294. (10,22,)
  295. (7,6,17,)
  296. (9,11,14,1,)
  297. (2,3,16,8,4,)

  298. (32,)
  299. (14,20,)
  300. (1,12,17,)
  301. (9,7,8,11,)
  302. (2,3,18,4,6,)

  303. (24,)
  304. (14,20,)
  305. (1,16,11,)
  306. (7,6,9,10,)
  307. (2,3,18,8,4,)

  308. (21,)
  309. (16,17,)
  310. (11,7,13,)
  311. (8,1,14,12,)
  312. (2,3,19,6,4,)

  313. (25,)
  314. (9,22,)
  315. (1,20,7,)
  316. (10,5,8,11,)
  317. (2,4,12,14,3,)

  318. (27,)
  319. (15,20,)
  320. (11,10,13,)
  321. (16,3,9,5,)
  322. (2,4,18,7,1,)

  323. (25,)
  324. (15,17,)
  325. (4,8,18,)
  326. (10,1,20,3,)
  327. (2,5,9,13,6,)

  328. (34,)
  329. (6,22,)
  330. (13,4,16,)
  331. (9,3,15,8,)
  332. (2,5,14,10,1,)

  333. (22,)
  334. (6,28,)
  335. (13,4,16,)
  336. (9,3,15,8,)
  337. (2,5,14,10,1,)

  338. (26,)
  339. (15,17,)
  340. (3,16,11,)
  341. (13,1,8,12,)
  342. (2,5,18,6,4,)

  343. (31,)
  344. (10,18,)
  345. (11,5,19,)
  346. (8,4,21,1,)
  347. (2,7,6,14,3,)

  348. (33,)
  349. (16,19,)
  350. (4,20,6,)
  351. (10,5,12,1,)
  352. (2,7,14,8,3,)

  353. (21,)
  354. (1,29,)
  355. (5,15,13,)
  356. (9,3,19,4,)
  357. (2,8,6,11,7,)

  358. (35,)
  359. (13,20,)
  360. (4,12,14,)
  361. (6,1,21,3,)
  362. (2,9,8,10,5,)

  363. (31,)
  364. (4,20,)
  365. (3,23,6,)
  366. (7,8,10,9,)
  367. (2,11,1,16,5,)

  368. (25,)
  369. (5,26,)
  370. (7,10,18,)
  371. (12,9,11,2,)
  372. (3,1,15,8,6,)

  373. (17,)
  374. (5,26,)
  375. (7,18,10,)
  376. (12,9,11,2,)
  377. (3,1,15,8,6,)

  378. (28,)
  379. (5,26,)
  380. (10,7,18,)
  381. (12,9,11,2,)
  382. (3,1,15,8,6,)

  383. (24,)
  384. (13,22,)
  385. (7,16,9,)
  386. (15,5,6,8,)
  387. (3,1,17,10,2,)

  388. (26,)
  389. (12,23,)
  390. (5,15,7,)
  391. (8,6,10,9,)
  392. (3,1,17,11,2,)

  393. (23,)
  394. (11,24,)
  395. (4,16,14,)
  396. (12,6,7,8,)
  397. (3,2,17,9,1,)

  398. (33,)
  399. (5,21,)
  400. (2,20,12,)
  401. (10,8,11,6,)
  402. (3,4,9,14,1,)

  403. (26,)
  404. (10,19,)
  405. (13,1,20,)
  406. (2,6,16,9,)
  407. (3,4,11,12,5,)

  408. (21,)
  409. (10,16,)
  410. (1,24,9,)
  411. (11,6,12,2,)
  412. (3,4,15,8,5,)

  413. (20,)
  414. (10,19,)
  415. (2,16,15,)
  416. (8,1,13,12,)
  417. (3,4,17,6,5,)

  418. (29,)
  419. (16,19,)
  420. (5,12,15,)
  421. (13,1,9,11,)
  422. (3,4,18,6,2,)

  423. (19,)
  424. (13,16,)
  425. (5,10,17,)
  426. (14,9,11,1,)
  427. (3,4,18,6,2,)

  428. (23,)
  429. (10,21,)
  430. (2,9,15,)
  431. (4,12,17,1,)
  432. (3,5,14,6,7,)

  433. (29,)
  434. (8,26,)
  435. (4,20,11,)
  436. (10,5,17,1,)
  437. (3,6,7,12,2,)

  438. (30,)
  439. (15,16,)
  440. (2,21,12,)
  441. (8,1,19,6,)
  442. (3,7,4,13,5,)

  443. (30,)
  444. (9,17,)
  445. (1,14,19,)
  446. (5,6,16,2,)
  447. (3,7,13,8,4,)

  448. (29,)
  449. (6,17,)
  450. (5,16,9,)
  451. (7,12,14,1,)
  452. (3,8,2,18,4,)

  453. (17,)
  454. (6,23,)
  455. (5,16,9,)
  456. (7,12,14,1,)
  457. (3,8,2,18,4,)

  458. (21,)
  459. (8,23,)
  460. (1,26,7,)
  461. (11,2,17,5,)
  462. (3,9,6,10,4,)

  463. (32,)
  464. (1,23,)
  465. (8,11,14,)
  466. (7,2,20,6,)
  467. (3,10,5,12,4,)

  468. (29,)
  469. (5,26,)
  470. (9,6,19,)
  471. (4,7,16,1,)
  472. (3,10,8,12,2,)

  473. (31,)
  474. (7,17,)
  475. (1,15,11,)
  476. (5,4,19,6,)
  477. (3,10,8,12,2,)

  478. (17,)
  479. (7,24,)
  480. (1,15,11,)
  481. (5,4,19,6,)
  482. (3,10,8,12,2,)

  483. (26,)
  484. (10,24,)
  485. (2,23,8,)
  486. (1,6,13,9,)
  487. (3,11,4,12,5,)

  488. (33,)
  489. (10,13,)
  490. (2,22,7,)
  491. (8,1,19,6,)
  492. (3,11,4,12,5,)

  493. (13,)
  494. (10,23,)
  495. (2,22,7,)
  496. (8,1,19,6,)
  497. (3,11,4,12,5,)

  498. (30,)
  499. (12,19,)
  500. (9,2,23,)
  501. (8,10,14,3,)
  502. (4,1,15,6,7,)

  503. (21,)
  504. (15,19,)
  505. (6,8,16,)
  506. (3,7,13,12,)
  507. (4,1,17,9,2,)

  508. (31,)
  509. (15,17,)
  510. (7,11,16,)
  511. (12,2,8,13,)
  512. (4,1,19,6,3,)

  513. (29,)
  514. (13,19,)
  515. (8,14,12,)
  516. (16,2,9,6,)
  517. (4,1,20,3,7,)

  518. (23,)
  519. (11,17,)
  520. (1,19,13,)
  521. (9,3,15,7,)
  522. (4,2,8,16,5,)

  523. (15,)
  524. (9,23,)
  525. (3,16,11,)
  526. (8,5,20,1,)
  527. (4,2,12,10,7,)

  528. (21,)
  529. (11,15,)
  530. (10,9,14,)
  531. (5,3,17,7,)
  532. (4,2,16,12,1,)

  533. (21,)
  534. (11,14,)
  535. (3,16,15,)
  536. (5,7,10,13,)
  537. (4,2,18,8,1,)

  538. (20,)
  539. (12,18,)
  540. (3,16,15,)
  541. (8,2,11,14,)
  542. (4,5,17,6,1,)

  543. (26,)
  544. (6,25,)
  545. (7,16,12,)
  546. (5,3,14,10,)
  547. (4,9,2,18,1,)

  548. (20,)
  549. (8,22,)
  550. (6,11,12,)
  551. (7,2,24,1,)
  552. (4,10,5,13,3,)

  553. (23,)
  554. (9,22,)
  555. (2,14,10,)
  556. (3,5,20,7,)
  557. (4,11,6,12,1,)

  558. (28,)
  559. (10,14,)
  560. (8,9,16,)
  561. (3,2,21,6,)
  562. (4,11,7,12,1,)

  563. (18,)
  564. (14,15,)
  565. (2,21,11,)
  566. (9,10,12,4,)
  567. (5,1,7,17,3,)

  568. (27,)
  569. (7,19,)
  570. (3,14,18,)
  571. (2,8,12,11,)
  572. (5,1,15,9,4,)

  573. (24,)
  574. (2,30,)
  575. (7,11,15,)
  576. (4,10,13,8,)
  577. (5,1,16,3,9,)

  578. (24,)
  579. (7,14,)
  580. (4,15,16,)
  581. (3,10,12,8,)
  582. (5,1,17,9,2,)

  583. (27,)
  584. (14,16,)
  585. (2,20,13,)
  586. (11,4,8,9,)
  587. (5,1,18,7,3,)

  588. (32,)
  589. (12,16,)
  590. (8,13,14,)
  591. (1,10,19,4,)
  592. (5,2,15,3,6,)

  593. (27,)
  594. (11,14,)
  595. (9,8,13,)
  596. (3,12,19,1,)
  597. (5,2,16,6,4,)

  598. (22,)
  599. (10,24,)
  600. (8,12,11,)
  601. (15,1,13,4,)
  602. (5,2,19,6,3,)

  603. (27,)
  604. (16,18,)
  605. (2,12,17,)
  606. (8,3,21,1,)
  607. (5,4,6,13,7,)

  608. (26,)
  609. (14,16,)
  610. (3,17,15,)
  611. (10,2,11,8,)
  612. (5,4,18,6,1,)

  613. (31,)
  614. (13,15,)
  615. (4,22,8,)
  616. (10,9,14,2,)
  617. (5,6,1,17,3,)

  618. (28,)
  619. (4,27,)
  620. (14,2,17,)
  621. (8,3,15,6,)
  622. (5,7,13,9,1,)

  623. (14,)
  624. (15,17,)
  625. (3,16,9,)
  626. (2,4,20,7,)
  627. (5,8,10,11,1,)

  628. (22,)
  629. (6,26,)
  630. (4,13,12,)
  631. (3,8,16,7,)
  632. (5,9,1,18,2,)

  633. (23,)
  634. (7,22,)
  635. (11,8,13,)
  636. (6,3,24,1,)
  637. (5,10,2,14,4,)

  638. (24,)
  639. (8,23,)
  640. (10,3,19,)
  641. (9,5,16,4,)
  642. (6,1,11,15,2,)

  643. (30,)
  644. (10,22,)
  645. (12,9,14,)
  646. (16,2,11,4,)
  647. (6,1,19,5,3,)

  648. (22,)
  649. (12,18,)
  650. (2,14,17,)
  651. (11,4,9,10,)
  652. (6,1,20,5,3,)

  653. (25,)
  654. (15,17,)
  655. (4,14,16,)
  656. (10,1,12,8,)
  657. (6,3,19,5,2,)

  658. (31,)
  659. (13,22,)
  660. (3,17,9,)
  661. (2,5,14,11,)
  662. (6,4,8,15,1,)

  663. (33,)
  664. (3,23,)
  665. (7,11,17,)
  666. (2,13,14,5,)
  667. (6,4,12,8,1,)

  668. (20,)
  669. (8,26,)
  670. (1,17,13,)
  671. (4,3,16,9,)
  672. (6,5,10,12,2,)

  673. (21,)
  674. (2,28,)
  675. (4,16,11,)
  676. (1,8,15,10,)
  677. (6,7,5,14,3,)

  678. (32,)
  679. (14,20,)
  680. (1,15,11,)
  681. (3,2,19,9,)
  682. (6,7,10,8,4,)

  683. (22,)
  684. (3,29,)
  685. (2,15,8,)
  686. (4,12,14,5,)
  687. (6,7,11,9,1,)

  688. (33,)
  689. (15,17,)
  690. (1,24,5,)
  691. (9,3,19,4,)
  692. (6,8,2,11,7,)

  693. (35,)
  694. (5,22,)
  695. (4,21,8,)
  696. (1,10,13,7,)
  697. (6,9,3,14,2,)

  698. (30,)
  699. (8,26,)
  700. (5,12,11,)
  701. (7,3,21,1,)
  702. (6,9,4,14,2,)

  703. (31,)
  704. (10,22,)
  705. (4,17,13,)
  706. (6,3,15,5,)
  707. (7,1,11,14,2,)

  708. (20,)
  709. (4,28,)
  710. (2,21,10,)
  711. (5,11,13,6,)
  712. (7,1,14,3,9,)

  713. (33,)
  714. (13,18,)
  715. (3,12,17,)
  716. (11,5,9,10,)
  717. (7,1,20,2,4,)

  718. (29,)
  719. (15,16,)
  720. (5,13,17,)
  721. (11,3,9,10,)
  722. (7,1,20,4,2,)

  723. (23,)
  724. (15,20,)
  725. (1,26,6,)
  726. (4,12,13,5,)
  727. (7,2,8,11,3,)

  728. (30,)
  729. (13,20,)
  730. (4,22,5,)
  731. (6,10,18,1,)
  732. (7,2,12,3,8,)

  733. (35,)
  734. (16,17,)
  735. (1,26,4,)
  736. (10,5,13,6,)
  737. (7,2,12,8,3,)

  738. (12,)
  739. (13,18,)
  740. (5,16,6,)
  741. (4,10,19,1,)
  742. (7,2,15,8,3,)

  743. (26,)
  744. (6,18,)
  745. (5,14,15,)
  746. (2,9,21,1,)
  747. (7,3,13,4,8,)

  748. (31,)
  749. (6,26,)
  750. (1,16,12,)
  751. (14,8,11,2,)
  752. (7,3,15,5,4,)

  753. (26,)
  754. (14,16,)
  755. (2,18,13,)
  756. (11,4,8,9,)
  757. (7,3,19,5,1,)

  758. (21,)
  759. (6,26,)
  760. (2,15,14,)
  761. (3,10,12,8,)
  762. (7,4,5,18,1,)

  763. (21,)
  764. (1,28,)
  765. (9,6,19,)
  766. (5,13,14,3,)
  767. (7,4,12,8,2,)

  768. (25,)
  769. (5,29,)
  770. (1,22,9,)
  771. (3,10,11,6,)
  772. (7,8,4,14,2,)

  773. (27,)
  774. (11,22,)
  775. (1,17,13,)
  776. (3,9,16,7,)
  777. (8,2,4,15,5,)

  778. (19,)
  779. (11,23,)
  780. (1,16,15,)
  781. (4,5,21,3,)
  782. (8,2,12,6,7,)

  783. (31,)
  784. (4,17,)
  785. (7,12,11,)
  786. (1,13,15,5,)
  787. (8,2,16,6,3,)

  788. (26,)
  789. (4,28,)
  790. (1,20,13,)
  791. (6,9,14,2,)
  792. (8,3,7,12,5,)

  793. (12,)
  794. (13,19,)
  795. (5,23,6,)
  796. (10,4,16,1,)
  797. (8,3,15,7,2,)

  798. (31,)
  799. (13,14,)
  800. (3,20,9,)
  801. (5,2,17,11,)
  802. (8,4,6,15,1,)

  803. (29,)
  804. (1,24,)
  805. (2,21,10,)
  806. (5,13,14,3,)
  807. (8,4,7,9,6,)

  808. (19,)
  809. (4,28,)
  810. (7,11,12,)
  811. (2,13,14,6,)
  812. (9,1,16,5,3,)

  813. (18,)
  814. (4,28,)
  815. (7,12,11,)
  816. (2,13,14,6,)
  817. (9,1,16,5,3,)

  818. (23,)
  819. (4,28,)
  820. (11,7,12,)
  821. (2,13,14,6,)
  822. (9,1,16,5,3,)

  823. (29,)
  824. (8,26,)
  825. (11,5,14,)
  826. (3,12,13,7,)
  827. (9,1,17,4,2,)

  828. (25,)
  829. (11,20,)
  830. (1,17,16,)
  831. (2,6,21,3,)
  832. (9,4,10,5,7,)

  833. (21,)
  834. (15,16,)
  835. (7,10,18,)
  836. (2,4,23,3,)
  837. (9,5,8,11,1,)

  838. (32,)
  839. (12,17,)
  840. (8,13,10,)
  841. (3,2,22,6,)
  842. (9,7,4,14,1,)

  843. (19,)
  844. (13,15,)
  845. (1,20,11,)
  846. (4,3,22,5,)
  847. (9,8,6,10,2,)

  848. (31,)
  849. (3,27,)
  850. (4,15,13,)
  851. (5,9,12,8,)
  852. (10,1,6,16,2,)

  853. (22,)
  854. (14,17,)
  855. (12,8,13,)
  856. (2,5,23,4,)
  857. (10,1,15,3,6,)

  858. (25,)
  859. (16,17,)
  860. (8,13,14,)
  861. (1,5,23,3,)
  862. (10,2,7,11,4,)

  863. (30,)
  864. (4,29,)
  865. (3,17,11,)
  866. (6,8,13,5,)
  867. (10,2,7,15,1,)

  868. (27,)
  869. (9,20,)
  870. (5,6,19,)
  871. (4,13,15,3,)
  872. (10,2,14,7,1,)

  873. (24,)
  874. (6,28,)
  875. (2,16,11,)
  876. (5,9,17,4,)
  877. (10,3,12,7,1,)

  878. (27,)
  879. (11,20,)
  880. (6,17,12,)
  881. (3,4,21,5,)
  882. (10,8,1,13,2,)

  883. (32,)
  884. (16,17,)
  885. (7,14,13,)
  886. (2,4,22,3,)
  887. (11,1,8,10,5,)

  888. (31,)
  889. (14,20,)
  890. (10,9,13,)
  891. (3,4,21,5,)
  892. (11,1,15,2,6,)

  893. (18,)
  894. (8,25,)
  895. (5,23,6,)
  896. (4,10,16,1,)
  897. (11,2,7,12,3,)

  898. It take 265 ms and find 136 solution

  899. Is searching the soultion when rule count is 6
  900. (39,)
  901. (15,27,)
  902. (7,33,11,)
  903. (13,19,22,2,)
  904. (8,10,16,12,9,)
  905. (3,14,6,25,4,1,)

  906. It take 182256 ms and find 1 solution
复制代码

点评

结果完全吻合!程序很成功!  发表于 2014-12-17 15:07
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-17 09:46:05 | 显示全部楼层
这是我编写的代码。
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <windows.h>

  5. /* 说明:
  6. 我们定义尺子编号为i,(i>=0), 尺子i总是有i+1段。
  7. 我们首先搜索编号最大的尺子,然后搜索编号次小的尺子,最后搜索编号为0的尺子,在本程序尺子编号用rule_idx来表示
  8. */

  9. #define MAX_RULES_COUNT 8                //最多可搜索8把尺子
  10. #define MAX_SEG_COUNT  120                //最多可覆盖120种不同的长度
  11. int g_used[MAX_SEG_COUNT+1];        //used[i]=1表示长度i可被尺子测量
  12. int g_maxSegArr[]={1,4,10,20,35,56,84,120}; //maxSegArr[i]表示尺子i可测量的不同长度的总数
  13. int g_result[MAX_RULES_COUNT][MAX_RULES_COUNT]; // result[i][j]表示尺子i第j+1段的长度
  14. int g_count;
  15. void output_result( int rule_count)
  16. {
  17.         int i,j;
  18.         for(i=0;i<rule_count;i++)
  19.         {
  20.                 printf("(");
  21.                 for(j=0;j<=i;j++)
  22.                         printf("%d,",g_result[i][j]);
  23.                 printf(")\n");     
  24.         }
  25.         printf("\n");
  26.         g_count++;
  27. }

  28. int check(int rule_idx, int deep, int *pNewSegCount, int newSegs[] )
  29. {
  30.         int i,c,sum;
  31.         for (c=0,sum=0,i=deep-1;i>=0;i--)
  32.         {
  33.                 sum += g_result[rule_idx][i];
  34.                 if ( g_used[sum] )
  35.                         return 0;
  36.                 g_used[sum]=1;
  37.                 newSegs[c++]=sum;
  38.                 *pNewSegCount=c;
  39.         }
  40.         return 1;
  41. }

  42. //deep: 表示将要确定尺子第deep+1段的长度
  43. void new_mark(int rule_count,int seg_count,int rule_idx, int deep)
  44. {
  45.         int i,j,mid,flag,sum,new_used_count;
  46.         int new_used[MAX_SEG_COUNT+1];

  47.         mid=rule_idx/2; //第rule_idx+1把尺子中间段的编号
  48.         for (sum=0,i=0;i<deep;i++)
  49.                 sum += g_result[rule_idx][i];

  50.         for (i=1;i<=seg_count;i++)
  51.         {
  52.                 if ( g_used[i])
  53.                         continue;
  54.                
  55.                 if ( i + sum > seg_count)
  56.                         break;

  57.                 if ( deep==mid+1 && i< g_result[rule_idx][rule_idx-deep] )
  58.                         continue;  //消除重复的结果

  59.                 g_result[rule_idx][deep]=i;
  60.                 flag=check(rule_idx,deep+1,&new_used_count,new_used);
  61.                 if (flag )
  62.                 {
  63.                         if ( rule_idx==0)
  64.                                 output_result(rule_count);
  65.                         if ( deep==rule_idx)
  66.                                 new_mark(rule_count,seg_count,rule_idx-1,0);
  67.                         else
  68.                                 new_mark(rule_count,seg_count,rule_idx,deep+1);
  69.                 }
  70.                 for ( j=0;j<new_used_count;j++)
  71.                         g_used[new_used[j]]=0;
  72.         }
  73. }

  74. void search(int n)
  75. {
  76.         DWORD t;
  77.         printf("\nIs searching the soultion when rule count is %d\n",n);
  78.         t=::GetTickCount();
  79.         g_count=0;memset(g_result,0,sizeof(g_result));
  80.         new_mark(n,g_maxSegArr[n-1],n-1,0);
  81.         t=::GetTickCount()-t;
  82.         printf("It take %d ms and find %d solution\n",t,g_count);
  83. }

  84. int main(int argc, char* argv[])
  85. {
  86.         int i;
  87.         for (i=1;i<=6;i++ ) search(i);
  88.         return 0;
  89. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-17 11:02:22 | 显示全部楼层
我觉得上楼的58-62行是瓶颈。它需要检查很多次。改用链接来存储尚未可被尺子度量的数应该可加快搜索过程。晚上下班后重写一版,看看速度能否提高。

  1. if ( g_used[i])
  2.         continue;
  3. if ( i + sum > seg_count)
  4.         break;
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-17 22:23:06 | 显示全部楼层
不打算编写新版了。
刚刚测试了下3个程序的在我的电脑 (I7-4700HQ Vs2010) 运行时间,12#,22#和28#,仅仅测试一次。
12# 代码应该是没有消除对称的代码,运行时间为7分35秒
22# 代码的运行时间为5分34秒
28# 代码的的运行时间为2分35秒
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 16:59 , Processed in 0.047548 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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