十二元问题

Question

背景

12枚硬币的问题是典型的平衡之谜，在求职面试中常用.这个谜题第一次出现在1945年，是我祖父在我父亲向我母亲求婚时向他提出的！在拼图中有十二枚硬币，其中一枚比其他硬币重或轻(你不知道是哪个)。问题是要用三次天平来确定唯一的硬币。在某些变体中，还需要确定硬币是重的还是轻的。

这里的任务是解决涉及n个硬币的一般问题，在最坏的情况下使用最少的权重。没有必要确定硬币是重的还是轻的，只有哪一枚。此外，您不能获得任何额外的硬币以外的给定集(奇怪的是，这是不同的)。

结果表明，k重足以容纳(3^k-1)/2硬币(因此，在这种变化中的4种称重实际上可以处理13枚硬币)。此外(而且令人惊讶)，提前选择整套称量是可能的(但这里不需要)，而不是让未来的称量取决于过去的结果。有关两种可能的解决方案的说明，请参见本论文和这个Quora的答案。

任务

编写一个函数或程序，通过STDIN、命令行参数或函数参数以整数n作为输入，这在最坏的情况下用最少的权重解决了n个硬币的问题。该方案应：

• 以1,2,3-4,5,6格式将称重打印到STDOUT，以指示刻度两边的硬币列表。任何未称重的硬币都不应提及。硬币隐式编号从1到n，不需要按数字顺序打印(因此2,1-3,4与1,2-3,4相同)。
• 在每次称重后，程序应该通过STDIN等待输入，STDIN应该是<、=或>，指示秤的左侧是否比右侧轻、相同或重。
• 在最后一次称重后，程序应打印或返回唯一硬币的编号。
• 程序不需要处理来自用户的不一致的结果输入。
• 程序不需要处理n小于3。

示例输出

>> 3
1-2
>> =
1-3
>> <
3

# using Quora algorithm
>> 13
1,2,3,4-5,6,7,8
>> <
1,2,5-3,4,6
>> >
3-4
>> <
3

# using paper algorithm
>> 13
1,2,3,4-5,6,7,8
>> <
2,6,7,9-3,8,10,11
>> >
6,8,10,12-4,5,7,11
>> =
3

评分

最短代码获胜。适用标准规则。

Answer 1

Python 3: 497字节

I=lambda a,b:input(",".join(a)+"-"+",".join(b)+"\n>> ")
def A(a,b):
 l,L=len(a),len(b)
 if l+L==1:return(a or b)[0]
 m=(2*l+1-L)//3;M=m+L-l;x,y,X,Y=a[:m],a[m:2*m],b[:M],b[M:2*M];r=I(x+X,y+Y);return A(a[2*m:],b[2*M:])if r=="="else A(x,Y)if r=="<"else A(y,X)
def B(a,n=[]):
 if len(a)==1:return a[0]
 m=len(n);l=(len(a)+1+m)//3;x,y,z=a[:l],a[l:2*l-m],a[2*l-m:];r=I(x,y+n);return B(z,a[:1])if r=="="else A(x+z[:1-m],y)if r=="<"else A(y+z[:1-m],x)
print(B(list(map(str,range(1,int(input("N= "))+1)))))

我怀疑这可能会进一步缩小，但我看不到任何明显的地方(在每个函数的大约5个不同版本之后)。

该代码使用三个函数从此页实现了一个稍微修改过的算法版本。I函数执行IO (打印选项并返回用户的响应)。A和B函数实现了该算法的主要功能。A采用两个不同大小的列表，它们的大小正好是一个元素(尽管其中一个列表可能更大)：a中的一个硬币可能比正常的要轻，或者b中的一个硬币可能更重。B有双重职责。它需要一个硬币列表，a和另一个列表，其中一个硬币是已知的正确重量。两种情况下的长度四舍五入行为需要不同，这导致了头痛的无止境。

这两个算法函数可以在输入不超过以下大小的情况下，在k加权中找到异常加权的硬币：

• A：3^k总硬币，分为(3^k-1)/2和(3^k+1)/2两大类。
• B：如果提供了一个已知的好硬币，(3^k + 1)/2会给出硬币，而(3^k - 1)/2则会.

这里提出的问题说明，我们在开始时没有任何已知的好硬币，所以我们可以在一组(3^k - 1)/2中找到k称重中的坏硬币。

下面是我编写的一个测试函数，以确保我的代码没有请求虚假的称量，或者使用超过它应该使用的重量的数量：

def test(n):
    global I
    orig_I = I
    try:
        for x in range(3,n+1):
            max_count = 0
            for y in range(x*2):
                count = 0
                def I(a, b):
                    assert len(a) == len(b), "{} not the same length as {}".format(a,b)
                    nonlocal count
                    count += 1
                    if y//2 in a: return "<"if y%2 else ">"
                    if y//2 in b: return ">"if y%2 else "<"
                    return "="
                assert B(list(range(x)))==y//2, "{} {} not found in size {}".format(['heavy','light'][y%2], y//2+1, x)
                if count > max_count:
                    max_count = count
            print(x, max_count)
    finally:
        I = orig_I

这打印出最坏的情况下，重量的数字，为给定的一套测试后，每组合硬币和不良重量(重或轻)。

以下是多达125组的测试输出：

>>> test(150)
3 2
4 2
5 3
6 3
7 3
8 3
9 3
10 3
11 3
12 3
13 3
14 4
15 4
16 4
17 4
18 4
19 4
20 4
21 4
22 4
23 4
24 4
25 4
26 4
27 4
28 4
29 4
30 4
31 4
32 4
33 4
34 4
35 4
36 4
37 4
38 4
39 4
40 4
41 5
42 5
43 5
44 5
45 5
46 5
47 5
48 5
49 5
50 5
51 5
52 5
53 5
54 5
55 5
56 5
57 5
58 5
59 5
60 5
61 5
62 5
63 5
64 5
65 5
66 5
67 5
68 5
69 5
70 5
71 5
72 5
73 5
74 5
75 5
76 5
77 5
78 5
79 5
80 5
81 5
82 5
83 5
84 5
85 5
86 5
87 5
88 5
89 5
90 5
91 5
92 5
93 5
94 5
95 5
96 5
97 5
98 5
99 5
100 5
101 5
102 5
103 5
104 5
105 5
106 5
107 5
108 5
109 5
110 5
111 5
112 5
113 5
114 5
115 5
116 5
117 5
118 5
119 5
120 5
121 5
122 6
123 6
124 6
125 6

断点就在您预期的位置，在(3^k - 1)/2和(3^k + 1)/2之间。