離散數(shù)學(xué)課程實(shí)踐-程序設(shè)計(jì)一教程

斷注科技學(xué)流,微教學(xué)錦程建世a編敖材

離微熬學(xué)錦程實(shí)踐——程序強(qiáng)什（1）

激?

玄端滿志朗葉標(biāo)

,假教學(xué)錦程迷破項(xiàng)目做

2004/1月

目錄

第一章：集合論、邏輯與算法基礎(chǔ).............................................12

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

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

1.1.1.1題目............................................................12

1.1.1.2代碼............................................................12

1.1.1.3測(cè)試............................................................14

1.1.1.4運(yùn)行結(jié)果........................................................14

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

1.1.2.1題目.............................................................15

1.1.2.2代碼............................................................15

1.1.2.3測(cè)試............................................................18

1.1.2.4運(yùn)行結(jié)果........................................................18

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

1.1.3.1題目............................................................18

1.1.3.2代碼............................................................18

1.1.3.3測(cè)試............................................................20

1.1.3.4運(yùn)行結(jié)果........................................................21

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

1.2.1題目..............................................................21

1.2.2代碼..............................................................21

1.2.3測(cè)試..............................................................24

1.2.4運(yùn)行結(jié)果.........................................................24

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

1.3.1題目..............................................................24

1.3.2代碼..............................................................24

1.3.3測(cè)試..............................................................26

1.3.4運(yùn)行結(jié)果.........................................................26

1.4多項(xiàng)式運(yùn)算.............................................................26

1.4.1題目..............................................................26

1.4.2代碼..............................................................26

1.4.3測(cè)試..............................................................34

1.4.4運(yùn)行結(jié)果.........................................................35

第二章整數(shù)與數(shù)學(xué)歸納法....................................................36

2.1歐兒里得算法..........................................................36

2.1.1題目..............................................................36

2.1.2代碼..............................................................36

2.1.3測(cè)試..............................................................37

2.1.4運(yùn)行結(jié)果.........................................................37

2.2十進(jìn)制轉(zhuǎn)二進(jìn)制........................................................37

2.2.1題目..............................................................37

2.2.2代碼..............................................................37

2.2.3測(cè)試..............................................................38

2.2.4運(yùn)行結(jié)果.........................................................38

2.3十進(jìn)制轉(zhuǎn)n進(jìn)制.........................................................38

2.3.1題目..............................................................38

2.3.2代碼..............................................................39

2.3.3測(cè)試..............................................................40

2.3.4運(yùn)行結(jié)果.........................................................40

2.4n進(jìn)制轉(zhuǎn)十進(jìn)制.........................................................40

2.4.1題目..............................................................40

2.4.2代碼..............................................................40

2.4.3測(cè)試..............................................................41

2.4.4運(yùn)行結(jié)果.........................................................41

2.5二進(jìn)制加減法...........................................................41

2.5.1題目..............................................................41

2.5.2代碼..............................................................41

2.5.3測(cè)試..............................................................43

2.5.4運(yùn)行結(jié)果.........................................................43

2.6判定素?cái)?shù)...............................................................44

2.6.1題目..............................................................44

2.6.2代碼..............................................................44

2.6.3測(cè)試..............................................................44

2.6.4運(yùn)行結(jié)果.........................................................45

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

2.7.1題目..............................................................45

2.7.2代碼..............................................................45

2.7.3測(cè)試..............................................................46

2.7.4運(yùn)行結(jié)果.........................................................46

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

2.8.1題目..............................................................46

2.8.2代碼..............................................................47

2.8.3測(cè)試..............................................................47

2.8.4運(yùn)行結(jié)果.........................................................48

2.9丟番圖方程求解.........................................................48

2.9.1題目..............................................................48

2.9.2代碼.............................................................48

2.9.3測(cè)試..............................................................49

2.9.4運(yùn)行結(jié)果.........................................................49

第三章關(guān)系與偏序集........................................................50

3.1判斷關(guān)系的自反和對(duì)稱...................................................50

3.1.1題目..............................................................50

3.1.2代碼..............................................................50

3.1.3測(cè)試..............................................................52

3.1.4運(yùn)行結(jié)果..........................................................52

3.2判斷反對(duì)稱.............................................................52

3.2.1題目..............................................................52

3.2.2代碼..............................................................52

3.2.3測(cè)試..............................................................53

3.2.4運(yùn)行結(jié)果.........................................................54

3.3對(duì)稱，自反閉包..........................................................55

3.3.1題目..............................................................55

3.3.2代碼..............................................................55

3.3.3測(cè)試..............................................................56

3.3.4運(yùn)行結(jié)果.........................................................56

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

3.4.1題目..............................................................57

3.4.2代碼..............................................................57

3.4.3測(cè)試..............................................................60

3.4.4運(yùn)行結(jié)果.........................................................61

第四章矩陣與關(guān)系閉包......................................................62

4.1矩陣加減乘轉(zhuǎn)置........................................................62

4.1.1題目..............................................................62

4.1.2代碼..............................................................62

4.1.3測(cè)試..............................................................66

4.1.4運(yùn)行結(jié)果.........................................................67

4.2布爾矩陣交并積.........................................................67

4.2.1題目..............................................................67

4.2.2代碼..............................................................68

4.2.3測(cè)試..............................................................70

4.2.4運(yùn)行結(jié)果.........................................................71

4.3求關(guān)系的傳遞閉包.......................................................72

4.3.1題目..............................................................72

4.3.2代碼..............................................................72

4.3.3測(cè)試..............................................................75

4.3.4運(yùn)行結(jié)果.........................................................76

4.4warshall算法求關(guān)系的傳遞閉包..........................................76

4.4.1題目..............................................................76

4,4.2代碼..............................................................76

4.4.3測(cè)試..............................................................79

4.4.4運(yùn)行結(jié)果.........................................................80

4.5確定最小等價(jià)關(guān)系.......................................................80

4.5.1題目..............................................................80

4.5.2代碼..............................................................80

4.5.3測(cè)試..............................................................84

4.5.4運(yùn)行結(jié)果.........................................................84

第五章函數(shù)................................................................85

5.1判斷是否單滿射一一映射.................................................85

5.1.1題目..............................................................85

5.1.2代碼..............................................................85

5.1.3測(cè)試..............................................................88

5.1.4運(yùn)行結(jié)果.........................................................88

5.2求一個(gè)函數(shù)的域和值域...................................................89

5.2.1題目..............................................................89

5.2.2代碼..............................................................89

5.2.3測(cè)試..............................................................91

5.2.4運(yùn)行結(jié)果.........................................................92

5.3判斷數(shù)列是否為升序.....................................................92

5.3.1題目..............................................................92

5.3.2代碼..............................................................92

5.3.3測(cè)試..............................................................93

5.3.4運(yùn)行結(jié)果.........................................................93

5.4求數(shù)列中有限項(xiàng)之和.....................................................94

5.4.1題目..............................................................94

5.4.2代碼..............................................................94

5.4.3測(cè)試..............................................................94

5.4.4運(yùn)行結(jié)果.........................................................95

5.5求數(shù)列中有限項(xiàng)之積.....................................................95

5.5.1題目..............................................................95

5.5.2代碼..............................................................95

5.5.3測(cè)試..............................................................96

5.5.4運(yùn)行結(jié)果.........................................................96

5.6二進(jìn)制轉(zhuǎn)使進(jìn)制非遞歸算法..............................................96

5.6.1題目..............................................................96

5.6.2代碼..............................................................96

5.6.3測(cè)試..............................................................97

5.6.4運(yùn)行結(jié)果.........................................................97

5.7十進(jìn)制轉(zhuǎn)二進(jìn)制非遞歸...................................................97

5.7.1題目..............................................................97

5.7.2代碼..............................................................98

5.7.3測(cè)試..............................................................98

5.7.4運(yùn)行結(jié)果.........................................................99

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

5.8.1題目..............................................................99

5.8.2代碼..............................................................99

5.8.3測(cè)試.............................................................101

5.8.4運(yùn)行結(jié)果.........................................................102

5.9字符串結(jié)合運(yùn)算........................................................102

5.9.1題目.............................................................102

5.9.2代碼.............................................................102

5.9.3測(cè)試.............................................................105

5.9.4運(yùn)行結(jié)果.........................................................105

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

5.10.1題目............................................................105

5.10.2代碼............................................................105

5.10.3測(cè)試............................................................107

5.10.4運(yùn)行結(jié)果.......................................................107

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

6.1判斷整除...............................................................108

6.1.1題目.............................................................108

6.1.2代碼.............................................................108

6.1.3測(cè)試.............................................................109

6.1.4運(yùn)行結(jié)果.........................................................109

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

6.2.1題目.............................................................109

6.2.2代碼.............................................................109

6.2.3測(cè)試.............................................................111

6.2.4運(yùn)行結(jié)果.........................................................112

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

6.3.1題目.............................................................112

6.3.2代碼.............................................................113

6.3.3測(cè)試.............................................................114

6.3.4運(yùn)行結(jié)果.........................................................115

6.4Masterorvise碼.......................................................115

6.4.1題目.............................................................115

6.4.2代碼.............................................................116

6.4.3測(cè)試.............................................................119

6.4.4運(yùn)行結(jié)果.........................................................119

6.5線性同余式............................................................120

6.5.1題目.............................................................120

6.5.2代碼.............................................................120

6.5.3測(cè)試.............................................................121

6.5.4運(yùn)行結(jié)果.........................................................122

6.6線性同余式方程組中國(guó)同余式...........................................122

6.6.1題目.............................................................122

6.6.2代碼.............................................................123

6.6.3測(cè)試.............................................................124

6.6.4運(yùn)行結(jié)果.........................................................124

6.7循環(huán)賽.................................................................124

6.7.1題目.............................................................124

6.7.2代碼.............................................................125

6.7.3測(cè)試.............................................................126

6.7.4運(yùn)行結(jié)果.........................................................127

6.8雙重散列..............................................................127

6.8.1題目.............................................................127

6.8.2代碼.............................................................127

6.8.3測(cè)試.............................................................128

6.8.4運(yùn)行結(jié)果.........................................................129

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

6.9.1題目.............................................................129

6.9.2代碼.............................................................129

6.9.3測(cè)試.............................................................129

6.9.4運(yùn)行結(jié)果.........................................................129

第七章計(jì)數(shù)原理...........................................................130

7.1求方程整數(shù)解..........................................................130

7.1.1題目.............................................................130

7.1.2代碼.............................................................130

7.1.3測(cè)試.............................................................131

7.1.4運(yùn)行結(jié)果.........................................................131

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

7.2.1題目.............................................................131

7.2.2代碼.............................................................131

7.2.3測(cè)試.............................................................132

7.2.4運(yùn)行結(jié)果.........................................................132

7.3動(dòng)態(tài)程序設(shè)計(jì)..........................................................132

7.3.1題目.............................................................132

7.3.2代碼.............................................................132

7.3.3測(cè)試.............................................................134

7.3.4運(yùn)行結(jié)果.........................................................134

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

7.4.1題目.............................................................134

7.4.2代碼.............................................................134

7.4.3測(cè)試.............................................................135

7.4.4運(yùn)行結(jié)果.........................................................136

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

7.5.1題目.............................................................136

7.5.2代碼.............................................................136

7.5.3測(cè)試.............................................................138

7.5.4運(yùn)行結(jié)果.........................................................139

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

7.6.1題目.............................................................139

7.6.2代碼.............................................................139

7.6.3測(cè)試.............................................................140

7.6.4運(yùn)行結(jié)果.........................................................141

7.7一個(gè)集合所有r-組合....................................................141

7.7.1題目.............................................................141

7.7.2代碼.............................................................141

7.7.3測(cè)試.............................................................143

7.7.4運(yùn)行結(jié)果.........................................................144

第八章遞歸關(guān)系............................................................144

8.1漢諾塔問題.............................................................144

8.1.1題目.............................................................144

8.1.2代碼.............................................................144

8.1.3測(cè)試.............................................................145

8.1.4結(jié)果.............................................................146

8.2Fibonacci數(shù)歹U......................................................................................................................146

8.2.1題目.............................................................146

8.2.2代碼.............................................................146

8.2.3測(cè)試.............................................................147

8.2.4結(jié)果.............................................................147

8.3線性齊次遞歸方程......................................................147

8.3.1題目.............................................................147

8.3.2代碼.............................................................148

8.3.3測(cè)試.............................................................148

8.3.4運(yùn)行結(jié)果.........................................................149

8.4非線性齊次遞歸方程....................................................149

8.4.1題目.............................................................149

8.4.2代碼.............................................................149

8.4.3測(cè)試.............................................................150

8.4.4運(yùn)行結(jié)果.........................................................150

第九章算法與時(shí)間復(fù)雜度...................................................150

9.1順序查找...............................................................150

9.1.1題目.............................................................150

9.1.2代碼.............................................................150

9.1.3測(cè)試.............................................................151

9.1.4運(yùn)行結(jié)果.........................................................152

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

9.2.1題目.............................................................152

9.2.2代碼.............................................................152

9.2.3測(cè)試.............................................................154

9.2.4運(yùn)行結(jié)果.........................................................155

9.3選擇排序..............................................................155

9.3.1題目.............................................................155

9.3.2代碼.............................................................155

9.3.3測(cè)試.............................................................157

9.3.4運(yùn)行結(jié)果.........................................................157

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

9.4.1題目.............................................................157

9.4.2代碼.............................................................157

9.4.3測(cè)試.............................................................158

9.4.4運(yùn)行結(jié)果.........................................................159

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

9.5.1題目.............................................................159

9.5.2代碼.............................................................159

9.5.3測(cè)試.............................................................161

9.5.4運(yùn)行結(jié)果.........................................................161

9.6同時(shí)求最大最小元素...................................................161

9.6.1題目.............................................................161

9.6.2代碼.............................................................162

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

9.6.3測(cè)試1......................................................................................................................163

9.6.4運(yùn)行結(jié)果I...............................................................................................................163

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

9.6.3測(cè)試2.......................................................................................................................164

9.6.4運(yùn)行結(jié)果2..............................................................................................................165

9.7矩陣乘法的最優(yōu)順序...................................................165

9.7.1題目.............................................................165

9.7.2代碼.............................................................165

9.7.3測(cè)試.............................................................167

9.7.4運(yùn)行結(jié)果.........................................................167

第十章圖論................................................................168

10.1輸出每個(gè)頂點(diǎn)的度.....................................................168

10.1.1題目............................................................168

10.1.2代碼............................................................168

10.1