什麼樣的程式設計師數學能力最好(程式設計師的數學很難)
2023-10-25 17:53:47 1
經常聽到程式設計師吐槽「數學好難!」而程式設計師在編程中卻又少不了這數學基礎。編程的基礎是計算機科學,計算機科學的基礎就是數學。
我們都知道,只有學好數學才能打好編程的地基,寫出健壯的程序。但還是會有人說「但我數學就是不好啊」。特別是很多人「一碰到算式就跳過不讀」。坦率而言,我也曾這樣過。
但是看了《程式設計師的數學》以後,我很確信是我以前打開數學的方式不對,而讓我對數學產生了某種誤解。
《程式設計師的數學》由圖靈出版,由日本資深技術作家結城浩著作。書中儘可能減少了「大家不想看的算式」,也省去了過多的定義、定理和證明。單純是為幫助程式設計師更容易理解編程而寫的書。真的是受益匪淺,特別是在編程中的「數學思維」方面!下面我們根據書中的講解來重新認識一下編程中的數學吧。
結城浩著作還有《數學女孩》《數學女孩2:費馬大定理》《數學女孩3:哥德爾不完備定理》《數學女孩4:隨機算法》《圖解密碼技術(第3版)》,點擊連結可以試讀。
眾所周知,我們人類使用 10進位,計算機使用 2進位,這樣的按位計數法中,0在其中所起的作用是什麼?乍一看, 0僅僅是表示 「什麼都沒有 」的意思,而實際上它具有創建模式、簡化並總結規則的重要作用。
0 的故事——無即是有◎◎課前對話
老師:1,2,3 的羅馬計數法是I,II,III。
學生:加法很簡單嘛。I II,只要將3 個I 並排寫就行了。
老師:不過II III 可不是IIIII,而是V 喔!
學生:啊,是這樣啊!
老師:沒錯,如果數目變大,那數起來可就費勁啦!
小學一年級的回憶以下是小學一年級時發生的事,我依然記憶猶新。
「下面請打開本子,寫一下『十二』。」老師說道。於是,我翻開嶄新的本子,緊握住削尖了的鉛筆,寫下了這樣大大的數字。
老師走到我跟前,看到我的本子,面帶微笑親切地說:「寫得不對喔。應該寫成12 喔。」
當時我是聽到老師說「十二」,才寫下了10 和2。不過那樣是不對的。眾所周知,現在我們把「十二」寫作12。
而在羅馬數字中,「十二」寫作XII。X 表示10,I 表示1。II 則表示兩個並排的1,即2。也就是說,XII 是由X 和II 組成的。
如同「十二」可以寫作12 和XII,數字有著各種各樣的計數法。12 是阿拉伯數字的計數法,而XII 是羅馬數字的計數法。無論採用哪種計數法,所表達的「數字本身」 並無二致。下面我們就來介紹幾種計數法。
10 進位計數法下面介紹10 進位計數法。
什麼是10 進位計數法
我們平時使用的是10 進位計數法。
使用的數字有 0、1、2、3、4、5、6、7、8、9共 10種。這裡的「種」指的是數字的種類,用來說明10 進位和2 進位中數字複雜程度的差異。如2561 中包含四種數字,而1010 中只包含兩種數字。
數位有一定的意義,從右往左分別表示個位、十位、百位、千位……以上規則在小學數學中都學到過,日常生活中也一直在用,是眾所周知的常識。
在此權當複習,後面我們將通過實例來了解一下10 進位計數法。
分解2503
首先,我們以2503 這個數為例。2503 表示的是由2、5、0、3 這4 個數字組成的一個稱作2503 的數。
這樣並排的數字,因數位不同而意義相異。
2 表示「1000的個數」。5 表示「100的個數」。0 表示「10的個數」。3 表示「1 的個數」。綜上所述,2503 這個數是2 個1000、 5 個100、0 個10 和3 個1 累加的結果。
用數字和語言來冗長地說明有些無趣,下面就用圖示來表現。
如圖,將數字的字體大小加以區別,各個數位上的數字2、5、0、3 的意義便顯而易見了。
1000 是10×10×10,即 103(10 的3 次方),100 是10×10,即102(10 的2 次方)。因此,也可以寫成如下形式(請注意箭頭所示部分)。
再則,10 是101(10 的1 次方),1 是100(10 的0 次方),所以還可以寫成如下形式。
千位、百位、十位、個位,分別可稱作103 的位、102 的位、101 的位、100 的位。10 進位計數法的數位全都是10n 的形式。這個10 稱作10 進位計數法的基數或底。
基數10 右上角的數字——指數,是3、2、1、0 這樣有規律地順次排列的,這點請記住。
2 進位計數法下面講解2 進位計數法。
什麼是2 進位計數法
計算機在處理數據時使用的是2 進位計數法。從10 進位計數法類推,便可很快掌握它的規則。
使用的數字只有 0、1,共2 種。從右往左分別表示 1 位、2 位、4位、8 位……用2 進位計數法來數數,首先是0,然後是1,接下去……不是2,而是在1 上面進位變成10,繼而是11,100,101……
表1-1 展示了0 到99 的數的10 進位計數法和2 進位計數法。
表1-1 0 到99 的數的10 進位計數法和2 進位計數法
分解1100
在此,我們以2 進位表示的1100(2 進位數的1100)為例來探其究竟。
和10 進位計數法一樣,並排的數字,各個數位都有不同的意義。從左往右依次為:
1 表示「8 的個數」。1 表示「4 的個數」。0 表示「2 的個數」。0 表示「1 的個數」。也就是說,2 進位的1100 是1 個8、 1 個4、0 個2 和0 個1 累加的結果。這裡出現的8、4、2、1,分別表示23、22、21、20。即2 進位計數法的1100,表示如下意思。
如此計算就能將2 進位計數法的1100 轉換為10 進位計數法。
由此可以得出,2 進位的1100 若用10 進位計數法來表示,則為12。
基數轉換
接下來我們試著將10 進位的12 轉換為2 進位。這需要將12 反覆地除以2(12 除以2,商為6 ;6 再除以2,商為3 ;3 再除以2……),並觀察餘數為「1」還是「0」。餘數為0 則表示「除完了」。隨後再將每步所得的餘數的列(1 和0 的列)逆向排列,由此就得到2 進位表示了。
同樣地,我們試將10 進位的2503 轉換為2 進位計數法。
我們從圖1-2 可以知道2503 用2 進位表示為100111000111。各個數位的權重如下:
在10 進位中,基數為10,各個數位是以10n 的形式表現的。而2 進位中,基數為2,各個數位是以2n 的形式表現的。從10 進位計數法轉換為2 進位計數法,稱作10 進位至2進位的基數轉換。
計算機中為什麼採用2 進位計數法
計算機中一般採用2 進位計數法,我們來思考一下原因。計算機在表示數的時候,會使用以下兩種狀態。
開關切斷狀態開關連通狀態雖說是開關,但實際上並不需要機械部件,你可以想像成是由電路形成的「電子開關」。總之,它能夠形成兩種狀態。這兩種狀態,分別對應0 和1 這兩個數字。
開關切斷狀態 … 0開關連通狀態 … 11 個開關可以用0 或1 來表示,如果有許多開關,就可以表示為許多個0 或1。你可以想像這裡排列著許多開關,各個開關分別表示2 進位中的各個數位。這樣一來,只要增加開關的個數,不管是多大的數字都能表示出來。
當然,做成能夠表示0 ~ 9 這10 種狀態的開關,進而讓計算機採用10 進位計數法,這在理論上也是可能的。但是,與0 和1 的開關相比,必定有更為複雜的結構。
另外,請比較一下圖1-3 和圖1-4 所示的加法表。2 進位的表比10 進位的表簡單得多吧。
若要做成1 位加法的電路,採用2 進位要比10 進位更為簡便。
不過,比起10 進位,2 進位的位數會增加許多,這是它的缺點。例如,在10 進位中2503 只有4 位,而在2 進位中要表達同樣的數則需要100111000111 共12 位數字。這點從表1-2 中也顯而易見。
人們覺得10 進位比2 進位更容易處理,是因為10 進位計數法的位數少,計算起來不容易發生錯誤。此外,比起2 進位,採用10 進位能夠簡單地通過直覺判斷出數值的大小。人的兩手加起來共有10 個指頭,這也是10 進位更容易理解的原因之一。
不過,因為計算機的計算速度非常快,位數再多也沒有關係。而且計算機不會像人類那樣發生計算錯誤,不需要靠直覺把握數字的大小。對於計算機來說,處理的數字種類少、計算規則簡單就最好不過了。
讓我們來總結一下。
在 10進位計數法中,位數少,但是數字的種類多。→對人類來說,這種比較易用。
在 2 進位計數法中,數字的種類少,但是位數多。→對計算機來說,這種比較易用。
鑑於上述原因,計算機採用了2 進位計數法。
人類使用10 進位計數法,而計算機使用2 進位計數法,因此計算機在執行人類發出的任務時,會進行10 進位和2 進位間的轉換。計算機先將10 進位轉換為2 進位,用2 進位進行計算,再將所得的2 進位計算結果轉換為10 進位。
按位計數法什麼是按位計數法
我們學習了10 進位和2 進位兩種計數法,這些方法一般稱作按位計數法。除了10 進位和2 進位以外,還有許多種類的按位計數法。在編程中,也常常使用8 進位和16 進位計數法。
● 8 進位計數法
8 進位計數法的特徵如下:
使用的數字有 0、1、2、3、4、5、6、7共 8 種。從右往左分別為 80 的位、81 的位、82 的位、83 的位……(基數是8)● 16 進位計數法
16 進位計數法的特徵如下:
使用的數字有 0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F共 16種。從右往左分別為 16º 的位、16¹ 的位、16²的位、16³ 的位……(基數是16)在16 進位計數法中,使用A、B、C、D、E、F(有時也使用小寫字母a、b、c、d、e、f)來表示10 以上的數字。
● N 進位計數法
一般來說,N 進位計數法的特徵如下:
使用的數字有 0,1,2,3,…,N-1,共 N種。從右往左分別為 Nº 的位、N¹的位、N² 的位、N³的位……(基數是 N)例如,N 進位計數法中,4 位數a₃a₂a₁a。 為
不使用按位計數法的羅馬數字
按位計數法在生活中最為常見,因此人們往往認為這種方法是理所當然的。實際上,在我們身邊也有不使用按位計數法的例子。
例如,羅馬計數法。
羅馬數字至今還常常出現在鐘錶錶盤上。
還有,在電影最後放映的演職員名單中,也會出現表示年號的MCMXCVIII 等字母。
這也是羅馬數字。
羅馬計數法的特徵如下:
數位沒有意義,只表示數字本身沒有 0使用 I(1)、V(5)、X(10)、L(50)、C(100)、D(500)、M(1000) 來記數將並排的數字加起來,就是所表示的數。例如,3 個並排的I(III)表示3,並排的V 和I(VI)表示6,VIII 表示8。
羅馬數字的加法很簡單,只要將羅馬數字並排寫就可以得到它們的和。比如,要計算1 2,只要將表示1 的I 和表示2 的II 並排寫作III 就行了。但是,數字多了可就不太簡單了。
例如,計算3 3 並不是把III 和III 並排寫作IIIIII,而是將5 單獨拿出來寫作V,所以6 就應該寫作VI。CXXIII(123) 和LXXVIII(78) 的加法, 也不能僅僅並排寫作CXXIIILXXVIII,而必須將IIIII 轉換為V,VV 轉換為X,XXXXX 轉換為L,再將LL 轉換為C,如此整理最後得到CCI(201)。在「整理」羅馬數字的過程中,必須進行與按位計數法的進位相仿的計算。
羅馬計數法中還有「減法規則」。例如IV,在V 的左側寫I,表示5-1,即4(在鐘錶錶盤上,由於歷史原因也有將4 寫作IIII 的)。
讓我們試著將羅馬數字的MCMXCVIII 用10 進位來表示。
可以發現,MCMXCVIII 表示的就是1998。羅馬數字真是費勁啊!
指數法則10 的0 次方是什麼
在10 進位的說明中,我們講過「1 是10º(10 的0 次方)」,即10º=1。
也許有些讀者會產生以下疑問吧。
10² 是「2 個10 相乘」,那麼10º 不就是「0 個10 相乘」嗎?這樣的話,不應該是1,而是0 吧?
這個問題的核心在哪裡呢?我們來深入思考一下。問題在於「10ⁿ 是n 個10 相乘」這部分。在說「n 個10 相乘」時,我們自然而然會把n 想作1,2,3…。因此,在說「0 個10 相乘」時,卻不知道應該如何正確理解它的意義。
那麼,暫且拋卻「n 個10 相乘」這樣的定義方式吧。我們從目前掌握的知識來類推,看看如何定義10º 比較妥當。
眾所周知,10³ 是1000,10² 是100,10¹ 是10。
將這些等式放在一起,尋找它們的規律。
每當10 右上角的數字(指數)減1,數就變為原先的10 分之1。因此, 100 就是1。綜上所述,在定義10ⁿ(n 包括0)的值時可以遵循以下規則:
指數每減1,數字就變為原來的10 分之1。
10的-1 次方是什麼
不要將思維止步於10º 之處。對於10 的-1 次方,讓我們同樣套用這一規則(指數每減1,數字就變為原來的10 分之1)。
規則的擴展
首先讓我們做一個小結。
我們學習了10ⁿ 計數法的相關內容。
起初,我們把n 為1,2,3…時,即10¹,10²,10³…想作「1 個10 相乘」 、「2 個10 相乘」、「3 個10 相乘」……
然後,我們拋卻了「n 個10 相乘」的思維,尋找到了一個擴展規則:對於10ⁿ,n 每減1,就變成原來的10 分之1。
當n 為0 時,若套用「10ⁿ 為n 個10 相乘」的規則,著實比較費解。於是我們轉而求助於「n 每減1,就變成原來的10 分之1」的規則」,定義出10º 是1(因為10¹ 的10 分之
1 就是1)。
對2º 進行思考
讓我們用思考10º 的方法,也思考一下2º 的值吧。
由此可知,對於2ⁿ 來說,n 每減1,數值就變成原來的2 分之1。
2¹ 的2 分之1 是2º,那麼2º=1。
在這裡我想強調的是,不要將2º 的值作為一種知識去記憶,我們更需要考慮的是,如何對2º 進行適當的定義,以期讓規則變得更簡單。這不是記憶力的問題,而是想像力的問題。請記住這種思維方式:以簡化規則為目標去定義值。
2的-1次方是什麼
讓我們參照10的-1次方 的規則來思考2的-1次方。2º 除以2,得到的是2的-1次方,即2的-1次方=½。
「2 的-1 次方」在直覺上較難理解。鑑於規則的簡單化和一致性,2 的-1 次方可以定義為
綜上所述,可以總結出如下等式:
看了上面的等式之後, 你應該就更能體會10º 和2º 為什麼都等於1 了吧。
到這裡,我們給之前所說的「規則」取名為「指數法則」。指數法則的表達式為
即「N 的a 次方乘以N 的b 次方,等於N 的a b 次方」法則(但N ≠ 0)。
0 所起的作用0 的作用:佔位
例如,用10 進位表示的2503,它當中的0 起到了什麼作用呢? 2503 的0,表示十位「沒有」。雖說「沒有」,但這個0 卻不能省略。因為如果省略了0,寫成253,那就變成另一個數了。
在按位計數法中,數位具有很重要的意義。即使十位的數「沒有」,也不能不寫數字。這時就輪到0 出場了,即0 的作用就是佔位。換言之,0 佔著一個位置以保證數位高於它的數字不會產生錯位。
正因為有了表示「沒有」的0,數值才能正確地表現出來。可以說在按位計數法中0是不可或缺的。
0 的作用:統一標準,簡化規則
在按位計數法的講解中,我們提到了「0 次方」,還將1 特意表示成10º。使用0,能夠將按位計數法的各個數位所對應的大小統一表示成10ⁿ。
否則,就必須特別處理「1」這個數字。0 在這裡起到了標準化的作用。
如果從高到低各個數位的數字依次為
那麼10 進位的按位計數法就能用以下表達式來表示:
按位計數法的各個數位也能統一寫作
請注意:a右下角的k 和10的指數k 是一致的。
在上述表達式中,設n=3,a₃=2,a₂=5,a₁=0,a。=3,最後的結果是2503。
通過0 來明示「沒有」,能夠使規則簡單化。在許多情況下,規則是越簡單越好的。當你在面對問題的時候,是否也可以藉助0 來使問題簡單化呢?請想一想吧。
日常生活中的0
在我們的日常生活中,有時也會遇到像0 那樣表示「沒有」的情況。
●沒有計劃的計劃
我們常常使用日程表來管理計劃。在日程表中填入「案頭工作」、「出差」、「研討會」等計劃。那麼,和「0」相當的計劃是什麼呢?
例如,我們可以將沒有計劃的狀況設定成「空計劃」。通過在計算機的日程表中搜索「空計劃」,就能找到沒有計劃的日期。這樣一來,我們就既能搜索已有的計劃,又能搜索「空計劃」了。
還有,我們也可以將「預計不安排計劃(即,將該時間空出來)」當作0 來考慮。在日程表中先將「預計不安排計劃」的日程填寫佔位,然後再填寫需要安排工作的日程。這樣就不至於引起混亂。這正好與按位計數法中的0 起到的佔位作用相似。
●沒有藥效的藥
假設現在必須有規律地服用一種膠囊,每4 天停用1 次。也就是3 天服用,1 天停用,3 天服用,1 天停用,按照這種周期循環服藥,有難度吧?
靈機一動,妙法自然來。那就每天都吃藥吧。只是,每4 粒中有1 粒是「沒有藥效」的假膠囊。事先準備好標有日期的盒子,並在其中放入每天需要服用的藥,不是更好嗎?
這樣一來,就無需判斷「今天是服藥日還是停藥日」了。正因為有了「沒有」藥效的藥,才形成了「每天服用一粒膠囊」的簡單規則。
由此可見,這時的假膠囊與按位計數法中「0」所起的作用相同。
人類的極限和構造的發現重溫歷史進程
現今,10進位計數法已經深深地融入了我們的生活。然而這個過程經歷了幾千年的歷史,涉及全世界的各式文明。下面我們就來快速回顧一下數學表述法的這段歷史吧。
古埃及人使用5進位和10進位混合的計數法。5和10為一個單元,用記號標識,但是,他們的計數法不是按位計數法,當然也不存在0了。古埃及人將數字記在一種紙莎草紙(papyrus)上面。
巴比倫人在粘土板用菱形記號來表示數。他們使用1和10兩種菱形記號來表示1~59,並通過記號的所在位置來表示60ⁿ的數位。由此,10進位和60進位混合的按位計數法就誕生了。現在通用的1小時為60分鐘,1分鐘為60秒的時間換算就是源於巴比倫的60進位計數法。粘土板和紙莎草紙有所不同,很難在上面書寫多種不同的記號,因此,巴比倫人需要以儘可能少的記號來表示數。換句話說,也許正是因為粘土板的硬體限制,才促成了按位計數法的產生。
古希臘人不僅僅把數字當成運算工具,還在其中注入哲學真理。他們將圖形、宇宙、音樂與數字相關聯。
瑪雅人數數時從0開始,使用的是20進位計數法。
羅馬人使用5進位和10進位混用的羅馬數字,以5為一個單元,記做V。以10為一個單元記做X,同樣,將50、100、500、1000記做L、C、D、M。諸如IV表示4,IX表示9,XL表示40等,將數字列在左側作為減法的表示法是後來制定的,古羅馬時並不這樣使用。
印度人在引進巴比倫的按位計數法的同時,清楚地認識到0也是數字。而且,他們用的是10 進位計數法。現在我們使用的0、1、2、3、4、5、6、7、8、9,被稱為阿拉伯數字而不是印度數字,也許是因為將印度數字傳入西歐的是阿拉伯學者的緣故吧。
光是討論數字的表示法,就已經涉及了如此眾多的國家和文明了。
為了超越人類的極限
這裡,我們稍微思考一下更深層次的問題。為什麼人類需要發明計數法呢?在羅馬數字中,將1、2、3 記作I、II、III,將4 寫作IIII 或IV,5 寫作V。不過,將5 記作IIIII 好像也可以,卻又為何不那麼做呢?
答案顯而易見。原因是:在這種表示方法下,數越大就越難處理。比如,IIIIIIIIII 和IIIIIIIIIII 哪個大?不能馬上得知。而X 和XI 就能馬上比較得出孰大孰小。如果光將I 排成一排,若要表示較大的數字就非常不便了。因此先賢們創造出了「單元」的概念。
為了表示較大的數而創造出「單元」的概念,看似是一件非常理所當然的事情。而實際上在這裡卻給了我們極其重要的啟發。要表示「十二」,比起IIIIIIIIIIII,用XII 比較方便。若使用按位計數法,寫成「12」則更方便。我們可以從中獲得哪些啟發呢?
那就是:將大問題分解為小「單元」。
如何高效地表示一個較大的數,對於古代的先人們來說是個重要的問題。對此歷史給出了兩種方法:10 進位計數法和按位計數法。由於人類的能力有限,因此必須開動腦筋,想出簡便的計數法。如果人類對數有更高的認知能力,就不會發展出以「單元」表示的計數法了吧。
如今,人類發展到了能夠發射火箭、分析基因信息的階段,我們所處理的數據呈爆炸性增長。這樣,按位計數法也顯得力不從心了。1000000000000 和10000000000000 哪個大呢?很難一眼就看出來。這時,指數表示法顯得異常重要。
剛才的兩個數字若寫作10的12次方 和10的13次方,便能一眼看出後者較大。指數表示法是著眼於0的個數的計數法。
問題不光停留在計數法上。在現代,我們使用計算機來解決人類難以處理的大規模問題。我們竭盡全力地編寫程序,絞盡腦汁地思考如何在短時間內解決大規模問題。「將大問題分解為小『單元』」的解決辦法,至今依然適用。「要解決大問題,就將它分解成多個小『單元』。如果小『單元』還是很大,那就繼續分解成更小的『單元』,直到問題最終解決。」這種方法至今依然通用。比如在編寫大程序的時候,一般會分解成多個小程序(模塊)來開發。
總結本文通過按位計數法,思考了0 所起的作用。0 雖然沒有實際的數量,卻起到了佔位的作用。正因為有了0,才能夠實現簡單的按位計數法。
另外,我們還學習了指數法則的相關內容。尤其是思考了如何定義0 次方才更為妥當。一定要在保持簡單規則的前提下擴展概念,請大家一定要理解這點。
◎◎課後對話
學生:樂譜上的休止符也像0 呢。
老師:正是!它明確地表示不發音!
學生:0 與其說是「空」,還不如說是「填空」更恰當。因為它的作用是佔位。
老師:說得對!這稱作佔位符。
學生:佔位符?
老師:有了佔位符才會產生模式,有了模式才會產生簡單的規則。
學生:原來如此!正是通過0 這個佔位符,才能實現簡單的按位計數法!
————
《程式設計師的數學》
面向讀者
本書面向程式設計師介紹了編程中常用的數學知識,藉以培養初級程式設計師的數學思維。本書主要面向的讀者是程式設計師。不過若你對編程或數學感興趣,讀起來也會一樣有意思。
你不需要精通數學。書中不會出現∑和∫等很難的算式,因此自認為數學不太好的讀者也完全可以閱讀。閱讀本書只需具備四則運算(+- ×÷)和乘方(23=2×2×2)等基礎知識。除此以外的知識在書中皆有說明。
如果你對數字和邏輯感興趣,可能會更喜歡本書。
你也不需要精通編程。不過如果稍有一些編程經驗,可能會更容易理解本書內容。書中有個別例子是用C 語言寫的程序,不過即使不懂C 語言也不妨礙理解。
主要內容
書中講解了二進位計數法、邏輯、餘數、排列組合、遞歸、指數爆炸、不可解問題等許多與編程密切相關的數學方法,分析了哥尼斯堡七橋問題、高斯求和方法、漢諾塔、斐波那契數列等經典問題和算法。引導讀者深入理解編程中的數學方法和思路。本書適合程序設計人員以及編程和數學愛好者閱讀。
目錄
前言
第1章 0故事——無即是有
第2章 邏輯——真與假的二元世界
第3 章 餘數 ——周期性和分組
第4 章 數學歸納法 ——如何徵服無窮數列
第5章 排列組合——解決計數問題的方法
第6章 遞歸——自己定義自己
第7章 指數爆炸——如何解決複雜問題
第8章 不可解問題——不可解的數、無法編寫的程序
第9章 什麼是程式設計師的數學——總結篇
相關圖書:《程式設計師的數學2:概率統計》《程式設計師的數學3:線性代數》
,