算法设计例题2
(2012-11-22 22:56:16)
标签:
杂谈 |
分类: c语言 |
有10箱产品每箱有1000件,正品每件100 克。其中的几箱是次品,次品每件比正品轻10
克,问能否用秤只称一次,就找出哪几箱是次品。
问题分析:
1) 假设只有一箱是次品:先将箱子编码1,2,3,
4……10。再从1号箱取1件产品,2号箱取2件产品,3号箱取3件产品……10号箱取10件产品,称它们的重量,
若比标准重量轻10克则1号箱为次品;比标准重量轻20 克,则2号箱为次品;比标准重量轻30克,则3号箱为次
品;……比标准重量轻100克,则10号箱为次品。
设取出产品重量为w,则次品的箱号为((1+2+3+……+10) *100-w)/10。
2) 若不止一箱次品时,以上的方法就行不通了。但以上方法的基本思想还是可利用的,即根据取出每箱产品数量的差异,和取出产
品的总重量与标准重量误差,来分析推算次品的箱号。
数字化过程:先将箱子编码1,2,3,4……10。用枚举方法分析问题,由小到大讨论:
从“1”号箱取1件产品,若最后总重量比标准重量轻10克,则1号箱为次品;
从“2”号箱取2件产品,若最后总重量比标准重量轻20克,则2号箱为次品;
从“3”号箱若取3件产品,若最后总重量比标准重量轻30克,无法识别哪些箱是次品。但从3号箱取4件产品,若最后总重量比标准重量轻40克,肯定3号箱为次品;
再看“4”号箱,
①取5件产品,若最后总重量比标准重量轻50克,无法识别哪些是次品:可能是1、3号箱(分别取1件、4件)或5号箱为次品。
② 取6件产品,若最后总重量比标准重量轻60克,无法识别 哪些是次品:可能是2、3号箱(分别取2件、4件)或5号箱为次 品。
③ 取7件产品,若最后总重量比标准重量轻70克,也无法识别 哪些是次品:可能是1、2、3号箱(分别取1件、2件、4件)或
5号箱为次品。
④ 取8件产品,则最后总重量比标准重量轻80克,则可以肯定
4号箱为次品;无需继续枚举就可看出:1,2,3,4……10号箱取产品的件数分别为20,21,22,23,24,25,26,27,
28,29,即1,2,4,8,16,32,64,128,256,512件。
3)根据以上方法,取出产品称量后:
轻10克1号箱为次品。
轻20克2号箱为次品。
轻30克1、2号箱为次品。
轻40克3号箱为次品。
轻50克1、3号箱为次品。
轻60克2、3号箱为次品。
轻70克1、2、3号箱为次品。
轻80克4号箱为次品。
轻90克1、4号箱为次品。
…………
算法设计:用算式或算法来识别误差与次品箱号.首先是计算标准总重量,存储在变量w1中。输入称取的总重量,存储在变量w2中。然后计算出比标准重量轻多少,仍存储在变量w1中。
1)当w/10=2k 时,则k+1号箱为唯一的一箱次品。
2)当w/10>2k k取最大时记为k1,k1+1号箱为的次品箱;
继续讨论w/10-2 k1 >2 k k取最大时记为k2,k2+1号箱为的次品箱;
…………
直到取等号w/10-2 ki-1 =2 ki ,ki+1号箱为的次品箱;结束。
#include
void main( )
{
}