织女的六把黄金尺子问题

zeroieme

mathe 发表于 2014-12-16 12:49
解不唯一

对称性！
如1号尺
1 5 30 36 50 53 转为差分形式  1 4 25 6 14 3
3 17 23 48 52 53 转为差分形式  3 14 6 25 4 1

6把尺子的一个解，正反表示，有$2^5=32$ 种组合。

zeroieme

我还在算，不过我加入了消对称代码

出来了

1. 1 4 25 6 14 3
   
2. 8 10 16 12 9
   
3. 2 22 19 13
   
4. 7 33 11
   
5. 15 27
   
6. 39

复制代码

毒酒滴冻鸭

这里大神果然很多。。。这道题算是一个不错的编程习作吧。。。手上还有几个很需要编程高手功力的数学趣题，有空提出研究！

mathe

消除对称时间可以减少到两分多。如果每个尺子的表示中首段小于尾段，时间将近3分钟，如果改成将最靠近中间两刻度消除对称情况，时间可缩减到略大于2分

gxqcn

如果略作修改，要求测量连续整数的区间跨度尽可能大，答案是否还是一样？会不会更复杂？

毒酒滴冻鸭

mathe 发表于 2014-12-16 15:09
消除对称时间可以减少到两分多。如果每个尺子的表示中首段小于尾段，时间将近3分钟，如果改 ...

这是用中科院级的超级电脑运算还是一般的个人电脑？

毒酒滴冻鸭

这是一楼的图配上各段长度标识，跟15#的数据一致。

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