Dijkstra算法： Dijkstra算法： 算法
OSPF协议是Dijkstra算法在网络路由中的一个具体实现 OSPF协议是Dijkstra算法在网络路由中的一个具体实现
中国邮递员问题（已从算法上解决） 中国邮递员问题（已从算法上解决）
给定一个连通图, 在每边e 上赋予一个非负的( ei ) , 要求一个圈 , 过 每边至少一次, 每边至少一次, 并使圈的总权最小
Your company slogan
13
若干示例——递归： Josephus问题 递归： 若干示例 递归 问题
在这里我们考虑它的变形：我们从围成一个圆的编号 在这里我们考虑它的变形： 个人开始，然后依次排除剩下的人中的第 为1到n的n个人开始，然后依次排除剩下的人中的第 直到仅剩下一个幸存者。 10的 二个直到仅剩下一个幸存者 例如，下面是n 二个直到仅剩下一个幸存者。例如，下面是n = 10的 开始状态： 开始状态：
Your company slogan
若干示例——递归：汉诺塔 递归： 若干示例 递归
现在又出现了一个问题：怎样做才最好？也就是说，为了 现在又出现了一个问题：怎样做才最好？也就是说， 完成这个任务，多少次移动是必要而且充分的？ 完成这个任务，多少次移动是必要而且充分的？ 为了回答这个问题，我们引入适当的表示法： 为了回答这个问题，我们引入适当的表示法： Lucas规则下将 设Tn 为在 Lucas规则下将 n 个盘子从一根杆转移到另一 根杆的最小移动次数。 根杆的最小移动次数。 很明显， =0， =1， 3。 很明显， T0=0，T1=1，T2 = 3。
Your company slogan
22
若干示例——Stern-Brocot数系 数系 若干示例
我们可以把Stern-Brocot树视为代表有理数的一 我们可以把Stern-Brocot树视为代表有理数的一 个数系,因为每个正的，简约分数恰好出现一次， 个数系,因为每个正的，简约分数恰好出现一次，当 我们从树的根转到一个特殊分数是，让我们用字母L 我们从树的根转到一个特殊分数是，让我们用字母L 表示下到左分支或右分支，于是L 和R表示下到左分支或右分支，于是L和R的一个串 唯一确定树中的一个位置，例如，LRRL意味着我 唯一确定树中的一个位置，例如，LRRL意味着我 们从1/1下到左边的 下到左边的1/2，然后下到右边的2/3， 们从1/1下到左边的1/2，然后下到右边的2/3， 然后下到右边的3/4，然后下到左边的5/7， 然后下到右边的3/4，然后下到左边的5/7，我们 能把LRRL考虑为 考虑为5/7的一种表示方法 的一种表示方法， 能把LRRL考虑为5/7的一种表示方法，每一个正 分数以此方式表示为唯一的一个Ｌ 的串. 分数以此方式表示为唯一的一个Ｌ和R的串.
15
若干示例——递归： Josephus问题 递归： 若干示例 递归 问题
列出递归方程：
假设n的二进制展开为
则有
Your company slogan
16
若干示例——递归：Catalan数 递归： 若干示例 递归 数
假设我们有 次相乘计算它的乘积. 个变量 ，通过 次相乘计算它的乘积. 以致完全指定相乘的次序, 把括号插入乘积 以致完全指定相乘的次序,问有多少 种方式？ 种方式？ 一个栈的容量为n 依次进栈， 一个栈的容量为n，现有元素 依次进栈，问总共有多少种不 同的出栈序列？ 同的出栈序列？ 一个凸n边形有多少种不同的三角剖分方式？ 一个凸n边形有多少种不同的三角剖分方式？ n个叶子节点的完全二叉树的个数? 个叶子节点的完全二叉树的个数?
用顶点表示通信设备、用边表示通信链路。 假定该图是完全图, 假定该图是完全图,即任意两点间都有一条 边相连。在某些应用场合, 边相连。在某些应用场合,顶点两两配合对 作为一个整体。保证在某些链路出故障不 能使用时, 能使用时,任两对配对顶点间都至少有一条 链路畅通无阻, 链路畅通无阻,如右图所示 (x1,x2)， (y1,y2) ，(z1,z2)各组 对 共 个 间设备 链 种颜 标记 †§标记蓝 †§标记蓝 间设备 问题， 问题，则 (x1,x2)顶 间没
对 (z1,z2)顶
对
Your company slogan
若干示例——组网 组网 若干示例
RamseyŠq•±‰å RamseyŠq•±‰å 应 组网
图x1x2z1z4‹DŽMˆ¼‰n 个单 C4 ‰0证 ‰0证 r(C4,C4)=6。因此, 如果只有 )=6。因此, 两个中间设施,那么存在一个5 两个中间设施,那么存在一个5 个顶点 的网络使得可以安排一种不出现单色C4 的网络使得可以安排一种不出现单色C4 的连接方式。 而r(C4,C4,C4)=11， )=11， 存在一个10 存在一个10 个 顶点的网络,它使用3 顶点的网络,它使用3 个中间设施且没有 单色的C 单色的C4
Your company slogan
7
若干示例——递归：汉诺塔 递归： 若干示例 递归
Your company slogan
8
若干示例——递归：汉诺塔 递归： 若干示例 递归
汉诺
void hanoi(int n,char A,char B,char C) hanoi( { if(n==1) { printf("Move printf("Move disk %d from %c to %c\n",n,A,C); %c\n",n,A,C); } else { hanoi(nhanoi(n-1,A,C,B); printf("Move printf("Move disk %d from %c to %c\n",n,A,C); %c\n",n,A,C); hanoi(nhanoi(n-1,B,A,C); } }
Your company slogan
14
若干示例——递归： Josephus问题 递归： 若干示例 递归 问题
处死的过程如下：
1
10
2 3 4
9 8 7 6 5
9
5
排除的次序是2，4，6，8，10，3，7，1，9，所以5是 幸存者。
问题是：如何确定幸存者的号码J(n)
Your company slogan
注意：上述公式没有使用‘＝’，而使用了‘≤’,因为
上述构造方法仅仅能证明 2Tn－1 ＋1 次移动是充分的，并 没有说明 2 Tn－1＋1次移动是必要的。
有更好的方法吗？
Your company slogan
12
若干示例——递归：汉诺塔 递归： 若干示例 递归
实际上没有更好的方法。
在某个时刻我们一定要移动最大的盘，当移动最大盘时， 在某个时刻我们一定要移动最大的盘，当移动最大盘时， n－1 个稍小的盘一定在一根杆上，而且至少用了Tn－1次 个稍小的盘一定在一根杆上，而且至少用了T 移动来把这些盘子放到那根杆上（这是根据T 的定义）。 移动来把这些盘子放到那根杆上（这是根据Tn－1的定义）。 移动最大盘的次数肯定不会少于1 移动最大盘的次数肯定不会少于1次。 在最后一次移动最大盘之后，还必须把n 个稍小盘( 在最后一次移动最大盘之后，还必须把n－1个稍小盘(一 定还在一根杆上)转移回最大盘上， 定还在一根杆上)转移回最大盘上，这同样至少需要 Tn－1 次移动。 因此有： 次移动。 因此有：
LOGO
组 数学 与计 机科学 机科学
许瑞 xrmzp@
Table of Contents
1
组 数学概
2
计 机科学 机科学
3
干
4
干问题 干问题
Your company slogan
组 数学概
组 数学研究 数学研究 问题 对
Šê‰å… 问题 计数 构 ŒŸ优 ŒŸ优 问题 问题 问题
Your company slogan
若干示例——区组设计 区组设计 若干示例
问题用15种饲料对动物做实验 问题用15种饲料对动物做实验，分5个阶段进行，每个阶段以3中饲 种饲料对动物做实验， 个阶段进行，每个阶段以3 料的混合物喂养7只同类动物。实验要求： 料的混合物喂养7只同类动物。实验要求：
Your company slogan
10
若干示例——递归：汉诺塔 递归： 若干示例 递归
Tn-1
1
Tn-1
Your company slogan
11
若干示例——递归：汉诺塔 递归： 若干示例 递归
根据前面的分析和图示，我们看到至多用2Tn-1+1 根据前面的分析和图示，我们看到至多用2 次移动就可以完成转移n个盘子的任务（n>0） 次移动就可以完成转移n个盘子的任务（n>0）:
Your company slogan
若干示例——递归：QuickSort分析 递归： 若干示例 递归 分析
QuickSort的平均比较次数满足递归： QuickSort的平均比较次数满足递归： 的平均比较次数满足递归
利用简单的技巧可以解得
若定义 则有
Your company slogan
若干示例——图论 图论 若干示例
Your company slogan
若干示例——递归：Fibonacci数 递归： 若干示例 递归 数
定义： 定义：
小的情形
意义：在一个网络中，消息接收者每过一个时间周期就将消息传递给 意义：在一个网络中， 一个新的节点，则在第n个周期知道消息的节点数即为Fibonacci数 一个新的节点，则在第n个周期知道消息的节点数即为Fibonacci数 Fn 推广:在一个网络中,消息所有者每过l个时间周期就将消息传递给m 推广:在一个网络中,消息所有者每过l个时间周期就将消息传递给m个 新的节点,则在第n个周期知道消息的节点数为多少？ 新的节点,则在第n个周期知道消息的节点数为多少？ 若考虑各个节点的差异性呢？ 若考虑各个节点的差异性呢？mi，ni