文档介绍：锁具数目和最大匹配问题

班级: 信计92
姓名: 雍宏巍
学号: 09092049

摘要
本文主要讨论了锁具装箱问题中n个槽m个高度时锁具的个数和槽高和为奇数和偶数两类锁之间的最大匹配问题。对于前者主要利用matlab编程,结合m进制数的思想和判断条件,得到了任意给定一组n和m均可以根据程序求出锁具的个数的结果。特别的对于4个槽5个高度求出一共有114中锁具。对于第二个问题,同样采用计算机编程的方法来做,采用邻接矩阵存储,利用matlab结合Edmonds算法和大基数基匹配矩阵的算法,求得最大匹配,通过建立每种锁具和平面上点的一一对应关系,将最后结果以附图形式给出。方法科学,结果理想。
问题叙述
某厂生产一种弹子锁具,每个锁具有n个槽,每个槽有m个高度,每个槽的高度从{1,2,…,m}这m个数(单位略)中任取一个,限制至少有一个相邻的槽高之差等于m-1,且至少有3个不同的槽高。每个槽的高度取遍这m个数且满足上面这两个限制时生产出一批锁。求一批锁的把数。
对于同一批中两个锁具是否能够互开,有以下试验结果:若二者相对应的 n个槽的高度中有 n-1个相同,另一个槽的高度差为1,则能互开,在其它情形下不可能互开。将这一批锁按槽高数之和分为奇数(A)和偶数(B)两类。请给出这两类锁之间的最大匹配。主要考虑 4个槽,5个高度的情况

问题分析
该问题主要分为两个部分,第一部分为符合条件的一批所的把数,第二部分为图论内容,求最大匹配。第一部分可以采用枚举法,利用计算机编程来解决,而且很容易实现。第二部分,首先要将图存成邻接矩阵,然后图论中的一些算法,例如Edmonds算法来解决。由于所涉及的锁具数目较多,结果不能以数据显示,太占篇幅,最好以图的形式展示。

求解一批锁具的数量有多种方法,比如排列组合法,递推法,图论方法等。但这里的n和m未知时这些方法往往比较复杂,需要较多的思考。这里我们采用计算机求解锁具数目的方法。基本思路为穷举法。对于所有可能的槽高组合进行一一验证,符合条件的槽高组合记录下来并计数。
首先要解决的是循环问题,若对每一个槽的槽高进行循环,则要采用n个for循环,由于n的数目未定,便无法实现。但是可以确定的是所有可能的槽高组合一共有种组合,我们能否只用一个for循环来实现呢?答案是可以的,采用m进制数的换算思想便可以实现。
我们可以让整数b在1到之间取值。将b转换为m进制数,将其每个数位上的数字提取出来。每个数字加1便是槽高的一个组合。

对0到之间给定的一个整数b,
其第一位数字;第二位数为,第三位数;……对于第i位数;
这样的话我们就可以将b所对应的m进制数的每一位数提取出来,对每一个数加一,以n维向量a来存储。这样的话便可以用一个for循环来实现穷举。

依据题目有满足要求的槽高需具备两个条件:一是有三个不同的槽高,二是、有相邻高差为m-1的情况。
,要有三个高度的槽。也就是说所有槽高除了槽高的最大值和最小值以外还应有其他取值。即除了max(a)和min(a)以外还应有其他值。以表示的第i个分量,若为max(a)或min(a),那么必然为零。若不为max(a)或min(a),则大于零。这样只需存在一个i,使得大于零即可,等价于所有i对应的之和大于零。这边可作为第一个判断条件。
-1的情况,可先求所以相邻槽的高度差的绝对值,让其最大值等于m-1即。
以s来计数,矩阵A来存储符合条件的槽高组合。
程序如下
function [s,A]=suoju(n,m)
A=[];s=0;
for b=0:(m^n-1)
ss=0;bb=0;a=[];
for i=1:n
bb=fix((b-ss)/m^(n-i));
a=[a,bb];
ss=ss+bb*m^(n-i);
end
for i=1:n
a(i)=a(i)+1;
end
amax=max(a); amin=min(a);
numbers=0;
for i=1:n
number(i)=(amax-a(i))*(a(i)-amin);
numbers=numbers+number(i);
end
for i=1:(n-1)
ab(i)=abs(a(i)-a(i+1));
end

neighbors=max(ab);
if numbers>
if neighbors>m-
s=s+1;
A=[A,a'];