织女的六把黄金尺子问题

mathe

编程20分钟，运行8分9秒，总共32个解

mathe

1. #include <stdio.h> #include <stdlib.h> #include <string.h> #define NUM_RULES 6 #define MAX_LENS_COUNT 6 #define TOTAL_STATES 56 static const int num_lens[NUM_RULES]={6,5,4,3,2,1}; static unsigned char used[TOTAL_STATES+1]; static int ruler_to_search; static int len_to_search; static int searched_len[NUM_RULES][MAX_LENS_COUNT]; static int count;  void output_result() {     int i,j;     printf("Solution %d:\n",++count);     for(i=0;i<NUM_RULES;i++){         printf("\t");         for(j=0;j<num_lens[i];j++){            printf("% 2d ",searched_len[i][j]);         }         printf("\n");     } }  void search_next() {     int i,j;     int prev_len=0;     if(len_to_search==num_lens[ruler_to_search]){         ruler_to_search++;len_to_search=0;         if(ruler_to_search==NUM_RULES){             output_result();             return;         }     }     if(len_to_search>0){        prev_len=searched_len[ruler_to_search][len_to_search-1];     }     for(i=prev_len+1;i<=TOTAL_STATES;++i){        if(used[i])continue;        for(j=0;j<len_to_search;j++){             if(used[i-searched_len[ruler_to_search][j]])break;        }        if(j<len_to_search)continue;        //find a candidate        searched_len[ruler_to_search][len_to_search]=i;        used[i]=1;        for(j=0;j<len_to_search;j++){             used[i-searched_len[ruler_to_search][j]]=1;        }        len_to_search++;        search_next();        len_to_search--;        if(len_to_search<0){             ruler_to_search--;             len_to_search=num_lens[ruler_to_search]-1;        }        used[i]=0;        for(j=0;j<len_to_search;j++){             used[i-searched_len[ruler_to_search][j]]=0;        }     } }  int main() {     search_next();     printf("Total %d solutions found\n",count); }

复制代码

mathe

Solution 1:          1  5  30  36  50  53          8  18  34  46  55          2  24  43  56          7  40  51          15  42          39 Solution 2:          1  5  30  36  50  53          8  18  34  46  55          2  24  43  56          7  40  51          27  42          39 Solution 3:          1  5  30  36  50  53          8  18  34  46  55          2  24  43  56          11  44  51          15  42          39 Solution 4:          1  5  30  36  50  53          8  18  34  46  55          2  24  43  56          11  44  51          27  42          39 Solution 5:          1  5  30  36  50  53          8  18  34  46  55          13  32  54  56          7  40  51          15  42          39 Solution 6:          1  5  30  36  50  53          8  18  34  46  55          13  32  54  56          7  40  51          27  42          39 Solution 7:          1  5  30  36  50  53          8  18  34  46  55          13  32  54  56          11  44  51          15  42          39 Solution 8:          1  5  30  36  50  53          8  18  34  46  55          13  32  54  56          11  44  51          27  42          39 Solution 9:          1  5  30  36  50  53          9  21  37  47  55          2  24  43  56          7  40  51          15  42          39 Solution 10:          1  5  30  36  50  53          9  21  37  47  55          2  24  43  56          7  40  51          27  42          39 Solution 11:          1  5  30  36  50  53          9  21  37  47  55          2  24  43  56          11  44  51          15  42          39 Solution 12:          1  5  30  36  50  53          9  21  37  47  55          2  24  43  56          11  44  51          27  42          39 Solution 13:          1  5  30  36  50  53          9  21  37  47  55          13  32  54  56          7  40  51          15  42          39 Solution 14:          1  5  30  36  50  53          9  21  37  47  55          13  32  54  56          7  40  51          27  42          39 Solution 15:          1  5  30  36  50  53          9  21  37  47  55          13  32  54  56          11  44  51          15  42          39 Solution 16:          1  5  30  36  50  53          9  21  37  47  55          13  32  54  56          11  44  51          27  42          39 Solution 17:          3  17  23  48  52  53          8  18  34  46  55          2  24  43  56          7  40  51          15  42          39 Solution 18:          3  17  23  48  52  53          8  18  34  46  55          2  24  43  56          7  40  51          27  42          39 Solution 19:          3  17  23  48  52  53          8  18  34  46  55          2  24  43  56          11  44  51          15  42          39 Solution 20:          3  17  23  48  52  53          8  18  34  46  55          2  24  43  56          11  44  51          27  42          39 Solution 21:          3  17  23  48  52  53          8  18  34  46  55          13  32  54  56          7  40  51          15  42          39 Solution 22:          3  17  23  48  52  53          8  18  34  46  55          13  32  54  56          7  40  51          27  42          39 Solution 23:          3  17  23  48  52  53          8  18  34  46  55          13  32  54  56          11  44  51          15  42          39 Solution 24:          3  17  23  48  52  53          8  18  34  46  55          13  32  54  56          11  44  51          27  42          39 Solution 25:          3  17  23  48  52  53          9  21  37  47  55          2  24  43  56          7  40  51          15  42          39 Solution 26:          3  17  23  48  52  53          9  21  37  47  55          2  24  43  56          7  40  51          27  42          39 Solution 27:          3  17  23  48  52  53          9  21  37  47  55          2  24  43  56          11  44  51          15  42          39 Solution 28:          3  17  23  48  52  53          9  21  37  47  55          2  24  43  56          11  44  51          27  42          39 Solution 29:          3  17  23  48  52  53          9  21  37  47  55          13  32  54  56          7  40  51          15  42          39 Solution 30:          3  17  23  48  52  53          9  21  37  47  55          13  32  54  56          7  40  51          27  42          39 Solution 31:          3  17  23  48  52  53          9  21  37  47  55          13  32  54  56          11  44  51          15  42          39 Solution 32:          3  17  23  48  52  53          9  21  37  47  55          13  32  54  56          11  44  51          27  42          39 Total 32 solutions found

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#的数据一致。