砝码分盐问题——从数学和计算机的角度分析(2)

晨曦之光 发布于 2012/03/09 14:16
阅读 84
收藏 0

本博客(http://blog.csdn.net/livelylittlefish )贴出作者(阿波)相关研究、学习内容所做的笔记,欢迎广大朋友指正!

 

 

Content

0. 问题

1. 一些方法

2. 从数学的角度分析

2.1 砝码组合状态

2.2 数学解法

2.2.1 限制规则

2.2.2 隐含的限制规则

2.2.3 规则小结

2.3 称量过程

2.4 正确的称量过程

2.5 一个疑问

3. 能否编程计算?

4. 一个改进的方法

5. 再改进的方法

6. 能否直接计算求出所有正确解?

7. 一个更为简单的方法

8. 所有代码的自动编译、运行

9. 问题扩展

10. 体会

11. 总结

Reference

附录 1 :数学分解的代码 weight1.c

附录 2 :数学分解程序 weight1 的运行结果

附录 3 :树结构分解的代码 weight2.c

附录 4 :再改进的方法的代码 weight3.1.c/3.2.c/3.3.c

附录 5 :再改进的方法的代码 weight3.1.c/3.2.c/3.3.c 的输出结果

附录 6 :直接计算正确分解的代码 weight4.c

附录 7 :一个更简单的方法的代码 weight5.1.c/5.2.c/5.3.c

 

2. 从数学的角度分析

 

从上面的方法可以看出,对于去除法和累加法,因其去除或者累加情况较多,组合的值也较多,不易确定分析。

 

但分解应该可以确定,因为分解主要是要利用已有的砝码对盐进行分堆,分堆的个数也容易确定,一定为 4 堆,因为 3 次称量,每次对其中一堆进行再分堆,且每次只能分成 2 堆。且分堆时用到的砝码重量也是确定的 ( 详见后续的分析 ) ,故分解方法的解的个数也一定是确定的。

 

本节即从数学的角度分析采用分解方法 的情况下正确的称量过程及正确的解的个数。

 

2.1 砝码组合状态

 

砝码的组合有两种情况。

 

(1) 出现在天平同一侧

 

14g 砝码

4g 砝码

组合结果

1

4g

1

14g

1

1

18g

 

表示不出现, 1 表示出现。实际上,对于两个砝码均不出现的情况,其动作即为等分盐。

 

(2) 出现在天平两侧

 

出现在天平两侧,不论位置,所代表的砝码质量均为 10g

 

综上,砝码组合共有 4g 10g 14g 18g ,共 5 中状态。

 

(3) 讨论

 

如果将以上 (1) (2) 两种情况综合在一起,也可以,只是需要重新定义。

  • :砝码不出现
  • 1 :砝码出现在天平同一侧
  • -1 :砝码出现在天平两侧 ( 每侧各一个 )

 

14g 砝码

4g 砝码

组合结果

1

4g

1

14g

1

1

18g

1/-1

-1/1

10g

 

可参考 " 砝码称重问题 " 一文,但要注意其间的区别。

 

2.2 数学解法

 

2.2.1 限制规则

 

(1) 第一次称量

 

设盐的重量为 z ,用重量为 w 的砝码称量,被分为重量为 x y( 假设 x<=y) 的盐,则 x y z w 满足如下等式。

y + x = z

y - x = w

 

(2) 第二次称量

 

第二次要对重量为 x 或者 y 的盐进行称量分解。共 2 种情况。

 

若对 x 进行称量,被分为 x1 x2( 假设 x1<=x2) ,则满足如下等式。

x2 + x1 = x

x2 - x1 = w

 

若对 y 进行称量,被分为 y1 y2( 假设 y1<=y2) ,则满足如下等式。

y1 + y2 = y

y2 - y1 = w

 

(3) 第三次称量

 

第三次要对重量为 x1 或者 x2 或者 y1 或者 y2 的盐进行称量分解。共 4 中情况。

 

(3.1) 分解 x1

 

若对 x1 进行称量,被分为 x11 x12( 假设 x11<=x12) ,则满足如下等式。

x12 + x11 = x1

x12 - x11 = w

 

至此, 3 次称量后,盐被分为重量为 x11 x12 x2 y 4 堆盐。

 

(3.2) 分解 x2

 

若对 x2 进行称量,被分为 x21 x22( 假设 x21<=x22) ,则满足如下等式。

x22 + x21 = x2

x22 - x21 = w

 

至此, 3 次称量后,盐被分为重量为 x1 x21 x22 y 4 堆盐。

 

(3.3) 分解 y1

 

若对 y1 进行称量,被分为 y11 y12( 假设 y11<=y12) ,则满足如下等式。

y12 + y11 = y1

y12 - y11 = w

 

至此, 3 次称量后,盐被分为重量为 x y11 y12 y2 4 堆盐。

 

(3.4) 分解 y2

 

若对 y2 进行称量,被分为 y21 y22( 假设 x21<=x22) ,则满足如下等式。

y22 + y21 = y2

y22 - y21 = w

 

至此, 3 次称量后,盐被分为重量为 x y1 y21 y22 4 堆盐。

 

2.2.2 隐含的限制规则

 

对于本题,根据 2.2.1 节的讨论,可知

 

(1) z=280g ,砝码 w 可取 4g 10g 14g 18g 。注意:这些值是砝码组合之后的值。

 

(2) 所有的变量均为整数。

 

(3) 因为 w 为偶数, x2-x1=w => x1 x2 同为奇数或者同为偶数。

x2 + x1 = x ,故 x 一定为偶数 ( 不论 x1 x2 同为奇数还是同为偶数 )

同样的道理,可知, y x1 x2 y1 y2 也一定为偶数。

 

(4) 根据 2.2.1(3) 对第三次称量的讨论,例如, (3.1) 分解 x1 ,盐被分为重量为 x11 x12 x2 y 4 堆盐,显然,题目要求的 100g 盐和 180g 盐要在这 4 堆盐中组合产生,且已知 x2 y 为偶数,故, x11 x12 也一定为偶数。

同样的道理,可知,对于其他对 x2 y1 y2 的分解, x21 x22 y11 y12 y21 y22 也一定为偶数。

 

2.2.3 规则小结

 

综上,由 w z 为偶数,可知, 3 次分解出的所有重量 x,y,x1(x11,x12),x2(x21,x22),y1(y11,y12),y2(y21,y22) 全都为偶数。——这便是本题隐含的限制规则。

 

分解可以记为: z(x(x1(x11,x12),x2(x21,x22)),y(y1(y11,y12),y2(y21,y22)))

其中对 x1,x2,y1,y2 的分解是或关系。因此,该记法明确表示只有 3 次称量。

 

2.3 称量过程

 

根据 2.2 节的讨论,称量过程就很好写出来了。以下 T 表示该次分解正确, F 表示错误。 10g 砝码表示此次分解用到的是 10g 砝码,其余类同。

 

(1) 第一次称量

 

280 = 140 + 140 (0g 砝码 , T)

280 = 138 + 142 (4g 砝码 , T)

280 = 135 + 145 (10g 砝码, F)

280 = 133 + 147 (14g 砝码, F)

280 = 131 + 149 (18g 砝码, F)

 

(2) 第二次称量

 

140 分解:

140 = 70 + 70 (0g 砝码 , T)

140 = 68 + 72 (4g 砝码 , T)

140 = 65 + 75 (10g 砝码 , F)

140 = 63 + 77 (14g 砝码 , F)

140 = 61 + 79 (18g 砝码 , F)

 

138 分解:

138 = 69 + 69 (0g 砝码 , F)

138 = 67 + 71 (4g 砝码 , F)

138 = 64 + 74 (10g 砝码, T)

138 = 62 + 76 (14g 砝码, T)

138 = 60 + 78 (18g 砝码, T)

 

142 分解:

142 = 71 + 71 (0g 砝码 , F)

142 = 69 + 73 (4g 砝码 , F)

142 = 66 + 76 (10g 砝码 , T)

142 = 64 + 78 (14g 砝码 , T)

142 = 62 + 80 (18g 砝码 , T)

 

(3) 第三次称量

 

过程如下,蓝色表示正确的分解。

 

第一次称量

第二次称量

第三次称量

280 = 140 + 140

(0g 砝码 , T)

140 = 70 + 70

(0g 砝码 , T)

分解 70

70 = 35 + 35 (0g 砝码 , F)

70 = 33 + 37 (4g 砝码 , F)

70 = 30 + 40 (10g 砝码 , T) => 30,40,70,140 => T

70 = 28 + 42 (14g 砝码 , T) => 28,42,70,140 => F

70 = 26 + 44 (18g 砝码 , T) => 26,44,70,140 => F

 

140 = 68 + 72

(4g 砝码 , T)

分解 68

68 = 34 + 34 (0g 砝码 , T) => 34,34,72,140 => F

68 = 32 + 36 (4g 砝码 , T) => 32,36,72,140 => F

68 = 29 + 39 (10g 砝码 , F)

68 = 27 + 41 (14g 砝码 , F)

68 = 25 + 43 (18g 砝码 , F)

 

分解 72

72 = 36 + 36 (0g 砝码 , T) => 68,36,36,140 => F

72 = 34 + 38 (4g 砝码 , T) => 68,34,38,140 => F

72 = 31 + 41 (10g 砝码 , F)

72 = 29 + 43 (14g 砝码 , F)

72 = 27 + 45 (18g 砝码 , F)

280 = 138 + 142

(4g 砝码 , T)

138 = 64 + 74

(10g 砝码, T)

分解 64

64 = 32 + 32 (0g 砝码 , T) => 32,32,74,142 => F

64 = 30 + 34 (4g 砝码 , T) => 30,34,74,142 => F

64 = 27 + 37 (10g 砝码 , F)

64 = 25 + 39 (14g 砝码 , F)

64 = 23 + 41 (18g 砝码 , F)

 

分解 74

74 = 37 + 37 (0g 砝码 , F)

74 = 35 + 39 (4g 砝码 , F)

74 = 32 + 42 (10g 砝码 , T) => 64,32,42,142 => F

74 = 30 + 44 (14g 砝码 , T) => 64,30,44,142 => F

74 = 28 + 46 (18g 砝码 , T) => 64,28,46,142 => F

 

138 = 62 + 76

(14g 砝码, T)

分解 62

62 = 31 + 31 (0g 砝码 , F)

62 = 29 + 33 (4g 砝码 , F)

62 = 26 + 36 (10g 砝码 , T) => 26,36,76,142 => F

62 = 24 + 38 (14g 砝码 , T) => 24,38,76,142 => T

62 = 22 + 40 (18g 砝码 , T) => 26,36,76,142 => F

 

分解 76

76 = 38 + 38 (0g 砝码 , T) => 62,38,38,142 => T

76 = 36 + 40 (4g 砝码 , T) => 62,36,40,142 => F

76 = 33 + 43 (10g 砝码 , F)

76 = 31 + 45 (14g 砝码 , F)

76 = 29 + 47 (18g 砝码 , F)

 

138 = 60 + 78

(18g 砝码, T)

分解 60

60 = 30 + 30 (0g 砝码 , T) => 30,30,78,142 => F

60 = 28 + 32 (4g 砝码 , T) => 28,32,78,142 => F

60 = 25 + 35 (10g 砝码 , F)

60 = 23 + 37 (14g 砝码 , F)

60 = 21 + 49 (18g 砝码 , F)

 

分解 78

78 = 39 + 39 (0g 砝码 , F)

78 = 37 + 41 (4g 砝码 , F)

78 = 34 + 44 (10g 砝码 , T) => 60,34,44,142 => F

78 = 32 + 46 (14g 砝码 , T) => 60,32,46,142 => F

78 = 30 + 48 (18g 砝码 , T) => 60,30,48,142 => F

 

142 = 66 + 76

(10g 砝码 , T)

分解 66

66 = 33 + 33 (0g 砝码 , F)

66 = 31 + 35 (4g 砝码 , F)

66 = 28 + 38 (10g 砝码 , T) => 138,28,38,76 => F

66 = 26 + 40 (14g 砝码 , T) => 138,26,40,76 => F

66 = 24 + 42 (18g 砝码 , T) => 138,24,42,76 => T

 

分解 76

76 = 38 + 38 (0g 砝码 , T) => 138,66,38,38 => F

76 = 36 + 40 (4g 砝码 , T) => 138,66,36,40 => F

76 = 33 + 43 (10g 砝码 , F)

76 = 31 + 45 (14g 砝码 , F)

76 = 29 + 47 (18g 砝码 , F)

 

142 = 64 + 78

(14g 砝码 , T)

分解 64

64 = 32 + 32 (0g 砝码 , T) => 138,32,32,78 => F

64 = 30 + 34 (4g 砝码 , T) => 138,30,34,78 => F

64 = 27 + 37 (10g 砝码 , F)

64 = 25 + 39 (14g 砝码 , F)

64 = 23 + 41 (18g 砝码 , F)

 

分解 76

78 = 39 + 39 (0g 砝码 , F)

78 = 37 + 41 (4g 砝码 , F)

78 = 34 + 44 (10g 砝码 , T) => 138,64,34,44 => F

78 = 32 + 46 (14g 砝码 , T) => 138,64,32,46 => F

78 = 30 + 48 (18g 砝码 , T) => 138,64,30,48 => F

 

142 = 62 + 80

(18g 砝码 , T)

分解 62

62 = 31 + 31 (0g 砝码 , F)

62 = 29 + 33 (4g 砝码 , F)

62 = 26 + 36 (10g 砝码 , T) => 138,26,36,80 => F

62 = 24 + 38 (14g 砝码 , T) => 138,24,38,80 => F

62 = 22 + 40 (18g 砝码 , T) => 138,22,40,80 => F

 

分解 80

80 = 40 + 40 (0g 砝码 , T) => 138,62,40,40 => F

80 = 38 + 42 (4g 砝码 , T) => 138,62,38,42 => T

80 = 35 + 45 (10g 砝码 , F)

80 = 33 + 47 (14g 砝码 , F)

80 = 31 + 49 (18g 砝码 , F)

 

2.4 正确的称量过程

 

综上,正确的称量 ( 分解 ) 过程如下。

No.

第一次称量

第二次称量

第三次称量

1

280 = 140 + 140 (0g 砝码 )

140 = 70 + 70 (0g 砝码 )

70 = 30 + 40 (10g 砝码 )=>30,40,70,140

2

280 = 138 + 142 (4g 砝码 )

138 = 62 + 76 (14g 砝码 )

62 = 24 + 38 (14g 砝码 )=>24,38,76,142

3

280 = 138 + 142 (4g 砝码 )

138 = 62 + 76 (14g 砝码 )

76 = 38 + 38 (0g 砝码 ) =>62,38,38,142

4

280 = 138 + 142 (4g 砝码 )

142 = 66 + 76 (10g 砝码 )

66 = 24 + 42 (18g 砝码 )=>138,24,42,76

5

280 = 138 + 142 (4g 砝码 )

142 = 62 + 80 (18g 砝码 )

80 = 38 + 42 (4g 砝码 ) =>138,62,38,42

 

至此,通过分解的方法,已经得到了全部的解,共 5 个。

 

2.5 一个疑问

 

或许细心的读者已经发现一个疑问。

 

如果第二次称量时分解的是 x( 分成 x1 x2) ,为什么第三次称量不分解 y( 分成 y1 y2)

或者如果第二次称量时分解的是 y ,为什么第三次称量不分解 x ?即称量过程如下。

 

第一次称量: z = x + y

第二次称量: x = x1 + x2 ( y = y1 + y2)

第三次称量: y = y1 + y2 ( x = x1 + x2)

以上假设 x1 <= x2 , y1 <= y2

 

这是可以证明的,下面给出证明过程。

 

证明: 假设按如上过程称量。

 

设第二、三次称量使用的砝码重量分别为 w1 w2 ,根据上述分析,可知, w1,w2 属于{0, 4, 10, 14, 18} ,因此,

<= W1+w2 <= 36 ,且 -18  <= w1-w2 <= 18 或者 -18  <= w1-w2  <= 18 。另有,

 

x2 -x1 = w1

y2 -y1 = w2

 

设最后分成的两堆盐为 z1=100 z2=180

 

(1)

x1 + y1 = z1

x2 + y2 = z2

可得, (x2+x1)-(y2+y1)=w1+w2=80 ,显然矛盾。

 

(2)

x1 + y2 = z1

x2 + y1 = z2

可得, (x2-x1)+(y1-y2)=w1-w2=80 ,显然矛盾。

 

(3)

x2 + y1 = z1

x1 + y2 = z2

可得, (x1-x2)+(y2-y1)=w2-w1=80 ,显然矛盾。

 

(4)

x2 + y2 = z1

x1 + y1 = z2

可得, (x2-x1)+(y2-y1)=w1+w2=-80 ,显然矛盾。

 

综上,假设不成立,即不能按如上过程进行称量。

至此,也从侧面证明 2.3 节的称量分解过程是完全的。


上一节 下一节

 


原文链接:http://blog.csdn.net/livelylittlefish/article/details/6555360
加载中
返回顶部
顶部