一、0的故事?

——無(wú)即是有

1、例子

按位計(jì)數(shù)法：無(wú)論是二進(jìn)制還是十進(jìn)制，一個(gè)數(shù)字的每一位代表有幾個(gè)該位基位值。例如二進(jìn)制1100

指數(shù)法則：對(duì)于10^n, n每減一就變成原來(lái)的十分之一抢野。這種定義是一種思維方式的運(yùn)用：以簡(jiǎn)化規(guī)則為目標(biāo)去定義值。

2各墨、總結(jié)0的作用

占位：例如2503中的0指孤，代表這個(gè)數(shù)字沒有十位，0的占位使得高位數(shù)字不會(huì)錯(cuò)位欲主。

統(tǒng)一標(biāo)準(zhǔn)邓厕，簡(jiǎn)化規(guī)則：

生活中的占位應(yīng)用：如沒有計(jì)劃的計(jì)劃，某一天沒有安排則視為空計(jì)劃即0扁瓢，作為計(jì)劃的一種占位详恼，這樣就方便搜索查找。又如沒有藥效的藥引几，一種藥每4天停用一次則可制作假膠囊直接每天服藥即可：

問題分解法：數(shù)越大越難處理昧互，將大問題分解為小單元。

二伟桅、邏輯

——真與假的二元世界

1敞掘、基本邏輯表達(dá)式

邏輯的基本思路：兼顧完整性和排他性，即無(wú)遺漏無(wú)重復(fù)楣铁。要注意邊界處玖雁。

分析工具：真值表、文氏圖盖腕、卡諾圖

異或的否定即為相等赫冬。常用邏輯表達(dá)式：

2、德摩根律

對(duì)偶性：

3溃列、借助邏輯表達(dá)式思考簡(jiǎn)化問題

例：

第一步：定義基本命題

第二步：根據(jù)規(guī)則改寫命題為邏輯表達(dá)式

第三步：用卡諾圖化簡(jiǎn)表達(dá)式

4劲厌、包含未定義的三值邏輯表達(dá)式

即邏輯表達(dá)式有true、false听隐、undefined三種可能的取值补鼻。

三、余數(shù)

——周期性和分組

1、星期數(shù)計(jì)算

余數(shù)就是分組的一種方法风范，面對(duì)難以計(jì)算的大數(shù)字時(shí)咨跌，發(fā)現(xiàn)它的循環(huán)或規(guī)律就易于解決。

找規(guī)律從小數(shù)一點(diǎn)點(diǎn)看起硼婿，發(fā)現(xiàn)規(guī)律：

易看出按0的個(gè)數(shù)來(lái)看每6個(gè)循環(huán)一次虑润，可以容易地算出10^n的一天星期幾。發(fā)現(xiàn)沒有星期日加酵，說(shuō)明10^n無(wú)法除盡7。按0的個(gè)數(shù)思考問題是將大數(shù)化小的對(duì)數(shù)化方法哭当。

2猪腕、乘方的思考

找出1234567^987654321的個(gè)位數(shù)。

先通過(guò)試算找規(guī)律钦勘，能影響兩個(gè)數(shù)乘方結(jié)果的個(gè)位數(shù)的只有這兩個(gè)數(shù)的個(gè)位數(shù)陋葡。即只需要找出7的乘方的個(gè)位數(shù)規(guī)律即可。

發(fā)現(xiàn)個(gè)位數(shù)是1彻采、7腐缤、3、9的循環(huán)肛响，故將987654321 / 4得到余數(shù)1岭粤，答案7

總結(jié)：涉及難以直接計(jì)算的大數(shù)字時(shí)，先用小數(shù)試算找到規(guī)律特笋，然后用余數(shù)將大數(shù)化小解決剃浇。

3、黑白棋通信——奇偶校驗(yàn)

隨機(jī)排列7個(gè)黑白棋猎物，后加一枚虎囚。觀眾選擇翻轉(zhuǎn)某顆棋或不都翻，問觀眾的選擇蔫磨。

只要事先設(shè)定8個(gè)棋子如黑棋為總為偶數(shù)個(gè)，可能情況為：

故最終可以確定是否翻轉(zhuǎn)過(guò)棋子。這就是奇偶校驗(yàn)的應(yīng)用襟锐。徒弟是發(fā)送方忽媒，魔術(shù)師是接收方，觀眾的翻轉(zhuǎn)就是噪音煤惩，發(fā)送方多放的一枚棋子為奇偶校驗(yàn)位嫉嘀。接收方通過(guò)檢查奇偶性判斷是否發(fā)生通信錯(cuò)誤。事實(shí)上奇偶校驗(yàn)將數(shù)字分為兩個(gè)集合魄揉，7枚棋子128種可能剪侮，其中一半黑棋為偶數(shù)，另一半為奇數(shù)，徒弟添加的棋子起到了標(biāo)識(shí)屬于哪組的作用瓣俯。

4杰标、找人

12個(gè)月前人在G村，后隨機(jī)移動(dòng)12次彩匕，問最后在A處的概率腔剂。

從較小的的數(shù)入手，不要按路線思考驼仪，按目的地分類

發(fā)現(xiàn)奇數(shù)次移動(dòng)掸犬，人在A、C绪爸、F湾碎、H，偶數(shù)次在B奠货、D介褥、E、G递惋，故12個(gè)月后不可能在A處柔滔。解答過(guò)程將8個(gè)村分為奇偶兩組，奇數(shù)村移動(dòng)一次到偶數(shù)萍虽，偶數(shù)一次回奇數(shù)睛廊，每次可知人在奇數(shù)村還是偶數(shù)村。

5贩挣、鋪設(shè)草席

草席不能分兩半喉前，問這個(gè)房間能否由草席鋪滿。

首先王财，若房間格子為奇數(shù)則肯定不能鋪滿卵迂。共62個(gè)，需進(jìn)一步分析绒净。整個(gè)房間左上角和右下角各缺一塊造成不規(guī)整见咒，既然是偶數(shù)，若草席可以分半則可鋪滿挂疆。故不能鋪滿的可能是作為整體的草席要么超邊界改览，要么缺的兩塊不在一起。故考慮涂色分組：

一張草席半黑半白缤言，故兩色應(yīng)該數(shù)量相等宝当，所以不能鋪滿。

要進(jìn)行有效的奇偶校驗(yàn)必須找到合適的分類方法

6胆萧、一筆畫證明

哥尼斯堡七橋問題簡(jiǎn)化為下圖庆揩，證明小寫字母代表的橋不能一次走遍俐东。

反復(fù)實(shí)驗(yàn)中發(fā)現(xiàn)：要通過(guò)一點(diǎn)，這點(diǎn)必須至少有“入”订晌、“出”兩條邊虏辫，每過(guò)此點(diǎn)一次則減少兩條邊。隨意取起點(diǎn)出發(fā)锈拨，則起點(diǎn)度數(shù)減1砌庄，途經(jīng)點(diǎn)度減2，不管經(jīng)過(guò)幾次度數(shù)奇偶性不變奕枢，終點(diǎn)度減1娄昆。假設(shè)這個(gè)過(guò)程完成了一筆畫，有以下兩種情況：

1缝彬、起點(diǎn)也是終點(diǎn)稿黄。畫成意味著邊走邊減的結(jié)果使所有頂點(diǎn)度數(shù)為0（偶），途經(jīng)點(diǎn)減的過(guò)程中奇偶性不變跌造，故為偶點(diǎn)。起終點(diǎn)為同一點(diǎn)族购，故同一點(diǎn)度數(shù)減2變?yōu)?壳贪，也是偶點(diǎn)。結(jié)論：在起點(diǎn)終點(diǎn)相同的一筆畫中寝杖，圖中的頂點(diǎn)都是偶點(diǎn)违施。

2、起點(diǎn)不是終點(diǎn)瑟幕。同理可知途經(jīng)點(diǎn)為偶點(diǎn)磕蒲，只有起點(diǎn)和終點(diǎn)為奇點(diǎn)。

總結(jié)為命題：可以一筆畫成——圖中所有點(diǎn)為偶點(diǎn)或有2個(gè)奇點(diǎn)只盹。反之也成立辣往。

根據(jù)命題說(shuō)明七橋不能一筆畫成。解答過(guò)程的思考方法是：觀察頂點(diǎn)邊數(shù)時(shí)著眼點(diǎn)不在數(shù)本身殖卑，而在奇偶性站削。想詳細(xì)研究事物時(shí)往往陷入“想正確把握所有細(xì)節(jié)”的思維，較之正確的把握有時(shí)準(zhǔn)確的分類更有效孵稽，發(fā)現(xiàn)了周期性和奇偶性就能將大問題轉(zhuǎn)化為小問題解決许起。

四、數(shù)學(xué)歸納法

——如何征服無(wú)窮數(shù)列

1菩鲜、高斯求和

用變量n园细，將1—100歸納為1—n得出公式：

用數(shù)學(xué)歸納法證明公式正確性。數(shù)學(xué)歸納法步驟為：

這種思路類似推到多米諾骨牌接校，只需2個(gè)步驟無(wú)論牌多長(zhǎng)都會(huì)倒：確保第一塊牌倒下猛频；確保第k塊牌倒下能使k+1塊倒下。

2、奇數(shù)求和

3伦乔、錯(cuò)誤實(shí)例：黑白棋

證明投擲的黑白棋顏色一定相同厉亏。n = 1顯然成立，假設(shè)n = k時(shí)成立, n = k + 1時(shí)有：

證明錯(cuò)誤之處：當(dāng)k = 1時(shí)兩組沒有共同棋子

循環(huán)不變式：在編寫循環(huán)時(shí)要找到讓每次循環(huán)都成立的邏輯表達(dá)式烈和，即循環(huán)不變式爱只。相當(dāng)于數(shù)學(xué)歸納法證明的斷言。編寫循環(huán)一要確保達(dá)到目的招刹，二要確保適時(shí)停止恬试，循環(huán)不變式確保一，循環(huán)范圍確保二疯暑。

五训柴、排列組合

——解決計(jì)數(shù)問題的方法

1、計(jì)數(shù)

要不重不漏：認(rèn)清計(jì)數(shù)對(duì)象的性質(zhì)即抽象化思考妇拯，找出一般規(guī)律幻馁，將計(jì)數(shù)對(duì)象與整數(shù)對(duì)應(yīng)起來(lái)。

加法法則：集合中沒有重復(fù)元素時(shí)

容斥原理：兩集合的并集數(shù)量等于兩集合的數(shù)量和減兩集合交集數(shù)量越锈。

乘法原理：兩集合元素的組合數(shù)量等于集合數(shù)量乘積仗嗦。

2、排列/置換/組合

置換：將n個(gè)事物按順序進(jìn)行排列甘凭。即 n稀拐！

排列：n個(gè)事物取一部分進(jìn)行排列。n張牌取k張排列：

組合：n個(gè)事物取一部分不考慮順序排列丹弱。

即置換與組合相結(jié)合就是排列德撬。置換表示3張牌的交替排列方法，組合表示3張牌的取法躲胳，結(jié)合就是取出3張牌進(jìn)行交替排列蜓洪。

3、實(shí)例

藥品調(diào)劑：A坯苹、B蝠咆、C三種藥品每種至少取一粒，一共取100粒北滥，不考慮順序有多少種方法刚操？

從小規(guī)模的同問題思考：隔板法。

撲克牌排列：至少一端是王牌的排法再芋，不區(qū)分大小王菊霜。

方法一：首先按區(qū)分大小王，左端為王牌有2 * 4济赎！鉴逞，右端同樣记某，兩端都是王有2！ * 3构捡！液南。根據(jù)容斥原理有：左 + 右 - 兩，最后除以重復(fù)度2勾徽！滑凉。

方法二：所有排列數(shù) - 兩端都不是王。5喘帚！- 3*2 * 3畅姊！，最后除以重復(fù)度2吹由！若未。

六、遞歸

——自己定義自己

1倾鲫、漢諾塔

從3個(gè)圓盤的情況試粗合，找出規(guī)律。發(fā)現(xiàn)一般步驟為：

總結(jié)為遞推公式：

求出解析式：發(fā)現(xiàn)H(0)—H(6)為0乌昔、1舌劳、3、7玫荣、15、31大诸、63...發(fā)現(xiàn)規(guī)律H（n）= 2 ^n - 1捅厂，用數(shù)學(xué)歸納法證明其正確性。

寫出程序：

總結(jié)思路：先從少量圓盤試移资柔，為了找出一般方法焙贷，使用n - 1層漢諾塔來(lái)表示 n 層漢諾塔的觀點(diǎn)考慮問題：

簡(jiǎn)單問題比復(fù)雜問題易解，遇到難題想辦法將問題轉(zhuǎn)換為較為簡(jiǎn)單的同類問題贿堰，即遞歸的思考方式：在問題中找出遞歸結(jié)構(gòu)辙芍，找出同類簡(jiǎn)單問題當(dāng)已知條件用。然后根據(jù)遞歸建立遞推公式羹与，能進(jìn)一步總結(jié)出解析式最好故硅。

2、遞歸和歸納

遞歸和歸納本質(zhì)相同纵搁，都是將復(fù)雜問題簡(jiǎn)單化吃衅，只是方向不同。遞歸是“從一般性前提推出個(gè)別性結(jié)論”腾誉，歸納是“從個(gè)別性前提推出一般性結(jié)論”徘层。

菲波那切數(shù)列：兔子繁殖問題峻呕，不要直接想第n天共有幾只：n - 1天前存在的兔子第n天還在；n - 2 天前出生的兔子在第n天繁殖1只趣效。由此得出遞歸式瘦癌，再補(bǔ)上基底轉(zhuǎn)為遞推公式。

擺磚塊跷敬、填音符讯私、爬樓梯等多種變形問題實(shí)質(zhì)都是菲波那切數(shù)列。

3干花、楊輝三角

說(shuō)明組合數(shù)可以通過(guò)反復(fù)計(jì)算相鄰兩數(shù)的和得出妄帘，比算階乘要高效。每一點(diǎn)的數(shù)是從頂點(diǎn)到此點(diǎn)的路徑數(shù)

可以根據(jù)楊輝三角的規(guī)律得出組合數(shù)的遞歸表達(dá)：

該式數(shù)學(xué)理論解釋：n中選k的組合數(shù) = n - 1 選 k - 1的組合數(shù) + n - 1 選 k 的組合數(shù)池凄。即選不選第n個(gè)數(shù)為第k個(gè)抡驼。

找出復(fù)雜問題隱含的遞歸結(jié)構(gòu)：

七、指數(shù)爆炸

——如何解決復(fù)雜問題

1肿仑、指數(shù)爆炸的特點(diǎn)

指數(shù)爆炸會(huì)使問題的規(guī)模迅速擴(kuò)大致盟，運(yùn)用對(duì)數(shù)思想解決問題則能快速降低問題規(guī)模。例如二分查找每次比較能確定的范圍尤慰，遞歸結(jié)構(gòu)為：

相反馏锡，可以利用指數(shù)爆炸的思想設(shè)計(jì)密碼，密碼每設(shè)多一位可能的密碼多一倍伟端。

2杯道、如何處理指數(shù)爆炸

1、理解問題空間的大小责蝠。任何問題只要具備：判斷是否已成功破解的方法党巾；按順序試解的步驟，就可以用暴力破解法霜医。

2齿拂、處理的4種方法

極力求解：增強(qiáng)計(jì)算機(jī)性能

變相求解：轉(zhuǎn)換成簡(jiǎn)單問題求解，尋找更好的算法

近似求解：不求完全解答肴敛，用估算或模擬器求解署海，有助于實(shí)際應(yīng)用

概率求解：求解時(shí)使用隨機(jī)數(shù)，可能在短時(shí)間解決医男，也可能找不到答案

八砸狞、不可解問題

——不可解的數(shù)，無(wú)法編寫的程序

1镀梭、反證法

矛盾就是命題P和其否定形式都成立趾代。

例：證明質(zhì)數(shù)是無(wú)窮的。

首先假設(shè)質(zhì)數(shù)有限丰辣，其集合為2撒强、3禽捆、5、7...P飘哨，將這所有質(zhì)數(shù)相乘后+1得到Q胚想。Q顯然比所有質(zhì)數(shù)都大，由假設(shè)知Q不是質(zhì)數(shù)芽隆。但任何質(zhì)數(shù)都不能整除Q浊服，由定義知Q是質(zhì)數(shù)，故矛盾胚吁。所以質(zhì)數(shù)是無(wú)窮的牙躺。

2、可數(shù)

元素可按一定規(guī)律不重不漏地?cái)?shù)出來(lái)腕扶，即與正整數(shù)一一對(duì)應(yīng)孽拷，可一一列出（可以無(wú)限）“氡В可數(shù)集合的例子：有限集合脓恕，0以上的偶數(shù)集合，整數(shù)窿侈、有理數(shù)集合炼幔，程序集合等

3、對(duì)角論證法——不可數(shù)集合

無(wú)論怎樣都會(huì)漏元素的集合史简，例如整數(shù)數(shù)列集合等乃秀，證明可用對(duì)角論證法。

如此得出的數(shù)列a1圆兵、a2...是整數(shù)數(shù)列跺讯，但不包含在這個(gè)“所有整數(shù)數(shù)列表”中。因?yàn)樗c“所有整數(shù)數(shù)列表”中任一整數(shù)數(shù)列相比至少有一處不同衙傀。與“所有整數(shù)數(shù)列表”矛盾，因此不可數(shù)萨咕。此外统抬，所有實(shí)數(shù)集合、函數(shù)集合都不可數(shù)危队。

4聪建、不可解問題

不包含在“程序可解決問題集合”中的問題。

停機(jī)問題：某程序在給定數(shù)據(jù)下茫陆，是否會(huì)在有限時(shí)間內(nèi)結(jié)束運(yùn)行金麸。

九、總結(jié)

何為解決問題：認(rèn)清模式簿盅，進(jìn)行抽象化挥下。從小問題著手揍魂，找到一般規(guī)律。