数学研发论坛

 找回密码
 欢迎注册
查看: 325|回复: 8

[提问] 砝码题

[复制链接]
发表于 2019-7-25 09:40:55 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
有一架天平和101个总重量为200克的砝码,砝码的重量都是整数克,但具体数值不详。
请设计一种方法,把所有砝码分置天平的两端而使天平平衡,并说明该方法的可行性。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-25 18:44:34 | 显示全部楼层
这个可以请 @Mathematica坛友来穷举。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-26 09:10:35 | 显示全部楼层
从重到轻贪心法放置即可
i)最重的砝码先放任意一侧
ii)反复将当前最重的砝码放置天平总重量较轻的一侧,直到所有砝码放置完毕。

以下说明这种方法必然最后会导致天平两侧平衡。
由抽屉原理可知至少有 2 个 1 克的砝码。
所以假如最后不平衡(两侧至少相差 2 克),那么说明
最后在天平左侧连续放置了 u 个共 a 克砝码,但是左侧比右侧仍然轻至少 2 克以上
假设此前在天平右侧最后一次放置了 1 个 b 克的砝码,  则

$a>=u,b>=a+2>=u+2$

即最后$u$个砝码至少$u$克, 而之前$101-u$个砝码都不轻于$u+2$克,故

$u+(101-u)(u+2)<=200$   →   $u(u-100)>=2$    →  $ u<0$ 或 $u>=101$

这不可能。所以天平两边必然会平衡。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-26 21:36:38 来自手机 | 显示全部楼层
没注意题目中有砝码重量不详,如果这样,我们认为就可以是先比较所有砝码之间轻重关系即可。于是每次可以只比较两个砝码重量,给它们排好序。接下去就可以用贪心法了

点评

特意强调简洁明了和通俗性,是因为它很可能是一道面试题,为了让更多人去理解  发表于 2019-7-27 12:15
还是一样的点评:在能把1克的砝码和大于1克的砝码区分开来的情况下,说明可行性是否就能更简洁明了些了,因为这题,每个砝码的克数都是能获知的。  发表于 2019-7-27 00:53
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-7-27 06:51:15 | 显示全部楼层
所谓不详,我理解为在制定方案前,丢番图方程\[g_1+g_2+...+g_{101}=200\]的解不明,具体的重量配置可能是方程解集中的任何一个。所以我们制定的方案应对解集中任意一个特定的解都可行。当具体实施时,我们面临的是一个特定解,各重量是已知的。
2楼的贪心算法就是一个这样的方案。事实上,该方案并不需要具体的重量值,只需要按重量的排序即可。

点评

你就别来瞎参和  发表于 2019-7-27 08:08
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-18 08:29 , Processed in 0.053295 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表