開啟主選單

求真百科

程序員的數學

程序員的數學

《程序員的數學》是2012年由人民郵電出版社出版的圖書,作者是結城浩。本書面向程序員介紹了編程中常用的數學知識,藉以培養初級程序員的數學思維。讀者無需精通編程,也無需精通數學,只需具備四則運算和乘方等基礎知識,就可以閱讀本書。

編程的基礎是計算機科學,而計算機科學的基礎是數學。因此,學習數學有助於鞏固編程的基礎,寫出更健壯的程序。

目錄

目錄

內容簡介

作者簡介

目錄

內容簡介

編程的基礎是計算機科學,而計算機科學的基礎是數學。因此,學習數學有助於鞏固編程的基礎,寫出更健壯的程序。

本書面向程序員介紹了編程中常用的數學知識,藉以培養初級程序員的數學思維。讀者無需精通編程,也無需精通數學,只需具備四則運算和乘方等基礎知識,就可以閱讀本書。

書中講解了二進制計數法、邏輯、餘數、排列組合、遞歸、指數爆炸、不可解問題等許多與編程密切相關的數學方法,分析了哥尼斯堡七橋問題、少年高斯求和方法、漢諾塔、斐波那契數列等經典問題和算法。引導讀者深入理解編程中的數學方法和思路

本書還對程序員和計算機的分工進行了有益的探討。讀完此書,你會對以程序為媒介的人機合作有更深刻的理解。

作者簡介

結城浩(Hiroshi Yuki)

生於1963年,日本資深技術作家和程序員。在編程語言、設計模式、數學、加密技術等領域,編寫了很多深受歡迎的入門書。代表作有《數學女孩》系列、《程序員的數學》等。

管傑

畢業於復旦大學日語系。現為對日軟件工程師,多年日語技術文檔編寫經驗。愛好日漢翻譯和日本文化史,譯有《明解C語言:入門篇》等。

目錄

第1章   0 的故事

——無即是有

本章學習內容  2

小學一年級的回憶   2

10 進制計數法 3

什麼是10   進制計數法 3

分解2503 3

2 進制計數法 4

什麼是2進制計數法 4

分解1100 5

基數轉換   6

計算機中為什麼採用2   進制計數法 8

按位計數法 10

什麼是按位計數法 10

不使用按位計數法的羅馬數字 11

指數法則 12

10 的0 次方是什麼 12

10-1 是什麼 13

規則的擴展 14

對20 進行思考 14

2-1 是什麼 15

0 所起的作用 16

0 的作用:占位 16

0 的作用:統一標準,簡化規則 16

日常生活中的0 17

人類的極限和構造的發現 18

重溫歷史進程 18

為了超越人類的極限 19

本章小結 20

第2章   邏輯

——真與假的二元世界

本章學習內容 22

為何邏輯如此重要 22

邏輯是消除歧義的工具 22

致對邏輯持否定意見的讀者 23

乘車費用問題——兼顧完整性和排他性   23

車費規則 23

命題及其真假 24

有沒有「遺漏」 24

有沒有「重複」 25

畫一根數軸輔助思考 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

三值邏輯中的否定(!) 58

三值邏輯的德?摩根定律 58

囊括所有了嗎 59

本章小結 60

第3章   餘數

——周期性和分組

本章學習內容 64

星期數的思考題(1) 64

思考題(100 天以後是星期幾) 64

思考題答案 64

運用餘數思考 65

餘數的力量——將較大的數字除一次就能分組 65

星期數的思考題(2) 66

思考題(10100  天以後是星期幾) 66

提示:可以直接計算嗎 67

思考題答案 67

發現規律 68

直觀地把握規律 68

乘方的思考題 70

思考題 70

提示:通過試算找出規律 70

思考題答案 70

回顧:規律和餘數的關係 71

通過黑白棋通信 71

思考題 71

提示 73

思考題答案 73

奇偶校驗 73

奇偶校驗位將數字分為兩個集合 74

尋找戀人的思考題 74

思考題( 尋找戀人) 74

提示:先試算較小的數 74

思考題答案 75

回顧 75

鋪設草蓆的思考題 77

思考題(在房間裡鋪設草蓆) 77

提示:先計算一下草蓆數 77

思考題答案 78

回顧 78

一筆畫的思考題 79

思考題(哥尼斯堡七橋問題) 79

提示:試算一下 80

提示:考慮簡化一下 81

提示:考慮入口和出口 82

思考題答案 82

奇偶校驗 85

本章小結 86

第4章   數學歸納法

——如何征服無窮數列

本章學習內容 88

高斯求和 88

思考題(存錢罐里的錢) 88

思考一下 89

小高斯的解答 89

討論一下小高斯的解答 89

歸納 91

數學歸納法——   如何征服無窮數列 91

0 以上的整數的斷言 92

高斯的斷言 93

什麼是數學歸納法 93

試着征服無窮數列 94

用數學歸納法證明高斯的斷言 95

求出奇數的和   ——   數學歸納法實例 96

奇數的和 96

通過數學歸納法證明 97

圖形化說明 98

黑白棋思考題   ——   錯誤的數學歸納法 99

思考題(黑白棋子的顏色) 99

提示:不要為圖所惑 100

思考題答案   100

編程和數學歸納法 101

通過循環表示數學歸納法 101

循環不變式   103

本章小結 107

第5章   排列組合

——解決計數問題的方法

本章學習內容 110

計數——與整數的對應關係 110

何謂計數 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

斐波那契數列 154

思考題(不斷繁殖的動物) 154

斐波那契數列 157

帕斯卡三角形 159

什麼是帕斯卡三角形 159

遞歸定義組合數 162

組合的數學理論解釋 163

遞歸圖形 165

以遞歸形式畫樹 165

實際作圖 166

謝爾平斯基三角形 167

本章小結 168

第7章   指數爆炸

——如何解決複雜問題

本章學習內容 172

什麼是指數爆炸   172

思考題(摺紙問題) 172

指數爆炸 175

倍數遊戲——指數爆炸引發的難題 176

程序的設置選項 176

不能認為是「有限的」就不假思索 178

二分法查找——利用指數爆炸進行查找 178

尋找犯人的思考題 178

提示:先思考人數較少的情況 179

思考題答案   180

找出遞歸結構以及遞推公式 181

二分法查找和指數爆炸 183

對數——掌握指數爆炸的工具 184

什麼是對數   184

對數和乘方的關係 184

以2 為底的對數 186

以2 為底的對數練習 186

對數圖表 187

指數法則和對數 188

對數和計算尺 190

密碼——利用指數爆炸加密 193

暴力破解法   193

字長和安全性的關係 193

如何處理指數爆炸 195

理解問題空間的大小 195

四種處理方法 195

本章小結 196

第8章   不可解問題

——不可解的數、無法編寫的程序

本章學習內容 200

反證法 200

什麼是反證法 200

質數思考題   202

反證法的注意事項 203

可數 203

什麼是可數   203

可數集合的例子 204

有沒有不可數的集合 206

對角論證法   207

所有整數數列的集合是不可數的 207

所有實數的集合是不可數的 211

所有函數的集合也是不可數的 212

不可解問題   213

什麼是不可解問題 213

存在不可解問題 214

思考題   215

停機問題 215

停機 216

處理程序的程序 217

什麼是停機問題 217

停機問題的證明 219

寫給尚未理解的讀者 222

不可解問題有很多 223

本章小結 224

第9章   什麼是程序員的數學

——總結篇

本章學習內容 226

何為解決問題 229

認清模式,進行抽象化 229

由不擅長催生出的智慧 229

幻想法則 230

程序員的數學 231