一年多前写的天平称球问题解法

黑色阳光_cu

有12球其大小、形状都一样，其中有一个球重量不一样（不知是轻或重）。给你一把天平，用三次把这个重量不一样的球称（找）出来。

推而广之，有N个球的情况呢？怎么样用Perl解题呢?

这里给出我一年多前写的代码：

1. #!/bin/env perl
   
2. 
   
3. use strict;
   
4. use warnings;
   
5. # use Data::Dumper;
   
6. 
   
7. my @balls = &ball_init(12);
   
8. my $bad_ball = &ball_find(\@balls);
   
9. if (defined $bad_ball)
   
10. {
    
11.         &ball_success($bad_ball);
    
12. }
    
13. else
    
14. {
    
15.         &ball_fail();
    
16. }
    
17. 
    
18. <STDIN>;
    
19. 
    
20. ########################################################################
    
21. 
    
22. sub ball_init
    
23. {
    
24.         my ($num) = @_;
    
25.         my @balls;
    
26.         my ($heavy, $error) = (10, 1);
    
27. 
    
28.         for (my $n = 1; $n <= $num; $n++)
    
29.         {
    
30.                 push(@balls, [$n, $heavy]);
    
31.         }
    
32. 
    
33.         my $select = int(rand($num));
    
34.         my $plus_or_minus = int(rand(2));
    
35.         if ($plus_or_minus)
    
36.         {
    
37.                 $balls[$select]->[1] += $error;
    
38.         }
    
39.         else
    
40.         {
    
41.                 $balls[$select]->[1] -= $error;
    
42.         }
    
43. 
    
44.         return @balls;
    
45. }
    
46. 
    
47. sub ball_find
    
48. {
    
49.         my @balls = @{$_[0]};
    
50.         my ($ref_buf, $deep) = ($_[1], $_[2]);
    
51.         $ref_buf = [] if (not defined $ref_buf);
    
52.         $deep = 0 if (not defined $deep);
    
53.         my (@left, @right, @others);
    
54. 
    
55.         ++$deep;
    
56.         print "\nA 第$deep次：\n";
    
57.         my $length = int(scalar(@balls) / 3 + 0.5);
    
58.         $length = 1 if ($length == 0);
    
59.         @left = @balls[0 .. $length - 1];
    
60.         @right = @balls[$length .. $length * 2 - 1];
    
61.         @others = @balls[$length * 2 .. $#balls];
    
62.         if (scalar(@balls) < 3)
    
63.         {
    
64.                 return undef if ($#{$ref_buf} == -1);
    
65.                 my $ball = shift(@$ref_buf);
    
66.                 print "取回：", &ball_show([$ball]), "\n";
    
67.                 my $ball2 = shift(@right);
    
68.                 @right = ($ball);
    
69.                 print "左边：", &ball_show(\@left), "\n";
    
70.                 print "右边：", &ball_show(\@right), "\n";
    
71.                 if (&ball_total_heavy(\@left) == &ball_total_heavy(\@right))
    
72.                 {
    
73.                         return $ball2;
    
74.                 }
    
75.                 else
    
76.                 {
    
77.                         return shift(@left);
    
78.                 }
    
79.         }
    
80. 
    
81.         print "左边：", &ball_show(\@left), "\n";
    
82.         print "右边：", &ball_show(\@right), "\n";
    
83.         print "余下：", &ball_show(\@others), "\n";
    
84.         my $heavy_left = &ball_total_heavy(\@left);
    
85.         my $heavy_right = &ball_total_heavy(\@right);
    
86.         if ($heavy_left == $heavy_right)
    
87.         {
    
88.                 push(@$ref_buf, @left);
    
89.                 push(@$ref_buf, @right);
    
90.                 &ball_find(\@others, $ref_buf, $deep);
    
91.         }
    
92.         else
    
93.         {
    
94.                 push(@$ref_buf, @others);
    
95.                 if ($heavy_left < $heavy_right)
    
96.                 {
    
97.                         &ball_find2(\@left, \@right, $ref_buf, $deep);
    
98.                 }
    
99.                 else
    
100.                 {
     
101.                         &ball_find2(\@right, \@left, $ref_buf, $deep);
     
102.                 }
     
103.         }
     
104. }
     
105. 
     
106. sub ball_find2
     
107. {
     
108.         my @balls = @{$_[0]};
     
109.         my @balls2 = @{$_[1]};
     
110.         my ($ref_buf, $deep) = ($_[2], $_[3]);
     
111.         $ref_buf = [] if (not defined $ref_buf);
     
112.         $deep = 0 if (not defined $deep);
     
113.         my (@left, @right, @others);
     
114. 
     
115.         ++$deep;
     
116.         print "\nB 第$deep次：\n";
     
117.         my $length = int((scalar(@balls) + scalar(@balls2)) / 3 + 0.5);
     
118.         if ((scalar(@balls) == 1 and scalar(@balls2) <= 2) or (scalar(@balls2) == 1 and scalar(@balls) <= 2))
     
119.         {
     
120.                 my $swp = 0;
     
121.                 if (scalar(@balls) != 1)
     
122.                 {
     
123.                         $swp = 1;
     
124.                         my @tmp = @balls;
     
125.                         @balls = @balls2;
     
126.                         @balls2 = @tmp;
     
127.                 }
     
128. 
     
129.                 if (@balls2 == 2)
     
130.                 {
     
131.                         push(@left, shift(@balls2));
     
132.                         push(@right, shift(@balls2));
     
133.                 }
     
134.                 else
     
135.                 {
     
136.                         if ($#{$ref_buf} == -1)
     
137.                         {
     
138.                                 return undef;
     
139.                         }
     
140. 
     
141.                         my $ball = shift(@$ref_buf);
     
142.                         print "取回：", &ball_show([$ball]), "\n";
     
143.                         push(@left, $ball);
     
144.                         push(@right, shift(@balls2));
     
145.                 }
     
146. 
     
147.                 print "左边：", &ball_show(\@left), "\n";
     
148.                 print "右边：", &ball_show(\@right), "\n";
     
149.                 my $heavy_left = &ball_total_heavy(\@left);
     
150.                 my $heavy_right = &ball_total_heavy(\@right);
     
151.                 if ($heavy_left == $heavy_right)
     
152.                 {
     
153.                         return shift(@balls);
     
154.                 }
     
155.                 elsif ($swp xor $heavy_left < $heavy_right)
     
156.                 {
     
157.                         return shift(@right);
     
158.                 }
     
159.                 else
     
160.                 {
     
161.                         return shift(@left);
     
162.                 }
     
163.         }
     
164.         else
     
165.         {
     
166.                 my (@a1, @a2, @a3, @b1, @b2, @b3);
     
167.                 my $n = int(scalar(@balls) / 2);
     
168.                 @a1 = @balls[0 .. $n - 1];
     
169.                 @a2 = @balls[$n .. $n * 2- 1];
     
170.                 @a3 = @balls[$n * 2 .. $#balls] if ($n * 2 <= $#balls);
     
171.                 my $n2 = $length - $n;
     
172.                 if ($n2 > 0)
     
173.                 {
     
174.                         @b1 = @balls2[0 .. $n2 - 1];
     
175.                         @b2 = @balls2[$n2 .. $n2 * 2 - 1];
     
176.                         @b3 = @balls2[$n2 * 2 .. $#balls2] if ($n2 * 2 <= $#balls2);
     
177.                 }
     
178.                 else
     
179.                 {
     
180.                         @b3 = @balls2;
     
181.                 }
     
182. 
     
183.                 @left = (@a1, @b1);
     
184.                 @right = (@a2, @b2);
     
185.                 @others = (@a3, @b3);
     
186. 
     
187.                 print "左边：", &ball_show(\@left), "\n";
     
188.                 print "右边：", &ball_show(\@right), "\n";
     
189.                 print "余下：", &ball_show(\@others), "\n";
     
190.                 my $heavy_left = &ball_total_heavy(\@left);
     
191.                 my $heavy_right = &ball_total_heavy(\@right);
     
192.                 if ($heavy_left == $heavy_right)
     
193.                 {
     
194.                         push(@$ref_buf, @left);
     
195.                         push(@$ref_buf, @right);
     
196.                         if (scalar(@a3) == 0 or scalar(@b3) == 0)
     
197.                         {
     
198.                                 my $heavy_flag = scalar(@a3) == 0 ? 1 : 0;
     
199.                                 &ball_find3(\@others, $heavy_flag, $ref_buf, $deep);
     
200.                         }
     
201.                         else
     
202.                         {
     
203.                                 &ball_find2(\@a3, \@b3, $ref_buf, $deep);
     
204.                         }
     
205.                 }
     
206.                 elsif ($heavy_left < $heavy_right)
     
207.                 {
     
208.                         push(@$ref_buf, @right);
     
209.                         push(@$ref_buf, @others);
     
210.                         if (scalar(@a1) == 0 or scalar(@b2) == 0)
     
211.                         {
     
212.                                 my $heavy_flag = scalar(@a1) == 0 ? 1 : 0;
     
213.                                 &ball_find3([@a1, @b2], $heavy_flag, $ref_buf, $deep);
     
214.                         }
     
215.                         else
     
216.                         {
     
217.                                 &ball_find2(\@a1, \@b2, $ref_buf, $deep);
     
218.                         }
     
219.                 }
     
220.                 else
     
221.                 {
     
222.                         push(@$ref_buf, @left);
     
223.                         push(@$ref_buf, @others);
     
224.                         if (scalar(@a2) == 0 or scalar(@b1) == 0)
     
225.                         {
     
226.                                 my $heavy_flag = scalar(@a2) == 0 ? 1 : 0;
     
227.                                 &ball_find3([@a2, @b1], $heavy_flag, $ref_buf, $deep);
     
228.                         }
     
229.                         else
     
230.                         {
     
231.                                 &ball_find2(\@a2, \@b1, $ref_buf, $deep);
     
232.                         }
     
233.                 }
     
234.         }
     
235. }
     
236. 
     
237. sub ball_find3
     
238. {
     
239.         my @balls = @{$_[0]};
     
240.         my ($heavy_flag, $ref_buf, $deep) = ($_[1], $_[2], $_[3]);
     
241.         $ref_buf = [] if (not defined $ref_buf);
     
242.         $deep = 0 if (not defined $deep);
     
243.         my (@left, @right, @others);
     
244. 
     
245.         return shift(@balls) if (scalar(@balls) == 1);
     
246. 
     
247.         ++$deep;
     
248.         print "\nC 第$deep次：\n";
     
249.         my $length = int(scalar(@balls) / 2);
     
250.         @left = @balls[0 .. $length - 1];
     
251.         @right = @balls[$length .. $length * 2 - 1];
     
252.         print "左边：", &ball_show(\@left), "\n";
     
253.         print "右边：", &ball_show(\@right), "\n";
     
254.         if ($length * 2 <= $#balls)
     
255.         {
     
256.                 @others = @balls[$length * 2 .. $#balls];
     
257.                 print "余下：", &ball_show(\@others), "\n";
     
258.         }
     
259. 
     
260.         my $heavy_left = &ball_total_heavy(\@left);
     
261.         my $heavy_right = &ball_total_heavy(\@right);
     
262.         if ($heavy_left == $heavy_right)
     
263.         {
     
264.                 return shift(@others) if (scalar(@others) == 1);
     
265.                 push(@$ref_buf, @left);
     
266.                 push(@$ref_buf, @right);
     
267.                 &ball_find3(\@others, $heavy_flag, $ref_buf, $deep);
     
268.         }
     
269.         else
     
270.         {
     
271.                 my @balls;
     
272.                 if ($heavy_flag xor $heavy_left < $heavy_right)
     
273.                 {
     
274.                         return shift(@left) if (scalar(@left) == 1);
     
275.                         @balls = @left;
     
276.                         push(@$ref_buf, @right);
     
277.                         push(@$ref_buf, @others);
     
278.                 }
     
279.                 else
     
280.                 {
     
281.                         return shift(@right) if (scalar(@right) == 1);
     
282.                         @balls = @right;
     
283.                         push(@$ref_buf, @left);
     
284.                         push(@$ref_buf, @others);
     
285.                 }
     
286. 
     
287.                 &ball_find3(\@balls, $heavy_flag, $ref_buf, $deep);
     
288.         }
     
289. }
     
290. 
     
291. sub ball_total_heavy
     
292. {
     
293.         my $heavy = 0;
     
294.         foreach my $ball (@{$_[0]})
     
295.         {
     
296.                 $heavy += $ball->[1];
     
297.         }
     
298. 
     
299.         return $heavy;
     
300. }
     
301. 
     
302. sub ball_show
     
303. {
     
304.         my $string = "";
     
305.         foreach my $ball (@{$_[0]})
     
306.         {
     
307.                 my ($id, $heavy) = @$ball;
     
308.                 $string .= "[$id,$heavy] ";
     
309.         }
     
310. 
     
311.         $string =~ s/\s+$//;
     
312.         return $string;
     
313. }
     
314. 
     
315. sub ball_success
     
316. {
     
317.         my ($id, $heavy) = @{$_[0]};
     
318.         print "\n缺陷球为：[$id,$heavy]\n";
     
319. }
     
320. 
     
321. sub ball_fail
     
322. {
     
323.         print "\n无解\n";
     
324. }
     

复制代码

CrkED

呵呵，刚好是俺上学期算法分析课的作业。最有效率的方法是用决策树模型。每个比较操作可能得到3种结果，所以这里的决策树是个三叉树。由于不知道是轻还是重，所以决策树可能的叶子节点一共有2*n个，所以lower bound=log3(2*n)。n=12的时候就是2.89<3。
ps1: 如果知道轻重，则可能的节点只有n个，此时lower bound=log3(n)。
ps2: 如果连是否存在与众不同的球都不知道，则lower bound=log3(2*n+1)。
ps3: 关于如何生成决策树，如c4.5算法，请自行google。