离散数学课程实践-程序设计一教程

断注科技学流,微教学锦程建世a编敖材

离微熬学锦程实践——程序强什（1）

激«

玄端满志朗叶标

,假教学锦程迷破项目做

2004/1月

目录

第一章：集合论、逻辑与算法基础.............................................12

1.1...................................................................................................................................................12

1.1.1A和B的差集.........................................................12

1.1.1.1题目............................................................12

1.1.1.2代码............................................................12

1.1.1.3测试............................................................14

1.1.1.4运行结果........................................................14

1.1.2并集..................................................................15

1.1.2.1题目.............................................................15

1.1.2.2代码............................................................15

1.1.2.3测试............................................................18

1.1.2.4运行结果........................................................18

1.1.3交集..................................................................18

1.1.3.1题目............................................................18

1.1.3.2代码............................................................18

1.1.3.3测试............................................................20

1.1.3.4运行结果........................................................21

1.2真值表.................................................................21

1.2.1题目..............................................................21

1.2.2代码..............................................................21

1.2.3测试..............................................................24

1.2.4运行结果.........................................................24

1.3冒泡排序...............................................................24

1.3.1题目..............................................................24

1.3.2代码..............................................................24

1.3.3测试..............................................................26

1.3.4运行结果.........................................................26

1.4多项式运算.............................................................26

1.4.1题目..............................................................26

1.4.2代码..............................................................26

1.4.3测试..............................................................34

1.4.4运行结果.........................................................35

第二章整数与数学归纳法....................................................36

2.1欧儿里得算法..........................................................36

2.1.1题目..............................................................36

2.1.2代码..............................................................36

2.1.3测试..............................................................37

2.1.4运行结果.........................................................37

2.2十进制转二进制........................................................37

2.2.1题目..............................................................37

2.2.2代码..............................................................37

2.2.3测试..............................................................38

2.2.4运行结果.........................................................38

2.3十进制转n进制.........................................................38

2.3.1题目..............................................................38

2.3.2代码..............................................................39

2.3.3测试..............................................................40

2.3.4运行结果.........................................................40

2.4n进制转十进制.........................................................40

2.4.1题目..............................................................40

2.4.2代码..............................................................40

2.4.3测试..............................................................41

2.4.4运行结果.........................................................41

2.5二进制加减法...........................................................41

2.5.1题目..............................................................41

2.5.2代码..............................................................41

2.5.3测试..............................................................43

2.5.4运行结果.........................................................43

2.6判定素数...............................................................44

2.6.1题目..............................................................44

2.6.2代码..............................................................44

2.6.3测试..............................................................44

2.6.4运行结果.........................................................45

2.7素因子分解.............................................................45

2.7.1题目..............................................................45

2.7.2代码..............................................................45

2.7.3测试..............................................................46

2.7.4运行结果.........................................................46

2.8Fermat因子解法........................................................46

2.8.1题目..............................................................46

2.8.2代码..............................................................47

2.8.3测试..............................................................47

2.8.4运行结果.........................................................48

2.9丢番图方程求解.........................................................48

2.9.1题目..............................................................48

2.9.2代码.............................................................48

2.9.3测试..............................................................49

2.9.4运行结果.........................................................49

第三章关系与偏序集........................................................50

3.1判断关系的自反和对称...................................................50

3.1.1题目..............................................................50

3.1.2代码..............................................................50

3.1.3测试..............................................................52

3.1.4运行结果..........................................................52

3.2判断反对称.............................................................52

3.2.1题目..............................................................52

3.2.2代码..............................................................52

3.2.3测试..............................................................53

3.2.4运行结果.........................................................54

3.3对称，自反闭包..........................................................55

3.3.1题目..............................................................55

3.3.2代码..............................................................55

3.3.3测试..............................................................56

3.3.4运行结果.........................................................56

3.4偏序集极小极大元最小最大元............................................57

3.4.1题目..............................................................57

3.4.2代码..............................................................57

3.4.3测试..............................................................60

3.4.4运行结果.........................................................61

第四章矩阵与关系闭包......................................................62

4.1矩阵加减乘转置........................................................62

4.1.1题目..............................................................62

4.1.2代码..............................................................62

4.1.3测试..............................................................66

4.1.4运行结果.........................................................67

4.2布尔矩阵交并积.........................................................67

4.2.1题目..............................................................67

4.2.2代码..............................................................68

4.2.3测试..............................................................70

4.2.4运行结果.........................................................71

4.3求关系的传递闭包.......................................................72

4.3.1题目..............................................................72

4.3.2代码..............................................................72

4.3.3测试..............................................................75

4.3.4运行结果.........................................................76

4.4warshall算法求关系的传递闭包..........................................76

4.4.1题目..............................................................76

4,4.2代码..............................................................76

4.4.3测试..............................................................79

4.4.4运行结果.........................................................80

4.5确定最小等价关系.......................................................80

4.5.1题目..............................................................80

4.5.2代码..............................................................80

4.5.3测试..............................................................84

4.5.4运行结果.........................................................84

第五章函数................................................................85

5.1判断是否单满射一一映射.................................................85

5.1.1题目..............................................................85

5.1.2代码..............................................................85

5.1.3测试..............................................................88

5.1.4运行结果.........................................................88

5.2求一个函数的域和值域...................................................89

5.2.1题目..............................................................89

5.2.2代码..............................................................89

5.2.3测试..............................................................91

5.2.4运行结果.........................................................92

5.3判断数列是否为升序.....................................................92

5.3.1题目..............................................................92

5.3.2代码..............................................................92

5.3.3测试..............................................................93

5.3.4运行结果.........................................................93

5.4求数列中有限项之和.....................................................94

5.4.1题目..............................................................94

5.4.2代码..............................................................94

5.4.3测试..............................................................94

5.4.4运行结果.........................................................95

5.5求数列中有限项之积.....................................................95

5.5.1题目..............................................................95

5.5.2代码..............................................................95

5.5.3测试..............................................................96

5.5.4运行结果.........................................................96

5.6二进制转使进制非递归算法..............................................96

5.6.1题目..............................................................96

5.6.2代码..............................................................96

5.6.3测试..............................................................97

5.6.4运行结果.........................................................97

5.7十进制转二进制非递归...................................................97

5.7.1题目..............................................................97

5.7.2代码..............................................................98

5.7.3测试..............................................................98

5.7.4运行结果.........................................................99

5.8输出逆序字符串.........................................................99

5.8.1题目..............................................................99

5.8.2代码..............................................................99

5.8.3测试.............................................................101

5.8.4运行结果.........................................................102

5.9字符串结合运算........................................................102

5.9.1题目.............................................................102

5.9.2代码.............................................................102

5.9.3测试.............................................................105

5.9.4运行结果.........................................................105

5.10串模式匹配............................................................105

5.10.1题目............................................................105

5.10.2代码............................................................105

5.10.3测试............................................................107

5.10.4运行结果.......................................................107

第六章同余................................................................108

6.1判断整除...............................................................108

6.1.1题目.............................................................108

6.1.2代码.............................................................108

6.1.3测试.............................................................109

6.1.4运行结果.........................................................109

6.2isbn.......................................................................................................................................109

6.2.1题目.............................................................109

6.2.2代码.............................................................109

6.2.3测试.............................................................111

6.2.4运行结果.........................................................112

6.3upc........................................................................................................................................112

6.3.1题目.............................................................112

6.3.2代码.............................................................113

6.3.3测试.............................................................114

6.3.4运行结果.........................................................115

6.4Masterorvise码.......................................................115

6.4.1题目.............................................................115

6.4.2代码.............................................................116

6.4.3测试.............................................................119

6.4.4运行结果.........................................................119

6.5线性同余式............................................................120

6.5.1题目.............................................................120

6.5.2代码.............................................................120

6.5.3测试.............................................................121

6.5.4运行结果.........................................................122

6.6线性同余式方程组中国同余式...........................................122

6.6.1题目.............................................................122

6.6.2代码.............................................................123

6.6.3测试.............................................................124

6.6.4运行结果.........................................................124

6.7循环赛.................................................................124

6.7.1题目.............................................................124

6.7.2代码.............................................................125

6.7.3测试.............................................................126

6.7.4运行结果.........................................................127

6.8双重散列..............................................................127

6.8.1题目.............................................................127

6.8.2代码.............................................................127

6.8.3测试.............................................................128

6.8.4运行结果.........................................................129

6.9rsa........................................................................................................................................129

6.9.1题目.............................................................129

6.9.2代码.............................................................129

6.9.3测试.............................................................129

6.9.4运行结果.........................................................129

第七章计数原理...........................................................130

7.1求方程整数解..........................................................130

7.1.1题目.............................................................130

7.1.2代码.............................................................130

7.1.3测试.............................................................131

7.1.4运行结果.........................................................131

7.2c(n,r)分治法............................................................131

7.2.1题目.............................................................131

7.2.2代码.............................................................131

7.2.3测试.............................................................132

7.2.4运行结果.........................................................132

7.3动态程序设计..........................................................132

7.3.1题目.............................................................132

7.3.2代码.............................................................132

7.3.3测试.............................................................134

7.3.4运行结果.........................................................134

7.4nextlargestpermutation......................................................................................................134

7.4.1题目.............................................................134

7.4.2代码.............................................................134

7.4.3测试.............................................................135

7.4.4运行结果.........................................................136

7.5集合的所有排列........................................................136

7.5.1题目.............................................................136

7.5.2代码.............................................................136

7.5.3测试.............................................................138

7.5.4运行结果.........................................................139

7.6nextlargestrcombination.....................................................................................................139

7.6.1题目.............................................................139

7.6.2代码.............................................................139

7.6.3测试.............................................................140

7.6.4运行结果.........................................................141

7.7一个集合所有r-组合....................................................141

7.7.1题目.............................................................141

7.7.2代码.............................................................141

7.7.3测试.............................................................143

7.7.4运行结果.........................................................144

第八章递归关系............................................................144

8.1汉诺塔问题.............................................................144

8.1.1题目.............................................................144

8.1.2代码.............................................................144

8.1.3测试.............................................................145

8.1.4结果.............................................................146

8.2Fibonacci数歹U......................................................................................................................146

8.2.1题目.............................................................146

8.2.2代码.............................................................146

8.2.3测试.............................................................147

8.2.4结果.............................................................147

8.3线性齐次递归方程......................................................147

8.3.1题目.............................................................147

8.3.2代码.............................................................148

8.3.3测试.............................................................148

8.3.4运行结果.........................................................149

8.4非线性齐次递归方程....................................................149

8.4.1题目.............................................................149

8.4.2代码.............................................................149

8.4.3测试.............................................................150

8.4.4运行结果.........................................................150

第九章算法与时间复杂度...................................................150

9.1顺序查找...............................................................150

9.1.1题目.............................................................150

9.1.2代码.............................................................150

9.1.3测试.............................................................151

9.1.4运行结果.........................................................152

9.2折半查找..............................................................152

9.2.1题目.............................................................152

9.2.2代码.............................................................152

9.2.3测试.............................................................154

9.2.4运行结果.........................................................155

9.3选择排序..............................................................155

9.3.1题目.............................................................155

9.3.2代码.............................................................155

9.3.3测试.............................................................157

9.3.4运行结果.........................................................157

9.4插入排序..............................................................157

9.4.1题目.............................................................157

9.4.2代码.............................................................157

9.4.3测试.............................................................158

9.4.4运行结果.........................................................159

9.5合并排序...............................................................159

9.5.1题目.............................................................159

9.5.2代码.............................................................159

9.5.3测试.............................................................161

9.5.4运行结果.........................................................161

9.6同时求最大最小元素...................................................161

9.6.1题目.............................................................161

9.6.2代码.............................................................162

方法1...................................................................................................................................162

9.6.3测试1......................................................................................................................163

9.6.4运行结果I...............................................................................................................163

方法2...................................................................................................................................163

9.6.3测试2.......................................................................................................................164

9.6.4运行结果2..............................................................................................................165

9.7矩阵乘法的最优顺序...................................................165

9.7.1题目.............................................................165

9.7.2代码.............................................................165

9.7.3测试.............................................................167

9.7.4运行结果.........................................................167

第十章图论................................................................168

10.1输出每个顶点的度.....................................................168

10.1.1题目............................................................168

10.1.2代码............................................................168

10.1