锁具装箱问题

锁具装箱问题学习目标1. 能表述锁具装箱问题的分析过程；2. 能表述模型的建立方法；3. 会利用排列组合来计算古典概型；4. 会利用Matlab求解锁具装箱问题。一、 问题 某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从1，2，3，4，5，66个数（单位从略）中任取一数。由于工艺及其它原因，制造锁具时对5个槽的高度有两个要求：一是至少有3个不同的数；二是相邻两槽的高度之差不能为5。满足上述两个条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地抽取，每60个装一箱出售。 从顾客的利益出发，自然希望在每批锁具中不能互开（“一把钥匙开一把锁”）。但是，在当前工艺条件下，对于同一批中两个锁具是否能够互开，有以下实验结果：若二者相对应的5个槽的高度中有4个相同，另一个槽的高度差为1，则可能互开；在其它情况下，不可能互开。 团体顾客往往购买几箱到几十箱，他们会抱怨购得的锁具中出现互开的情形。现请回答以下问题：1 每批锁具有多少个，能装多少箱？2 按照原来的装箱方案，如何定量地衡量团体顾客抱怨互开的程度（试对购买一、二箱者给出具体结果）。二、 问题分析与建立模型因为弹子锁具的钥匙有5个槽，每个槽的高度从1，2，3，4，5，6这6个数中任取一数，且5个槽的高度必须满足两个条件：至少有3个不同的数；相邻两槽的高度之差不能为5。所以我们在求一批锁具的总数时，应把问题化为三种情况，即5个槽的高度由5个不同数字组成、由4个不同数字组成、由3个不同数字组成，分别算出各种情况的锁具个数，然后相加便得到一批锁具的总个数。在分别求这三种情况锁具个数的时候，先求出满足第1个条件的锁具个数再减去不满足第2个条件的锁具个数。在求这三种情况锁具个数的时候，主要依靠排列组合的不尽相异元素的全排列公式。下面用一个5元数组来表示一个锁具： Key=（h1，h2，h3，h4，h5） 其中hi表示第i个槽的高度，i=1，2，3，4，5。此5元数组表示一把锁，应满足下述条件： 条件1： hi1，2，3，4，5，6，i = 1，2，3，4，5。 条件2：对于任意一种槽高排列h1，h2，h3，h4，h5，至少有3种不同的槽高。 条件3：对于任意一种槽高排列h1，h2，h3，h4，h5，有| hi，hi-1|5，i = 2，3，4，5。 而两个锁可以互开的条件为：两个锁的钥匙有四个槽高相同，其中一个槽高相差为1。1 一批锁具个数的计算 记一批锁具的集合为： K=（h1，h2，h3，h4，h5）| hi1，2，3，4，5，6，i = 1，2，3，4，5，且（h1，h2，h3，h4，h5）为一锁具，其个数小于65，可采用逐个检验条件1，2，3的方法，求一批中的所有锁具，当然也可计算出其个数。2 抱怨程度的刻划 在这里我们简单地用平均互开总对数来刻划抱怨程度，所以，关键是计算出顾客购买一箱或两箱时的平均互开总对数，这可以用计算机模拟去计算。 我们引入下面的记号： P=（h1，h2，h3，h4，h5）|（h1，h2，h3，h4，h5）K，且为偶数 Q=（h1，h2，h3，h4，h5）|（h1，h2，h3，h4，h5）K，且为奇数 则可得到P中的锁具不能互开，Q中的锁具不能互开，P中的锁具与Q中的才能互开。 在计算中，判断互开时，我们将P和Q中的锁具分别标号为0，1，这样就减少了判断时的计算，大大提高了计算速度。 说明：直接用平均互开总对数来刻划抱怨程度有一定的不合理性。因为这样来刻划，购买的箱数越多，抱怨程度就越大，而实际上，购买的越多，自然互开的可能性就越大，这是顾客意料之中的，不应有太多的抱怨，顾客所不能容忍的是在购买少量的锁具而出现互开现象。因此应把购买箱数作为一个因素考虑到抱怨函数中。理想的抱怨函数应该是，开始随购买量的增加而增加，到一定量后下降，这才合理。在这里，我们的主要任务是模拟求解，而简单地用平均互开总对数来刻划抱怨程度。三、 计算过程 计算流程如下：1 对（h1，h2，h3，h4，h5）的所有排列逐个检验条件2、条件3，判断其是否为锁具，将锁具放在数组key中，若为奇数，标号为1，若为偶数，标号为0，并计数count。2 输出一批锁具的总个数count。3 多次用随机数来模拟销售一箱的情况，计算平均互开总对数。4 输出一箱平均互开总对数average。 注意：以上流程略去了某些细节，具体的细节可参看下面的程序。对上流程稍加修改，可用于研究2，3，4箱等的平均互开总对数。程序对（h1，h2，h3，h4，h5）的所有排列逐个检验条件2、条件3时要进行两次判断，一次是判断（h1，h2，h3，h4，h5）是否有3个不同的数，另一次是相邻槽高之差是否为5。在前一次判断时，采用了比较简捷的方法，请仔细考察。 找（h1，h2，h3，h4，h5）的所有排列，实际上可用五重循环来实现。具体程序如下：Modelh1，h2，h3，h4，h5，flag，cnt，key，flal，su，te，keel，i，aid， mnx，kebe，k，j，n， （*计算一批锁具的个数*）key=TableTable0，5，5880；keel=Table0，5；flag=Table-1，5880；cnt=0；Forh1=1，h1=6，h1+， Forh2=1，h2=6，h2+， Forh3=1，h3=6，h3+， Forh4=1，h4=6，h4+， Forh5=1，h5=3，keel1=h1；keel2=h2；keel3=h3； Forflal=1；i=2，i=5，flal=0，； Ifflal= =1，cnt+；keycnt=keel； flagcnt=IfModkeel.Table1，5，2= =0，0，1； ， ； Print“count=”，cnt； （*计算顾客购买一箱时的平均互开总对数*）cnt=0；aid=Table1，5；kebe=Table0，5；Forn=1，n=1000，n+， （*模拟1000次*）Mnx=TableRndomInteger，1，5880，60； Fori=1，i=60，i+， Fork=i+11，k=60，k+， Ifflagmnxi! =flagmnxk ，IfAbskeymnxi.aid-keymnxk.aid= =1， Keel=keymnxI；kebe=keymnxk； Forflal=0；j=1，j=5，j+，Ifkeelj!=kebej，flal+，； Ifflal= =1，cnt+，； Print“Average=”，Ncnt/10