信息學(xué)競賽冬令營集

猜想及其應(yīng)用內(nèi)容簡介前言類比猜想與熟悉的問題類比

巨人與鬼青蛙的煩惱與特殊的問題類比圓圈點(diǎn)（略）歸納猜想

青蛙過河（略）

排列問題結(jié)語猜想是一種主觀不充分似真推理。它建立在觀察、分析、聯(lián)想、歸納的基礎(chǔ)上前言提出猜想以小規(guī)模數(shù)據(jù)驗(yàn)證猜想證明結(jié)論YN修改猜想解決問題由此可見，猜想是在深入分析問題的基礎(chǔ)上，不懈探索、反復(fù)修正的過程。決不可能一蹴而就。提出猜想是整個(gè)過程的核心和重點(diǎn)。類比猜想、歸納猜想類比猜想事物A事物B性質(zhì)a性質(zhì)a性質(zhì)b性質(zhì)c性質(zhì)a’性質(zhì)b’性質(zhì)c’性質(zhì)d性質(zhì)d’類比、猜想引例：巨人與鬼（1）問題描述平面上有n個(gè)巨人和n個(gè)鬼（1<=n<=50）。每個(gè)巨人都有新式激光武器，可以對(duì)鬼進(jìn)行直線攻擊。然而這種武器有一種很大的弱點(diǎn)：兩個(gè)不同武器發(fā)出的激光不能交叉，否則就有爆炸的危險(xiǎn)。已知任意三個(gè)個(gè)體（包括巨人和鬼）都不在一條直線上，每個(gè)巨人負(fù)責(zé)攻擊一個(gè)鬼。當(dāng)然激光不能交叉?，F(xiàn)在的問題是：請你求出任意一種攻擊的方案。（即確定哪個(gè)巨人攻擊哪個(gè)鬼）引例：巨人與鬼（2）試題中是實(shí)際上是要確定巨人與鬼之間的一一對(duì)應(yīng)關(guān)系——這使我們很自然的聯(lián)想到了匹配。引例：巨人與鬼（3）構(gòu)圖：將巨人、鬼都抽象成為頂點(diǎn)。巨人組成的點(diǎn)集記為X，鬼組成的點(diǎn)集記為Y。在所有的x∈X、y∈Y之間連一條邊。任務(wù)：1、找到一個(gè)完備匹配。2、匹配邊不相交。假設(shè)有相交邊：OABCD方案1ABCD方案2OA+OB>AB，OC+OD>CDAD+CB>AB+CD方案1的“匹配邊長度總和”>方案2的“匹配邊長度總和”引例：巨人與鬼（4）方案2與方案１，“匹配邊的長度總和”減小了。故而：每一個(gè)“包含相交邊的完備匹配”都能夠轉(zhuǎn)換成為“匹配邊長度總和”更小的一個(gè)完備匹配——換句話說，“匹配邊長度總和”最小的完備匹配一定不包含相交邊！而我們要求的，正是一個(gè)不包含相交邊的完備匹配！建立二分圖最佳匹配模型：每條邊的權(quán)值設(shè)為它兩端頂點(diǎn)的歐幾里德距離。用匈牙利算法求最佳匹配模型。問題解決了。引例小結(jié)本題二分圖中的頂點(diǎn)具有特殊性：每個(gè)頂點(diǎn)都對(duì)應(yīng)于平面上的一點(diǎn)。因此，頂點(diǎn)與頂點(diǎn)之間不僅有邏輯關(guān)系，還有幾何直觀關(guān)系。正是由于充分利用了“幾何直觀”這一隱蔽關(guān)系才使得算法模型豁然開朗。例１：青蛙的煩惱(1)問題描述池塘里有n片荷葉（1<=n<=1000），它們正好形成一個(gè)凸多邊形。我們按照順時(shí)針方向?qū)⑦@n片荷葉順次編號(hào)為1,2,…,n。有一只小青蛙站在一號(hào)荷葉上，它想跳過每片荷葉一次且僅一次（它可以從所站的荷葉跳到另外任意一片荷葉上）。同時(shí)，它又希望跳過的總距離最短。請你編程，幫助小青蛙設(shè)計(jì)一條路線構(gòu)圖：首先將每片荷葉抽象成一個(gè)頂點(diǎn)，在任意兩個(gè)頂點(diǎn)x,y之間連一條邊，邊的權(quán)值設(shè)為頂點(diǎn)x與y的歐幾里德距離。模型：以1為起點(diǎn)的最短Hamilton鏈。例１：青蛙的煩惱(2)經(jīng)過觀察分析，發(fā)現(xiàn)構(gòu)造的圖：是一個(gè)完全圖。邊的權(quán)值等于它兩端頂點(diǎn)的歐幾里德距離。圖中的每個(gè)頂點(diǎn)對(duì)應(yīng)于平面上的一點(diǎn)。這些性質(zhì)和【引例】是多么相似?。。ㄟ@是表面上的類似）由于圖中的每個(gè)頂點(diǎn)對(duì)應(yīng)于平面上的一點(diǎn)，所以頂點(diǎn)之間不僅存在著由“邊”連接的邏輯關(guān)系，還存在著特殊的“幾何直觀”關(guān)系。利用好這個(gè)隱含的條件是解題的關(guān)鍵——這正與【引例】的基本特性不謀而合?。ㄟ@是本質(zhì)上的類似）解決【引例】時(shí)利用這個(gè)特性可以將“匹配邊總長度”不斷的縮短；而本題所求的問題也是一個(gè)最短路問題。例１：青蛙的煩惱(3)根據(jù)兩題諸多相似之處，我們猜測：

證明設(shè)從1出發(fā)，首先到達(dá)頂點(diǎn)A(2<A<n)。由于所有點(diǎn)在一個(gè)凸包上、2<A<n，所以除1、i以外的頂點(diǎn)必然被分作兩個(gè)部分，分別位于線段<1,A>的兩側(cè)。不失一般性，設(shè)從i出發(fā)經(jīng)過若干步到左側(cè)的頂點(diǎn)B，再到右側(cè)的頂點(diǎn)C，如下圖所示：C1AB實(shí)線表示一步到達(dá)；虛線表示多步到達(dá)猜想B最短Hamilton鏈中不存在相交的邊。

例１：青蛙的煩惱(4)我們可以做這樣的變換：1AB實(shí)線表示一步到達(dá)；虛線表示多步到達(dá)1AB實(shí)線表示一步到達(dá)；虛線表示多步到達(dá)CC變換后的鏈的長度，顯然比變換前的要短。所以變換前的方案必然不是最優(yōu)解。因此最優(yōu)Hamilton鏈肯定不存在相交邊。例１：青蛙的煩惱(5)…………12n以n為起點(diǎn)，遍歷{2..n}集合中的頂點(diǎn)一次且僅一次以2為起點(diǎn)，遍歷{2..n}集合中的頂點(diǎn)一次且僅一次…………12n…………12n從1出發(fā)，遍歷{1..n}中的頂點(diǎn)一次且僅一次，第一步必然是到2、或者n例１：青蛙的煩惱(6)設(shè)f[s,L,0]表示從s出發(fā)，遍歷{s..s+L-1}中的頂點(diǎn)一次且僅一次的最短距離；f[s,L,1]表示從s+L-1出發(fā)，遍歷{s..s+L-1}中的頂點(diǎn)一次且僅一次的最短距離。則：f[s,L,0]=min{dis(s,s+1)+f(s+1,L-1,0),dis(s,s+L-1)+f(s+1,L-1,1)}f[s,L,1]=min{dis(s+L-1,s+L-2)+f(s,L–1,1)dis(s+L-1,s)+f(s,L-1,0)}f[s,1,0]=0,f[s,1,1]=0求：f[1,n,0]“與熟悉的問題類比”小結(jié)

深入、透徹的分析模型。觀察、聯(lián)想。問題A算法A解決問題B類似算法B解決猜想與熟悉的問題進(jìn)行類比的基本步驟是：分析：分析問題的特征抽象出模型。聯(lián)想：與熟悉的，擁有類似特征、模型的問題類比。比較：確定類比對(duì)象后將兩者比較，分析異同。猜想：根據(jù)已知問題猜想新問題的解決方法。歸納猜想（1）歸納，是指通過對(duì)特例的分析來引出普遍結(jié)論的一種推理形式

前提歸納結(jié)論若干已知的個(gè)別、特殊事實(shí)

普遍性的陳述、判斷，猜想觀察、分析、聯(lián)想、概括的過程主觀的、不充分、似真推理必須經(jīng)過嚴(yán)格的邏輯論證歸納猜想（2）歸納猜想的一般步驟：列舉。將一些特殊的、簡單的、小規(guī)模的數(shù)據(jù)列舉出來。（這一步可以用手推，或者編寫簡單的搜索小程序）觀察。觀察列舉數(shù)據(jù)的規(guī)律。猜想。根據(jù)部分?jǐn)?shù)據(jù)猜想一般結(jié)論。證明。證明猜想的正確性。（一般采用數(shù)學(xué)歸納法）例4：排列問題（1）問題描述在整數(shù)1，2，……，N的排列中，有些排列滿足下面一個(gè)性質(zhì)A：該排列中除了最后一個(gè)整數(shù)以外的每一個(gè)整數(shù)后面都跟有（不必直接緊跟）一個(gè)同它相差為1的整數(shù)。例如：N=4，排列1432是具有性質(zhì)A的，而2431則不滿足。設(shè)有一個(gè)N個(gè)數(shù)的排列，已知其中P(P<=N)個(gè)位置上的數(shù)，求共有多少個(gè)這樣的排列——在P個(gè)位置上具有已知的數(shù)，且具有上述性質(zhì)A。例如：N=4，且已知第1位、第2位分別是1和4，則1432，1423就是這樣的兩個(gè)排列。例4：排列問題（2）當(dāng)n=5時(shí)，有16組滿足要求的序列（搜索出的解）：12345 1235412534 1254315234 1524315423 1543251234 5124351423 5143254123 5413254312 54321觀察發(fā)現(xiàn)：任何一個(gè)排列的后k位（1<=k<=n）是若干連續(xù)整數(shù)組成的集合例4：排列問題（3）任何一個(gè)排列的后k位（1<=k<=n）是若干連續(xù)整數(shù)組成的集合51243后5位：51243{1..5}后4位：1243{1..4}后3位：243{2..4}后2位：43{3..4}后1位：3{3}例4：排列問題（4）猜想1任何一個(gè)排列的后k位（1<=k<=n）是若干連續(xù)整數(shù)組成的集合。

證明約定序列的第i位用v[i]表示。設(shè)序列后x位（x>=1）是若干連續(xù)整數(shù)，這些整數(shù)構(gòu)成集合{s..t}。那么倒數(shù)第x+1位上的數(shù)v[n-x+1]必然等于p-1或者p+1（p∈{s..t}）。顯然v[n-x+1]∪{s..t}={s-1..t}或者{s..t+1}，還是若干連續(xù)整數(shù)。

猜想2如果一個(gè)排列的后k位（1<=k<=n）是若干連續(xù)整數(shù)組成的集合，則這個(gè)排列符合題目要求。證明約定該序列的第i位用v[i]表示。設(shè){v[n],v[n-1],…,v[n-k+1]}={s..t}。因?yàn)閧v[n-1],…,v[n-k+1]}也是若干連續(xù)整數(shù)的集合，所以v[n]=s或t。如果v[n]=s，那么必有：s+1∈{v[n-1],…,v[n-k+1]}如果v[n]=t，那么必有：t-1∈{v[n-1],…,v[n-k+1]}即這是一個(gè)滿足要求的序列。例4：排列問題（5）因此問題轉(zhuǎn)化為：求后k位（1<=k<=n）是若干連續(xù)整數(shù)組成的集合的排列總數(shù)（由1，2，……，N組成）。設(shè)g[s,r]表示滿足下面條件的序列C的總數(shù)：

C由集合[s..s+r-1]中的數(shù)組成，且后k位（1<=k<=r）是若干連續(xù)整數(shù)組成的集合。如果原問題中倒數(shù)第i個(gè)位置上的數(shù)已經(jīng)確定為x（1<=i<=r），那么C的倒數(shù)第i個(gè)位置上的數(shù)也要是x。例4：排列問題（6）

g[s+1,r-1]如果倒數(shù)第r位確定為s

g[s,r-1]如果倒數(shù)第r位確定為s+r-1g[s,r]=g[s,r-1]+g[s+1,r-1]如果倒數(shù)第r位不確定

0其他情況g[s,1]=1求：g[1,n]例４小結(jié)題目給定的條件比較復(fù)雜，很不便于轉(zhuǎn)化利用，極容易誘使選手走上“搜索”的“不歸路”。本題解決的關(guān)鍵在于通過對(duì)特例的觀察，歸納出兩個(gè)大膽的猜想，將復(fù)雜、不利于利用的條件，變換到一個(gè)我們熟悉的形式，為動(dòng)態(tài)規(guī)劃模型的建立打開了通道。結(jié)語其實(shí)我們解題時(shí)都在不知不覺的猜想——猜想問題的性質(zhì)；猜想模型的形式；猜想算法的內(nèi)容……猜想是