我唯一知道的事就是我一無所知 ----蘇格拉底

本書是數(shù)學大師馬丁.伽德納所著专肪，源自于一本科教雜志，為什么這樣的集高學術(shù)水平和高施教水平的老師不能出現(xiàn)在中國寸士？大多數(shù)中國人還是和以前一樣檐什，抱著所謂的國學成天研究，喜歡研究人與人之間的關系弱卡，對于自然科學的探索乃正，對于大自然的好奇心，這正是我們國人所缺乏的婶博，在如今的現(xiàn)代化社會中瓮具，科技的發(fā)展主要來自于自然科學，而科技已經(jīng)是一個國家發(fā)展壯大的最主要的推動力凡人，中國社會需要那種對于科學的熱愛名党，那種求真的態(tài)度

組合數(shù)學

推測一件事情發(fā)生的概率，有三種方法
古典概率模型：基本空間由有限個元素或基本事件組成挠轴，其個數(shù)記為n传睹，每個基本事件發(fā)生的可能性是相同的。若事件A包含m個基本事件岸晦，則定義事件A發(fā)生的概率為p（A）=m/n
幾何概率模型：隨機試驗中的基本事件有無窮多個欧啤，且每個基本事件發(fā)生是等可能的睛藻，這時就不能使用古典概率，于是產(chǎn)生了幾何概率邢隧。幾何概率的基本思想是把事件與幾何區(qū)域?qū)暧。脦缀螀^(qū)域的度量來計算事件發(fā)生的概率，布豐投針問題是應用幾何概率的一個典型例子

“組合數(shù)學 + 古典概率模型"
為求概率提供了相當不錯的思路

巧妙的借用

這個方法最早是從老頭分馬那兒看到的:一個富翁倒慧，留下17匹馬按摘，分給3個兒子，大兒子分1/2纫谅，二兒子分1/3炫贤，三兒子分1/9。聰明的老頭牽了一頭馬來付秕，分完后照激，又牽了回去，大家各得其所

分馬問題雖然巧妙盹牧，給人一種思維啟發(fā)俩垃，但是不具有普遍性，高中學數(shù)學的時候汰寓，多項式的因式分解就經(jīng)常通過先加一個數(shù)口柳，然后減去同一個數(shù)來達到目的，這才是借用的普遍用法有滑，這種方法改變了的條件的狀態(tài)跃闹，使之利于求解

本書中有這樣一個有意思的問題：有一次n人參加的一對一的淘汰賽，估計出比賽輪空的總?cè)藬?shù)毛好。這種問題當然可以在紙上通過一步一步的演算得出結(jié)果望艺，但是如果n比較大，那會是相當耗時肌访，書上有一個很妙的解法找默，先找到一個最小的m
，使得m + n = A（A是2的x次方）吼驶，把n和m看成是二進制惩激，m中1的個數(shù)，就是最終的解

為什么這樣解可以呢蟹演？

首先风钻，我們通過巧妙的借用m來使得出現(xiàn)了A這樣一個數(shù)，因為A是2的x次方酒请，所以A場比賽就可以無人輪空的完整進行下去骡技，現(xiàn)在我們就可以把A看成兩個小組，第一組有n個人羞反，第二組有m個人布朦，m組每輪比賽可能會多出一個人毛萌，也可能剛剛好，如果是多出一個人喝滞，那么把這個人和第一組輪空的那個人進行比賽，這樣就能使無人輪空的進行完所有比賽膏秫，這樣m中多出的人數(shù)就是第一組n人中輪空的人數(shù)右遭，即二進制表示的m中1的個數(shù)

這個巧妙的借用沒有改變問題的形態(tài)，只是從問題的反面進行了求解

有時候我們單獨對于一個解無從下手缤削，只能通過巧妙的借用窘哈，達到一個有利于求解的狀態(tài)，根據(jù)這個“借用”和“狀態(tài)”來求所解

奇偶消除

在《編程之美》上有這么一道題：假如已知一個數(shù)在數(shù)組中出現(xiàn)的次數(shù)超過數(shù)組個數(shù)的一半亭敢，用最快的速度找出這個數(shù)滚婉。書中給出的解法就是建立兩個空間，A和B帅刀，有兩個屬性让腹，一是記錄存放的是哪個元素，一個是記錄存放該元素的個數(shù)扣溺，初始值都為0骇窍，代表為空，遍歷一遍數(shù)組锥余，如果A或B為空則把數(shù)組元素放入其中一個腹纳，并計A或B的值為1，如果出現(xiàn)重復的元素驱犹，則在相應的A或B上加1嘲恍，當A和B都不為空時，A和B同時減一雄驹，這樣遍歷一遍數(shù)組佃牛，最后留在A或B中的元素就是所求解，這里雖然沒有用到奇偶消除医舆，但是把放在A和B中不同元素想象成正負離子吁脱，也算是異曲同工

這里用了一種巧妙的方法簡化問題的規(guī)模，同時彬向，不改變問題的性質(zhì)兼贡，這與本書中的“鋪磚理論”如出一轍，在一個地板磚上娃胆，有偶數(shù)個小方塊遍希，每次鋪磚必須覆蓋到四鄰域內(nèi)的連續(xù)兩個小方塊，怎樣快速判斷是否能完整鋪完

書中給出的解法：
在四鄰域內(nèi)依次標記小方塊為紅色和白色的里烦，由于每次鋪磚必須覆蓋到四鄰域內(nèi)的連續(xù)兩個小方塊凿蒜，這樣同色的方塊就可以看成具有相同的奇偶性禁谦，每次覆蓋必須是一對具有相反的奇偶性才行，這樣如果最初紅色和白色的個數(shù)不一樣（如19,21）废封，所以不能進行奇偶配對州泊，最后留下會兩個同色的方塊，則肯定無法按要求鋪完漂洋，這樣就能把問題規(guī)模最后規(guī)約到判斷最后一對方塊的奇偶性

運用奇偶性理論可以做兩件事
消除問題規(guī)模：鋪磚問題
判斷問題狀態(tài)是否發(fā)生改變：奇偶校驗遥皂；反過來想，利用某些我們指定的操作刽漂，保持問題的狀態(tài)不變（翻硬幣問題演训，如果每次必須翻一對，那么正面和反面的奇偶性將是保持不變）

數(shù)的表示

古羅馬人對于數(shù)的表示很呆板贝咙，簡單的用和來表示一個數(shù)样悟，聰明的印度人創(chuàng)造了十進制，數(shù)的表示清晰易懂庭猩，后來計算機的出現(xiàn)窟她，由于硬件的限制，又帶來二進制蔼水，其實在生活中礁苗，有很多事情也可以用二進制來表示，其中的1和0就代表是與非

最經(jīng)典的一個問題就是1000瓶藥徙缴，有一瓶毒藥试伙，有十只老鼠，藥效發(fā)作是一天于样，需要在這一天里面來判斷哪瓶藥是毒藥
小老鼠吃不吃藥就是一個1和0的問題疏叨，這樣可以有2的10次方中表達，每種表達就能對應某一瓶藥

如果一系列東西中某些東西只允許出現(xiàn)一次（即可以出現(xiàn)穿剖，或者不能出現(xiàn)）蚤蔓，用二進制表示是最恰當?shù)模热缯f用一系列數(shù)字表達0~14糊余，每個數(shù)字最多只能出現(xiàn)一次秀又，那么最簡潔的表達方式就是 1 2 4 8

圖形

切蛋糕

對于一個平面的蛋糕，切n刀贬芥，最多能切出多少塊吐辙？
因為第k刀與之前的每一刀最多只有一個交點，所以第k+1刀最多和已存在的k刀有k個交點蘸劈，再加上邊緣的兩個交點昏苏，共k+2個交點，這樣就會產(chǎn)生k+1條線，每條線把之前的切塊一分為二贤惯，那么就會產(chǎn)生k + 1個新塊

切第一刀洼专，會有兩塊
如果切了n刀后的，切出的塊數(shù)位m孵构，那么n+1刀切出后的塊數(shù)就應該是 m + （n + 1 + 1）

所以f(n)表示切n刀后的塊數(shù)
f(n) = 1, n == 1
f(n) = f（n -1） + n + 1 , n > 1

又是一個歸納法Ｆㄉ獭！颈墅！

邏輯推理

集體智慧推理

基于邏輯推理的歸納法

在多人參與的一個事件中蜡镶，有一種推理，是基于參與這個事件的所有人有著和計算機一樣的準確思維

例1精盅，有三個人，頭上可能會是紅色帽子或者藍色帽子谜酒，如果某人看到了誰戴了紅色帽子叹俏，就舉手，如果你是其中一位僻族，看見了其余兩人舉手了（自己也舉手說看到了紅帽）粘驰，當過了片刻還沒有人說自己頭上是什么帽子，要求猜出頭上的帽子

有三個人的時候述么，分別為A,B,C蝌数，可以一步一步的進行簡單的推理，如果我是A度秘，我如果頭上是藍帽子顶伞，那么其余兩個人就會看到一個是藍色一個是紅色，B看到C也舉手了剑梳，說明他看到了紅色唆貌，這樣他就會知道自己頭上戴的是紅色，但是他不知道垢乙，所以我頭上的是紅色

這種情況可以推論到n個人锨咙，即有n個人，頭上可能會是紅色帽子或者藍色帽子追逮，如果某人看到了誰戴了紅色帽子酪刀，就舉手，如果你是其中一位钮孵，看到所有人都舉手了（自己也舉手說看到了紅帽）骂倘，當過了片刻還沒有人說自己頭上是什么帽子，要求猜出頭上的帽子

這里就要用到歸納法巴席，如果要用到歸納法稠茂，一般是首先確定f(n)代表的是什么，然后確定f(n +１)與f(n)的關系,在這里，是一種很特別的歸納法睬关，f(n)并不能直接表示某個具體的解诱担，而是表示一個事實：f(n)表示的是共有n +１個人，其中一個人看到了n頂紅帽（自己也舉手說看到了紅帽）电爹，但是大家都不暫時知道自己的帽子蔫仙，那么他自己戴的肯定是紅帽

當有n個人時，一個人看到了其余的全是紅帽（自己也舉手說看到了紅帽）丐箩，但是過了片刻還沒有人說自己頭上是什么帽子摇邦，這說明自己的問題可以簡化為當自己的帽子為藍色時，求f(n - 1),這樣一直就可以簡化成f(2)即最開頭的那樣屎勘，這樣就得出了解

例2施籍，即有n個人，頭上可能會是紅色帽子或者藍色帽子（肯定有一頂是藍色的）概漱，每一輪主持人都會問偷偷問每個人丑慎，他知不知道自己頭上帽子的顏色，如果有人發(fā)現(xiàn)了瓤摧，則主持人宣布游戲介紹竿裂，問如果有m只藍帽子（m < n）時，這個游戲能進行多少輪照弥？

如果只有一頂藍帽子腻异，那么第一天就會被人發(fā)現(xiàn)，游戲結(jié)束
設如果有n頂藍帽子这揣，那么在第n天會被人發(fā)現(xiàn)悔常，游戲結(jié)束

這時如果有n+1頂藍帽子，即當一個人A看到了n頂藍帽子给赞，過去了n天都沒人說自己發(fā)現(xiàn)了頭頂?shù)念伾庀@時A在第n+1天肯定會知道自己頭上的顏色，游戲結(jié)束

所以最終答案是進行m輪

上面兩個題都是以每個人十分聰明和理性塞俱，即按照自己設想的來姐帚，大家達到一種共識，因為一個人第一題看到有k只藍帽子障涯，他需要進行判斷的是自己也是藍帽子罐旗，如果沒有之前的共識，即“如果有n頂藍帽子唯蝶，那么在第n天發(fā)現(xiàn)”九秀，他是不可能猜到自己的帽子的
，這類問題只有理論價值

操作設計

能量消耗

許多問題是問最少多少次能夠完成粘我，這就可以用能量消耗法來考慮鼓蜒，不考慮具體的操作痹换，先確定總?cè)蝿樟繛锳，每次操作能減少任務量為B都弹，這樣A/B就為最少的次數(shù)

例1娇豫，舉辦一個淘汰賽，總參加人數(shù)為n畅厢，為最少多少場比賽能夠決出第一名

首先不考慮怎么安排比賽冯痢，最后留一個人，總?cè)蝿樟繛閚 - 1框杜，因為每場比賽會淘汰一個人浦楣，每次操作能減少任務量為1，這樣結(jié)果就為 (n - 1)/1 就為最少的次數(shù)

例2咪辱，考牛排問題振劳，一個烤架只能放n塊牛排，現(xiàn)有m塊牛排(m > n)油狂，牛排兩面都需要烤熟历恐，牛排從生到熟需要k分鐘，問所有牛排烤熟至少需要多少分鐘

總?cè)蝿樟繛?m * 2选调， 每次減少的任務量為n夹供，所有所需時間為 k * ( (m * 2) / n )(如果不是整除灵份，那么還得加1)
;

例3仁堪，有n個醫(yī)生，m個病人填渠，每個醫(yī)生都會給每個病人看一種傳染蚕夷簟（醫(yī)生和護士都可能得病）氛什，看病的時候手套內(nèi)側(cè)和醫(yī)生接觸莺葫，手套外側(cè)和病人接觸，問要使病人之間不傳染枪眉，醫(yī)生之間不傳染捺檬，至少需要多少副手套

這個題如果一個個推的話就很麻煩，其實每個人分配一副手套的一側(cè)贸铜，這樣需要的手套數(shù)就為 （m + n)/ 2

上面三個問題其實都需要一個前提堡纬，就是證明 “每次操作能減少任務量B，不多不少蒿秦，就是B烤镐，同樣，某次減少任務量后棍鳖，面對的情況（即問題模型）和減少前是一樣的”