离散数学实验指导书(2011-5-16)(6)

nn?1n?21F=Cn·nm－Cn·(n?1)m+Cn·(n?2)m－??.+ (?1)n?1Cn·1m

来求得其解。但是在这儿，我们也可以使用计算机中常用的一种方法——枚举法来求解。

枚举法就是一个个的列出所有满足条件的函数，并将其记录下来，当枚举结束时就可得到欲求函数的数目。对于上面提出的问题，相当于把n个不同的数字放到m个位置上去的所有不同的方法。其中，数字是可重复出现的，但是每个数字必须都出现过至少一次才是满射函数。 5、实验仪器设备或软件环境及工具

运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。 6、实验要求

预习函数的定义和函数的性质，实验由几人一组完成。所设计的程序能够通过编译，并能够实现求从集合A到B上的所有满射函数的个数。 7、实验报告要求

（1）写出实验过程中遇到的问题及其解决过程。

（2）设计出类c的算法并编写一个程序求出从集合A到B上的所有满射函数的个数。 （3）写出实验结束时的程序清单及运行结果及实验总结。 8、思考题

设计出一个类c的算法，并编写一个程序求出从集合A到B上的所有单射函数的个数。

18

第三章 图论

实验十二 求可达矩阵的Warshall算法

1、实验类型：操作性 2、实验目的

通过算法设计并编程实现求出给定n个结点的图G的可达矩阵P，加深学生对可达矩阵的理解。 3、实验内容

给定n个结点的图G的邻接矩阵A，求G的可达矩阵P。 4、实验仪器设备或软件环境及工具

运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。 5、实验要求

复习图的矩阵表示部分的内容，实验由一人一组完成。所设计的程序能够通过编译，并能够实现从给定n个结点的图G的邻接矩阵A，求出G的可达矩阵P 6、实验步骤及注意事项

（1） 将图G的邻接矩阵送入P（n，n）中。 （2） 1?i。 （3） 1?j。

（4） 对于k=1，2，?，n，作：Pjk∨（Pji∧Pik）?Pjk （5） j+1?j，若j?n，则转（4）。

（6） i+1?i，若i?n，则转（3），否则结束。 7、实验报告要求

（1）写出实验过程中遇到的问题及其解决过程。

（2）写出类c的算法并写出一个程序求给定n个结点的图G的可达矩阵P （3）写出实验结束时的程序清单及运行结果及实验总结。

19