根据上述得出的式子，我们计算dN，因为dN?dN?1?1(mod7)所以每到下一年我们加上一天，得到d1600?N?1600,在加上中间出现的因为闰年而多出的天数x，我们得到下面的公式
dN?d1600?N?1600?x
?d1600?100C?Y?1600?3C?[C/4]?[Y/4]?3(mod7) 整理我们得到
dN?d1600?2C?Y?[C/4]?[Y/4](mod7)
上面的这个公式就是我们联系任何一年3月1号的星期数与1600年3月1号的星期数的公式，但是想要求
dN我们还需要计算出
d1600的值，在这里我们采取代
入求值的方法，根据事实，对于1992年3月1日，有N=1992，C=19，Y=92,又因为d1992?0，所以得到
?9?2038 0?d160?[19?/4][?9d2/1?4]060 3(mod7)dd因此，d1600?3，即1600年3月1号是星期三。接着将1600代入到计算N的式
子中，得到
[ dN?3?2C?Y?[C/4]?Y/4](m o （3-1）
上述式子就是我们用来计算第年每一月的第一天的星期数的方法结论，那么我们只能计算每月第一天的星期数吗？有没有方法来计算特定月份的每一天的星期数呢？事实证明是可以的。我们利用它与前一个约得第一天的天数的差值来计算。因为有
30?2(mod7)，也就是说如果这个月有30天，那么它下个月的第一
天的星期数要比这个月第一天的星期数增加2；同理根据31?3(mod7)我们很快得到，如果是31天的话，星期数相应的增加3。所以在计算特定月份的某一天的星期数时，我们必须加上多余的天数。
因为1,3,5,7,8,10,12月份分别有31天，所以在计算它们下一月的时候要加上3天，同样的，2,4,6,9,11月份用来计算某一月份的特定天数的星期数时我们加上2。 如果我们利用上述这种方法是麻烦的，我们需要找出一个相同具有相同增量的表达式。注意到一共有11个增量共29天，所以每个增量是2.6天。不难发现，当m取2到12的数值时，函数[2.6m?0.2]?2得出与上面相同的增量。当m?1时，
21
函数的值为0。因此，dN?[2.6m?0.2]?2模7的最小负剩余表示第N年第m月第一天的星期数。记W为第N年第m月
第k天的星期数，我们只需要在该月第一天的想起书公式中加上k?1，得到
m?0.2?]C2?Y?Y[ W?k?[2.6/?4C][/4 ](我们可以利用这个公式来计算任何一年的任何一天的星期数。
例3.7 求出你出生的那一天的星期数，并计算出你今年生日的星期数。 1990年12月8号
其中，C?19,Y?90,m?10,k?8 因此有：
W?8?[26?0.2]?38?90?[90/4]?[19/4](mod7)?111(mod7)?6(mod7)
从而，我出生那天是星期六。 2013年12月8号
其中，C?20,Y?13,m?10,k?8 因此有:
W?8?[26?0.2]?40?13?[13/4]?[20/4](mod7)?14(mod7)?0(mod7)
即今年我的生日是星期日。 3.3 循环赛程
在本小节中，我们将讨论如何利用同余来安排N个队的循环赛的赛程，使得每个队与其他任何一个队都比赛一次，这个方法是由弗轮德发明的。
我们首先需要讨论的是N的奇偶性，如果N是奇数，则可以添加一个虚拟的队，使得参加比赛的队的总数是偶数，在某一轮与虚拟的队配对的队在本轮中轮空，不参加比赛。所以，我们总可以假设有偶数个小队参加比赛，在必要的时候添加一个虚拟的队。
我们将N个队进行编号:1,2,3...N?1,N。按照下面的方法进行配对，如果
i?j?k(modN?1),i?N,j?N,且j?i，那么在第k轮中，第i队与第k队比赛。
除了第N队和满足2i?k(modN?1)的第i队外，这个赛程表让其他所有队在第k轮中进行比赛。因为(2,N?1)?1，根据定理2.31，同余方程2x?k(modN?1)
22
在1?x?N?1内有且仅有一个解。所以，这样的第i队是存在的。我们让第i队与第N队在第k轮中进行比赛。
那么为什么这样做就使得每个队与其他任何一个队都比赛一次且只比赛一次呢？我们考虑前N?1个队，在第k轮中第i队与第N队制比赛一次，其中
1?x?N?1，并且2i?k(modN?1)，即第i队不会两次与同一队进行比赛。如果
'ikjk第队与第队在第轮和第轮都进行了比赛，那么就会有i?j?k(modN?1)''i?j?k(modN?1)k?k(modN?1)，所以显然矛盾。 和。因为
所以我们得到，前N?1个队中的每一个队都进行了N?1次比赛。并且和同一个队比赛不超过两次。也就是说，和每一个队只进行一次比赛。同理，第N队进行了N?1次比赛，又因为任何其他队与第N队只进行一次比赛，所以第N队与其他任何一队只进行了一次比赛。
例 为了安排七个队进行比赛，我们将这六个队进行编号：1,2,3,4,5，6,7。虚拟队用8编号。在第一轮中，第1队与第j队比赛，其中我们有1?j?1(mod7)。当j的值为7时同余式成立，故第一队与第7队比赛。又因为同余式2?j?1(mod7)的解的值为6，所以第二队与第六队进行比赛。如此进行下去，我们得到，第三队与第五队进行比赛。而j?4是同余式2j?1(mod7)的解，那么第四队与虚拟队第八队配对。也就是说，第四队在第一轮中轮空。继续这个步骤，我们就可以完成其他轮的赛程安排。如表3.1所示，第k轮第i队的对手在第k行第i列给出。
23
表3.1 七队循环赛赛程安排
轮 1 2 3 4 5 6 7 1 7 bye 2 3 4 5 6 2 6 7 1 bye 3 4 5 3 5 6 7 1 2 bye 4 队 4 bye 5 6 7 1 2 3 5 3 4 bye 6 7 1 2 6 2 3 4 5 bye 7 1 7 1 2 3 4 5 6 bye
3.4 散列函数
假设我们想要在计算机中存储一份文件，每份文件的识别号码或者说关键词是位数较多的整数，所以为每个可能的识别号码或者关键字建立一个存储地址是不可行的。但是我们可以利用一种较为系统化的方法。此方法利用适当数量的存储单元，将这些文件排列在存储器中，这样我们就会很容易的访问每个文件。而这个排列所采用的这种较为系统的方法就是基于散列函数发展起来的。在这种方法中，每个散列函数为每份文件分配一个特定的存储单元。现在我们经常使用的函数类型模运算，就是散列函数的一种。我们接下来将要讨论这种类型的函数。 假设一个大学想要在计算机中为它的每一个学生储存一份文件，每份文件的识别号码或者说关键词是每个学生的社会安全号码，首先，令k是被存储文件的关键词，在这个例子中，k是一个学生的社会安全号码，令m是一个正整数，我们定义散列函数h(k):
m)0?h(k)?m h(k)?k(mod,其中，
因此是k模m的最小正剩余.我们想要找到一个m，使得文件合理的分布在m个不同的存储单元0,1,...m?1中。
上述中的m不可以是用来表示一个关键词的基底b的方幂，例如：当我们选取社会安全号码作为关键词时，m不可以是10的方幂，如104 。否则这个时候的散列函数的值会变为关键词的最后几位数字。并且很有可能会使得关键词在存储单元中分布不均匀。这就是为什么早期 社会安全号码的最后三位数字为什么 通常在000到999之间，而不是在900到999之间。
我们有时也会遇到以下几个问题，下面介绍一下问题及其解决方法。
24
k选取m为可以整除b?a （其中k和a对模m来说是较小的整数）的数。
这是不明智的做法。根据上述这个式子，h(k)的值通常会依赖于关键词的某几位数。而且相似的关键字经过顺序重排也可能会被发送到同一个存储单元。如
3310?1(mod111)。 10?1?999m?111取，因为111整除。所以我们得到
又因为
h(064212848)?064212848?064?212?848?14(mod111) 和
?12) h(0648482064?8482?12?064?84821 2那么如何解决上述这个问题呢？我们只需要令m是接近于存储单元数目的一个素数即可。如：我们想要存储2000个学生的文件时，如果我们有5000个存储单元，那么m应该取素数4969。
(1)发生冲突，即将两份不同的文件分配到相同的存储单元。
为了解决这种冲突，使得每份文件分配到唯一的存储单元，我们有两种解决方法。第一种方法：发生冲突时，增加额外的存储单元并且将这个存储单元与原来的存储单元建立链接。我们想要存取发生了冲突的文件时，首先会对涉及的关键字的散列函数进行计算，其次搜索与该存储单元有链接的列表。第二种方法是：寻找下一个开放的存储地址。为了达到这个目的，我们采取被称作双重散列的方法。首先，我们选择h(k)?k(modm),0?h(j)?m，其中m是素数，是散列函数。我们接着选取第二个散列函数：
d?，2 g(k)?k?1(mom
其中0?g(k)?m?1，所以我们有g(k)与m互素。选取
hj(k)?h(k)?j?g(k)(modm)且可以为零。因为我们有
为检测序列，其中
hj(k)的值在零到m之间，并
g(k)与m互素。当j取遍所有整数0,1,...m?1时，将选
出所有的存储单元。当m-2也为素数时，是最佳情况。这种最佳情况使得g(k)的值合理进布。综上，我们希望m与m-2是一对孪生素数。
例 我们引入一个例子，利用社会安全号码，给具有下列社会安全号码的学生文件分配存储地址：
25