程序員的數(shù)學

第1章　 　0 的故事
——無即是有
本章學習內容　　 　2
小學一年級的回憶　　 　2
10 進制計數(shù)法　　3
什么是10　 　進制計數(shù)法　　3
分解2503　　3
2 進制計數(shù)法　　4
什么是2　 　進制計數(shù)法　　4
分解1100　　5
基數(shù)轉換　　 　6
計算機中為什么采用2　 　進制計數(shù)法　　8
按位計數(shù)法　　10
什么是按位計數(shù)法　　10
不使用按位計數(shù)法的羅馬數(shù)字　　11
指數(shù)法則　　12
10 的0 次方是什么　　12
10-1 是什么　　13
規(guī)則的擴展　　14
對20 進行思考　　14
2-1 是什么　　15
0 所起的作用　　16
0 的作用：占位　　16
0 的作用：統(tǒng)一標準，簡化規(guī)則　　16
日常生活中的0　　17
人類的極限和構造的發(fā)現(xiàn)　　18
重溫歷史進程　　18
為了超越人類的極限　　19
本章小結　　20
第2章　 　邏輯
——真與假的二元世界
本章學習內容　　22
為何邏輯如此重要　　22
邏輯是消除歧義的工具　　22
致對邏輯持否定意見的讀者　　23
乘車費用問題——兼顧完整性和排他性　　 　23
車費規(guī)則　　23
命題及其真假　　24
有沒有“遺漏”　　24
有沒有“重復”　　25
畫一根數(shù)軸輔助思考　　26
注意邊界值　　28
兼顧完整性和排他性　　28
使用if　 　語句分解問題　　28
邏輯的基本是兩個分支　　29
建立復雜命題　　30
邏輯非——不是A　　30
邏輯與—— A 并且B　　32
邏輯或—— A 或者B　　34
異或—— A 或者B（但不都滿足）　　37
相等—— A 和B 等　　39
蘊涵——若A　則　B　　40
囊括所有了嗎　　45
德?摩根定律　　46
德?摩根定律是什么　　46
對偶性　　47
卡諾圖　　48
二燈游戲　　48
首先借助邏輯表達式進行思考　　49
學習使用卡諾圖　　50
三燈游戲　　52
包含未定義的邏輯　　54
帶條件的邏輯與（&&）　　55
帶條件的邏輯或（||）　　57
三值邏輯中的否定（?。　?8
三值邏輯的德?摩根定律　　58
囊括所有了嗎　　59
本章小結　　60
第3　 　章　 　余數(shù)
——周期性和分組
本章學習內容　　64
星期數(shù)的思考題（1）　　64
思考題(100　天以后是星期幾)　　64
思考題答案　　64
運用余數(shù)思考　　65
余數(shù)的力量——將較大的數(shù)字除一次就能分組　　65
星期數(shù)的思考題（2）　　66
思考題(10100　 天以后是星期幾)　　66
提示：可以直接計算嗎　　67
思考題答案　　67
發(fā)現(xiàn)規(guī)律　　68
直觀地把握規(guī)律　　68
乘方的思考題　　70
思考題(1234567987654321)　　70
提示：通過試算找出規(guī)律　　70
思考題答案　　70
回顧：規(guī)律和余數(shù)的關系　　71
通過黑白棋通信　　71
思考題　　71
提示　　73
思考題答案　　73
奇偶校驗　　73
奇偶校驗位將數(shù)字分為兩個集合　　74
尋找戀人的思考題　　74
思考題(　尋找戀人)　　74
提示：先試算較小的數(shù)　　74
思考題答案　　75
回顧　　75
鋪設草席的思考題　　77
思考題（在房間里鋪設草席）　　77
提示：先計算一下草席數(shù)　　77
思考題答案　　78
回顧　　78
一筆畫的思考題　　79
思考題（哥尼斯堡七橋問題）　　79
提示：試算一下　　80
提示：考慮簡化一下　　81
提示：考慮入口和出口　　82
思考題答案　　82
奇偶校驗　　85
本章小結　　86
第4　 　章　 　數(shù)學歸納法
——如何征服無窮數(shù)列
本章學習內容　　88
高斯求和　　88
思考題（存錢罐里的錢）　　88
思考一下　　89
小高斯的解答　　89
討論一下小高斯的解答　　89
歸納　　91
數(shù)學歸納法——　 　如何征服無窮數(shù)列　　91
0　以上的整數(shù)的斷言　　92
高斯的斷言　　93
什么是數(shù)學歸納法　　93
試著征服無窮數(shù)列　　94
用數(shù)學歸納法證明高斯的斷言　　95
求出奇數(shù)的和　 　——　 　數(shù)學歸納法實例　　96
奇數(shù)的和　　96
通過數(shù)學歸納法證明　　97
圖形化說明　　98
黑白棋思考題　 　——　 　錯誤的數(shù)學歸納法　　99
思考題（黑白棋子的顏色）　　99
提示：不要為圖所惑　　100
思考題答案　　 　100
編程和數(shù)學歸納法　　101
通過循環(huán)表示數(shù)學歸納法　　101
循環(huán)不變式　　 　103
本章小結　　107
第5章　 　排列組合
——解決計數(shù)問題的方法
本章學習內容　　110
計數(shù)——與整數(shù)的對應關系　　110
何謂計數(shù)　　110
注意“遺漏”和“重復”　　111
植樹問題——不要忘記0　　111
植樹問題思考題　　111
加法法則　　115
加法法則　　115
乘法法則　　117
乘法法則　　117
置換　　121
置換　　121
歸納一下　　122
思考題（撲克牌的擺法）　　123
排列　　125
排列　　125
歸納一下　　126
樹形圖——能夠認清本質嗎　　128
組合　　130
組合　　130
歸納一下　　131
置換、排列、組合的關系　　132
思考題練習　　 　134
重復組合　　134
也要善于運用邏輯　　136
本章小結　　139
第6章　 　遞歸
——自己定義自己
本章學習內容　　142
漢諾塔　　142
思考題（漢諾塔）　　142
提示：先從小漢諾塔著手　　143
思考題答案　　 　146
求出解析式　　 　148
解出漢諾塔的程序　　149
找出遞歸結構　　150
再談階乘　　151
階乘的遞歸定義　　152
思考題（和的定義）　　153
遞歸和歸納　　 　153
斐波那契數(shù)列　　154
思考題（不斷繁殖的動物）　　154
斐波那契數(shù)列　　157
帕斯卡三角形　　159
什么是帕斯卡三角形　　159
遞歸定義組合數(shù)　　162
組合的數(shù)學理論解釋　　163
遞歸圖形　　165
以遞歸形式畫樹　　165
實際作圖　　166
謝爾平斯基三角形　　167
本章小結　　168
第7章　 　指數(shù)爆炸
——如何解決復雜問題
本章學習內容　　172
什么是指數(shù)爆炸　　 　172
思考題（折紙問題）　　172
指數(shù)爆炸　　175
倍數(shù)游戲——指數(shù)爆炸引發(fā)的難題　　176
程序的設置選項　　176
不能認為是“有限的”就不假思索　　178
二分法查找——利用指數(shù)爆炸進行查找　　178
尋找犯人的思考題　　178
提示：先思考人數(shù)較少的情況　　179
思考題答案　　 　180
找出遞歸結構以及遞推公式　　181
二分法查找和指數(shù)爆炸　　183
對數(shù)——掌握指數(shù)爆炸的工具　　184
什么是對數(shù)　　 　184
對數(shù)和乘方的關系　　184
以2　為底的對數(shù)　　186
以2　為底的對數(shù)練習　　186
對數(shù)圖表　　187
指數(shù)法則和對數(shù)　　188
對數(shù)和計算尺　　190
密碼——利用指數(shù)爆炸加密　　193
暴力破解法　　 　193
字長和安全性的關系　　193
如何處理指數(shù)爆炸　　195
理解問題空間的大小　　195
四種處理方法　　195
本章小結　　196
第8章　 　不可解問題
——不可解的數(shù)、無法編寫的程序
本章學習內容　　200
反證法　　200
什么是反證法　　200
質數(shù)思考題　　 　202
反證法的注意事項　　203
可數(shù)　　203
什么是可數(shù)　　 　203
可數(shù)集合的例子　　204
有沒有不可數(shù)的集合　　206
對角論證法　　 　207
所有整數(shù)數(shù)列的集合是不可數(shù)的　　207
所有實數(shù)的集合是不可數(shù)的　　211
所有函數(shù)的集合也是不可數(shù)的　　212
不可解問題　　 　213
什么是不可解問題　　213
存在不可解問題　　214
思考題　　 　215
停機問題　　215
停機　　216
處理程序的程序　　217
什么是停機問題　　217
停機問題的證明　　219
寫給尚未理解的讀者　　222
不可解問題有很多　　223
本章小結　　224
第9章　 　什么是程序員的數(shù)學
——總結篇
本章學習內容　　226
何為解決問題　　229
認清模式，進行抽象化　　229
由不擅長催生出的智慧　　229
幻想法則　　230
程序員的數(shù)學　　231