數(shù)學(xué)與程序設(shè)計(jì)

數(shù)學(xué)與程序設(shè)計(jì)清華大學(xué)胡淵鳴程序設(shè)計(jì)中的數(shù)學(xué)基礎(chǔ)數(shù)學(xué)知識(shí)組合數(shù)學(xué)數(shù)論計(jì)算幾何與復(fù)雜度理論基礎(chǔ)數(shù)學(xué)知識(shí)數(shù)學(xué)證明為什么要進(jìn)行數(shù)學(xué)證明？增強(qiáng)對(duì)題目性質(zhì)的信心嚴(yán)謹(jǐn)?shù)乃季S防止無(wú)用功“誒呀這題第一步我就想錯(cuò)了”如何進(jìn)行數(shù)學(xué)證明？邏輯推理利用計(jì)算機(jī)驗(yàn)證例證法

機(jī)器驗(yàn)證(對(duì)拍)

小范圍內(nèi)成立？

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

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

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

反證法

博君一笑博君一笑博君一笑博君一笑貪心與調(diào)整法如何證明一個(gè)方案是最優(yōu)的？考慮異于這個(gè)方案的任意方案，總可以通過(guò)調(diào)整使得它們更優(yōu)于是他們都不是最優(yōu)方案例：排序不等式，排隊(duì)接水問(wèn)題基本計(jì)數(shù)原理加法原理不相交集合的并乘法原理笛卡爾積排列與組合

組合意義

組合數(shù)的性質(zhì)（組合論證）

可重復(fù)組合

方程的解數(shù)I

方程的解數(shù)II擴(kuò)展:要求每個(gè)變量為正整數(shù)利用上面的結(jié)論或者隔板法模型轉(zhuǎn)換把一個(gè)計(jì)數(shù)對(duì)象轉(zhuǎn)化成與其數(shù)目完全一樣且結(jié)構(gòu)更優(yōu)的計(jì)數(shù)對(duì)象簡(jiǎn)化問(wèn)題如何確定兩個(gè)集合大小一樣?存在一一對(duì)應(yīng)(雙射)Catalan數(shù)

Catalan數(shù)

Catalan數(shù)

Catalan數(shù)

Catalan數(shù)

Catalan數(shù)

Catalan數(shù)

Catalan數(shù)

Catalan數(shù)

Catalan數(shù)問(wèn)：二叉樹(shù)的數(shù)目與出棧序列的數(shù)目是否有關(guān)系？嘗試構(gòu)造一一對(duì)應(yīng)思考：樹(shù)與棧有什么聯(lián)系？構(gòu)造成功！Catalan數(shù)

Catalan數(shù)

容斥原理

容斥原理

錯(cuò)位排列全排列，但每個(gè)數(shù)不能排在自己原來(lái)的位置上利用容斥原理在所有排列中占多大比例?Stirling數(shù)

Stirling數(shù)

Stirling數(shù)

方程的解數(shù)III

堆的計(jì)數(shù)

堆的計(jì)數(shù)

不相鄰組合

不相鄰組合

Hanoi雙塔問(wèn)題Hanoi

Tower

NOIpHanoi雙塔問(wèn)題相同大小的盤(pán)子有兩個(gè)，輸出最優(yōu)解的步數(shù)。證明？初等數(shù)論例題NOIp2009細(xì)胞分裂博士正在培養(yǎng)細(xì)胞樣本?，F(xiàn)在有N種細(xì)胞，編號(hào)從1~N，一個(gè)第i種細(xì)胞經(jīng)過(guò)1秒鐘可以分裂為Si個(gè)同種細(xì)胞（Si為正整數(shù)）。他需要選取某種細(xì)胞的一個(gè)放進(jìn)培養(yǎng)皿，讓其分裂。一段時(shí)間以后，再把培養(yǎng)皿中的所有細(xì)胞平均分入M個(gè)試管，形成M份樣本。Hanks博士的試管數(shù)M很大，可以表示為m1的m2次方，即M=m1^m2，其中m1，m2均為基本數(shù)據(jù)類(lèi)型可以存儲(chǔ)的正整數(shù)。注意，整個(gè)實(shí)驗(yàn)過(guò)程中不允許分割單個(gè)細(xì)胞，比如某個(gè)時(shí)刻若培養(yǎng)皿中有4個(gè)細(xì)胞，Hanks博士可以把它們分入2個(gè)試管，每試管內(nèi)2個(gè)，然后開(kāi)始實(shí)驗(yàn)。但如果培養(yǎng)皿中有5個(gè)細(xì)胞，博士就無(wú)法將它們均分入2個(gè)試管。此時(shí)，博士就只能等待一段時(shí)間，讓細(xì)胞們繼續(xù)分裂，使得其個(gè)數(shù)可以均分，或是干脆改換另一種細(xì)胞培養(yǎng)。在選定一種細(xì)胞開(kāi)始培養(yǎng)后，他總是在得到的細(xì)胞“剛好可以平均分入M個(gè)試管”時(shí)停止細(xì)胞培養(yǎng)?，F(xiàn)在博士希望知道，選擇哪種細(xì)胞培養(yǎng)，可以使得實(shí)驗(yàn)的開(kāi)始時(shí)間最早。1≤N≤10000，1≤m1≤30000，1≤m2≤10000，1≤Si≤2,000,000,000。NOIp2005循環(huán)

平面計(jì)算幾何入門(mén)點(diǎn)與向量

向量的基本運(yùn)算

向量的點(diǎn)積與叉積

前后與左右

向量的點(diǎn)積與叉積

前后與左右

直線(xiàn)與線(xiàn)段

直線(xiàn)與線(xiàn)段

直線(xiàn)的交點(diǎn)

單位向量

經(jīng)典問(wèn)題線(xiàn)段是否相交點(diǎn)到直線(xiàn)的距離判斷圓和圓相交，求交點(diǎn)點(diǎn)是否在多邊形內(nèi)部（凹、凸）直線(xiàn)與圓的交點(diǎn)求包圍一個(gè)點(diǎn)集的最小凸多邊形凸包求凸包

JSOI合金合金是指由鐵、銅、鋁三種金屬按一定比率混合而成的混合物給定幾種合金作為原料，再給定幾種合金作為產(chǎn)品，求使用給定的原料能否生產(chǎn)出這些產(chǎn)品。如果只有2種金屬呢？NOIp2011Car的旅行路線(xiàn)

NOIp2011Car的旅行路線(xiàn)輸入只給定每個(gè)矩形的3個(gè)頂點(diǎn)，如何求出第四個(gè)？接下來(lái)如何做？算法的復(fù)雜度漸進(jìn)復(fù)雜度的幾個(gè)記號(hào)

漸進(jìn)復(fù)雜度的幾個(gè)記號(hào)

判斷題

“常數(shù)”

復(fù)雜度類(lèi)什么是??,????,??????,????????????？P(polynomialtime)NP(non-deterministicpolynomialtime)NPC(plete)NP-hard(AtlastashardasN