织女的六把黄金尺子问题

liangbch · 发表于 2014-12-16 08:52:01

将规模降低，推算一下3把尺子能否度量1-10之间10个数的问题。

liangbch · 发表于 2014-12-16 09:47:09

找到一个3把尺子的方案,见下

第1把尺子：3段长度分别为1,2,5, 可度量1，2，3，5，7，8
第2把尺子：2段长度分别为4，6, 可度量4，6，10
第3把尺子：长度为9, 可度量9

liangbch · 发表于 2014-12-16 09:50:07

liangbch 发表于 2014-12-16 08:14
尽管如此，其搜索规模依然是很大的。
以5个刻度的尺子为例。其全部方案有 $56^6/2=15.4G $之多。

这是一个很松的上界。实际上，许多分支可以剪掉。比如所有各段的总长度不能超过56. 任何2段（每段指相邻2个刻度的部分）的长度必须互不相同。

zeroieme · 发表于 2014-12-16 10:48:20

liangbch 发表于 2014-12-16 09:47
找到一个3把尺子的方案,见下

第1把尺子：3段长度分别为1,2,5, 可度量1，2，3，5，7，8

暴搜3把尺子花了多久？

mathe · 发表于 2014-12-16 12:49:18

解不唯一

mathe · 发表于 2014-12-16 12:50:44

为了编程方便，我先使用位置刻度，即刻度线到一端的距离。一端的刻度为0，就省略了。
1 5 30 36 50 53； 9 21 37 47 55； 13 32 54 56； 11 44 51； 27 42； 39
求一个差分，就得到各段的长度。
1 4 25 11 14 3; 9 12 16 10 8; 13 19 22 2; 11 33 7; 27 15; 39

mathe · 发表于 2014-12-16 12:51:56

程序还在运行中，总数可能不少

mathe · 发表于 2014-12-16 13:03:52

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

mathe · 发表于 2014-12-16 13:09:05

#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 · 发表于 2014-12-16 13:11:15

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

账号		自动登录	找回密码
密码			欢迎注册

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

点评

点评

点评

评分

点评