數(shù)學歸納法與解題之道

1、IOI2009國家集訓隊論文演示 張昆瑋,數(shù)學歸納法與解題之道,山西省實驗中學　張昆瑋,道,IOI2009國家集訓隊論文演示 張昆瑋,貪心,構造,優(yōu)化,如此之多的算法，是怎樣想到的？這些算法巧誠巧矣，可正確性怎么證明呢？,引言,道生一，一生二，二生三，三生萬物。,——老子：《道德經》,數(shù)學歸納法,IOI2009國家集訓隊論文演示 張昆瑋,概覽,2.在證明算法正確性上的應用貪心算法其他算法,3.在構造性算法中的應用數(shù)據(jù)結

2、構的恢復性構造策略與解決方案的構造,4.數(shù)學歸納法與算法優(yōu)化巧妙選擇歸納對象力求完善歸納基礎慎重選擇歸納方向適當加強歸納假設,5.啟發(fā)作用與美學價值,6.問題與缺陷理論上是否欠完備應用上是否較繁瑣不適用的問題,1.關于數(shù)學歸納法簡短的回顧基本的定理、概念與方法是總結更是探索,例5（線性結構）Set Cover例6（樹狀結構）Roman Roads,√,IOI2009國家集訓隊論文演示 張昆瑋,難,缺乏固定套路依

3、賴于具體的數(shù)據(jù)結構,通用靈活適用于各種數(shù)據(jù)結構,易,構造性問題,,,數(shù)學歸納法,,IOI2009國家集訓隊論文演示 張昆瑋,【例5】Set Cover——數(shù)據(jù)結構的恢復性構造,子集覆蓋問題定義為選出盡量少的子集，使已知集合中的每個元素至少屬于其中的一個。 線段覆蓋問題定義為選出盡量少的整點，使給定的每條線段上都至少有其中的一個。 以整點為子集，所有包含這個整點的線段為子集中的元素，可以把一

4、個線段覆蓋問題歸約到子集覆蓋問題。如果給定一個由線段覆蓋問題歸約成的子集覆蓋問題，該怎么解決呢？,IOI2009國家集訓隊論文演示 張昆瑋,線段覆蓋問題,在數(shù)軸上選出盡量少的整點給定的每條線段上必須至少有其中的一個按左端點排序后有簡單的貪心算法,,,,,,,,,,√,√,√,√,√,,,,,IOI2009國家集訓隊論文演示 張昆瑋,轉化成子集覆蓋問題,整點作為集合（實際上只需每線段的右端點）所有包含此整點的線段為其元素一般的子集

5、覆蓋問題→NP完全,,,,,,,,,,,,1,2,3,4,5,1,2,2,3,3,4,4,5,5,,,,IOI2009國家集訓隊論文演示 張昆瑋,怎么辦？,恢復線性結構,直接搜索,Tips：只需要恢復線段的位置關系和每個線段的右端點,IOI2009國家集訓隊論文演示 張昆瑋,定義線段的位置,線段的位置即為其中點的位置兩線段距離即為其中點的距離兩線段距離可以使用對應集合運算求出,,兩線段必須相交！,IOI2009國家集訓隊論文演示 張

6、昆瑋,到底是“＋”還是“－”？,問題：如何拓展連通分量？,我們把問題分為連通分量來處理兩個連通分量之間線段距離可以任意，不影響結論每個連通分量的第一條線段位置任意,,IOI2009國家集訓隊論文演示 張昆瑋,調整歸納假設,只有一條線段時方向無關緊要初始時刻選擇不同的方向只會使最終的結果互為軸對稱而已。其他情形中為了判斷方向，我們需要調整歸納假設,,IOI2009國家集訓隊論文演示 張昆瑋,同側？異側？,,X與B在A的同側的充分必

7、要條件是他們在A之內的部分存在包含關系,,,IOI2009國家集訓隊論文演示 張昆瑋,同側？異側？,,X與B在A的同側的充分必要條件是他們在A之內的部分存在包含關系,,IOI2009國家集訓隊論文演示 張昆瑋,線段的右端點,,,所有與A相交、在A右側的線段與A的公共點,問題解決,IOI2009國家集訓隊論文演示 張昆瑋,小結,以上解題過程用庖丁解牛的方法步步推進，將問題分為多個部分，逐一化解數(shù)學歸納法靈活的歸納假設為主要問題的求解提供