資源描述：
《淺談逆向思維在解題中的應用》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。
1、正難則反-淺談逆向思維在解題中的應用紹興市第一中學唐文斌【摘要》逆向思維是一種思考問題的方式，它有悖于通常人們的習慣，而正是這一特點，使得許多靠正常思維不能或是難于解決的問題迎刃而解。本文通過幾個例子，總結(jié)了逆向思維在信息學解題中的應用。逆向思維容斥原理參數(shù)搜索二分動態(tài)規(guī)劃記憶化引言我們先看一個簡單的問題：平面上有四個點，構(gòu)成一個邊長為1的正方形?，F(xiàn)在進行一種操作，每次可以選擇兩個點力和〃，把/關于E對稱到G然后把/去掉。求證：不可能經(jīng)過有限次操作得到一個邊長大于1的正方形操作后的結(jié)果是相當復雜的，如果我們從正面著手，很難證明命題。不妨從反面來看問題：觀察可以發(fā)現(xiàn)，每一步操作都是可逆的。即
2、，我們?nèi)绻梢园颜叫巫兇螅部梢园颜叫巫冃?。證明：不妨設四個頂點都是整點。假設我們可以通過有限次操作得到一個邊長大于1的正方形，那么我們把所有操作反過來對原正方形進行操作，我們可以得到一個邊長小于1的正方形。因為四個頂點都是整點，操作之后，點的坐標依然是整數(shù)。所以我們得到一個邊長小于1且四個點都是整點的正方形。這顯然不可能。所以假設不成立。命題得證。上面的例子說明了逆向思維在數(shù)學問題中的應用。山重水復疑無路，應用逆向思維，換個角度看問題，便柳暗花明又一村了。例一、DinnerIsReady1ZhejiangUniversityOnlineJudge1442(acm.zju.edu.cn
3、)題目大意:媽媽燒了〃根骨頭分給門個孩子們，第了個孩子有兩個參數(shù)Mim和Maxi,分別表示這個孩子至少要得到加巾根骨頭，至多得到Maxi根骨頭。輸入：第一行包含兩個數(shù)t7（0〈"W8）,J/（0〈必，表示孩子數(shù)量和骨頭的數(shù)量。接下來n行分別輸入Mini和Maxi（0WMinWMaxWM）輸出：輸出一個整數(shù)，表示媽媽有多少種分配方案（骨頭不能浪費，必須都分給孩子們）初步分析：該題模型很簡單，即求如下方程組的整數(shù)解的個數(shù)：/=iMin}0廠/?-]
4、1這是一個很經(jīng)典的組合問題，可由隔板原理得出答案。D=M/=1i=設K-=X+Mini則原方程組轉(zhuǎn)化為0
5、s,
6、無法計算，但是，岡可解！?。∥覀兿Ｍ?/p>
7、s,
8、的計算轉(zhuǎn)化到可解的岡。于是：Answer=
9、S,nS2nS3...nSH=
10、S-(S]+
11、S2
12、+...+Sn)+(S]cSr+S]cS?+?..+
13、s“_jcSn)—(-1)"*S]cc...cS.這是一種容斥原理的形式。至此，問題已經(jīng)解決。我們應用逆向思維，在原集合的模M不可解的情況下，通過可解的訓得到答案。并給出了一個基于容斥原理的算法。時間復雜度為0(2!*(n+M)).例二、GreedyPath1有/?個城市，被加條路連接著。最近成立了一些旅行社，在這些城市之間給旅行者們提供服務。旅行者從城市2?到城市丿需要付給旅行社的費用是G,j,需要的時間為7b。很多旅行者希望加入旅行社，但是旅行社只有一輛車。于是旅行社的老板決定組織一次旅行大賺一筆。公司里的專家需
14、要提供一條使得貪心函數(shù)尸⑹最大的回路G。F(G)等于總花費除以總時間。但是沒有人找到這樣的回路，于是公司的領導請你幫忙。輸入：第一行包含兩個數(shù)/7(3W/7W50),刃分別表示點數(shù)和邊數(shù)。接下來m行每行包含一條路的描述。輸入四個數(shù),A,B,Ca.b,Ta,b(O^G.^lOO,0W7LW100)輸出：如果不存在這樣的路，輸出0。否則輸出回路中包含的城市個數(shù)，然后依次輸出通過的城市的順序。如果有很多條這樣的路，輸出任意一條。初步分析：SaratovStateUniversityOnlineJudge236(acm.sgu.ru)題目要求是求一條回路，但不是邊權(quán)和最大或者最小，所以我們不能直接
15、使用經(jīng)典算法。設&二｛V,Q,S為G中所有回路C二（廠,刃）組成的集合。我們的目標是找到集合S中的一條回路使得F?取到最大值：F（C）=應用逆向思維：如果我們知道二（y*,E^wS是一條最優(yōu)回路，那么ycF（c*）=n工?Q-F（C*）x工?Te=0Zj心*人于是我們定義函數(shù):0&）二max（V，匕f-i—r~MewEewE我們做一個猜想：如果有o（f*）=0,那么存在C*=（叱鯛wS滿足yc嚴二厶ewE*我們認為c*就
