[详细完整版]计算机鼓轮.doc

计算机鼓轮 假设一个旋转鼓的表面被等分为16个部分，如图14- 1所示，其中每一部分分别由导体或绝缘体构成，图中阴影部分表示导体，空白部分表示 绝缘体，导体部分给出信号1，绝缘体部分给出信号0。根据鼓轮转动时所处的位置，四 个触头A、B、C、D将获得一定的信息。因此，鼓轮的位置可用二进制信号表示。试问如 何选取鼓轮16个部分的材料才能使鼓轮每转过一个部分得到一个不同的二进制信号，即 每转一周，能得到0000到1111的16个数。 这个问题也可表示为：把16个二进制数排成一个圆圈，使得四个依次相连的数字所组 成的16个四位二进制数互不相同。 这个问题的解决思想是这样的。设ai {0,1}（i = 1,2,3,…,16），鼓轮每转一个部分，信号就从a1a2a3a4变为a2a3a4a5，前者的右三位决 定了后者的左三位。因此，我们可把所有三位二进制数作为结点，从每个结点a1a2a3到 a2a3a4连一条有向边表示a1a2a3a4这个四位二进制数，作出如图14- 2所示的所有可能的码变换的有向图。于是问题就转化为在这个有向图中找一条欧拉回路 。这个有向图中8个结点的出度和入度都是2，因此存在欧