程序設(shè)計(jì)中常用的計(jì)算思維方式

程序設(shè)計(jì)中常用的計(jì)算思維方式算法思維邏輯思維第1章正確認(rèn)識(shí)和處理整體與部分的關(guān)系概述：“整體”與“部分”是一對(duì)雖然對(duì)立、但并非僵化不變的概念。在一定條件下，“部分”可以看作“整體”，“整體”又可以看作是另一個(gè)“整體”的“部分”，兩者相互依存和影響?！罢w”與“部分”又可以相互轉(zhuǎn)化的?！罢w”的問(wèn)題可以分割成“部分”來(lái)處理，“部分”的問(wèn)題也可以通過(guò)“整體”來(lái)解決。整體實(shí)現(xiàn)的關(guān)鍵是準(zhǔn)確地應(yīng)用必要條件A、選擇有助于簡(jiǎn)化問(wèn)題、變難為易的必要條件這里面就是說(shuō)我們要在堅(jiān)持“簡(jiǎn)化問(wèn)題、變難為易”的原則下，盡力尋找“精確”的必要條件，以縮小求解范圍，提高出解速度。當(dāng)碰到一道難題時(shí)，總是嘗試從最簡(jiǎn)單的特殊情況入手，找出有助于簡(jiǎn)化問(wèn)題、變難為易的必要條件，逐漸深入，最終分析歸納出一般規(guī)律。B、合成必要條件，從整體結(jié)構(gòu)上優(yōu)化在搜索和動(dòng)態(tài)規(guī)劃中，必要條件有期很好的應(yīng)用價(jià)值。一般地，對(duì)于深度優(yōu)先搜索和廣度優(yōu)先搜索，如何限制搜索范圍、減少搜索量最有效的手段是“剪枝”。然而由于問(wèn)題的錯(cuò)綜復(fù)雜，所以我們要找最高效的優(yōu)化條件，來(lái)提高程序的效率。所以我們可以嘗試從多個(gè)側(cè)面分析尋找必要條件，把問(wèn)題分解，根據(jù)各部分的本質(zhì)聯(lián)系，將各方面的必要條件綜合起來(lái)使用。C、必要條件與原有模型比較、更新算法上面所說(shuō)的兩種優(yōu)化程序的策略其實(shí)是都是在“縮小求解范圍”，改進(jìn)在有算法的基礎(chǔ)上進(jìn)行的，屬于局部?jī)?yōu)化。然而精確選擇揭示問(wèn)題本質(zhì)的必要條件，與原有的模型比較，小結(jié)：必要條件是邏輯推到的理論依據(jù)，也是思考過(guò)程的一種取向。解題時(shí)，若能尋找出精確的必要條件，一方面能幫助我們揭示問(wèn)題的本質(zhì)，設(shè)計(jì)出正確的算法；另一種方面又能“縮小求解范圍”，提高算法效率。因此，準(zhǔn)確地應(yīng)用必要條件是整體實(shí)現(xiàn)的關(guān)鍵。所以我們要在堅(jiān)持“具體問(wèn)題具體分析”的原則，不拘一格，靈活處理；在分析問(wèn)題時(shí)，要勤于思考，善于發(fā)現(xiàn)。整體思考的一個(gè)重要角度是“守恒”A、從具體問(wèn)題中抽象出守恒量守恒量需要通過(guò)聯(lián)想和化歸思維將其抽象出來(lái)，從問(wèn)題本身的結(jié)構(gòu)中抽象出守恒量。B、根據(jù)問(wèn)題的本質(zhì)構(gòu)造守恒量有時(shí)候，如果能為每一個(gè)元素標(biāo)一個(gè)權(quán)值，就可以揭示問(wèn)題“守恒”規(guī)律。在總價(jià)值不變的前提下，或許能將整個(gè)問(wèn)題轉(zhuǎn)化成一個(gè)簡(jiǎn)單的、或者是經(jīng)典的問(wèn)題。比如構(gòu)造成Fibonacci數(shù)列等。C、在交互式問(wèn)題中構(gòu)造變化中的不變量考慮可能出現(xiàn)的各種情況和最優(yōu)策略，找變化中的不變量，運(yùn)用“守恒”法尋找解題的突破口小結(jié)：守恒是問(wèn)題分析問(wèn)題的一種思維方式一種整體意識(shí)和解題方法，通過(guò)聯(lián)想和化歸思維將其抽象出來(lái)。提高整體實(shí)現(xiàn)效率的基本途徑是“充分利用有效信息”和“壓縮冗余信息”計(jì)算過(guò)程中充分利用有效信息：在記憶化搜索和動(dòng)態(tài)規(guī)劃中充分利用信息，特別指出在動(dòng)態(tài)規(guī)劃中改變狀態(tài)的表示含義對(duì)優(yōu)化問(wèn)題是個(gè)很好的策略。還有在數(shù)值計(jì)算中充分利用信息。通過(guò)“壓縮法”消除冗余的圖形和數(shù)據(jù)信息在圖論的問(wèn)題中，通過(guò)采用“縮點(diǎn)法”，將具有等價(jià)意義的一類頂點(diǎn)壓縮成一個(gè)頂點(diǎn)，來(lái)簡(jiǎn)化問(wèn)題；還有就是壓縮冗余信息。改善整體性能狀態(tài)的基礎(chǔ)是處理好細(xì)節(jié)問(wèn)題細(xì)節(jié)是算法整體的關(guān)鍵部分，對(duì)整體起到“牽一發(fā)而動(dòng)全身”的作用，是算法整體性能狀態(tài)的基礎(chǔ)。在程序設(shè)計(jì)中，細(xì)節(jié)的處理十分重要，應(yīng)該對(duì)其取“舉輕若重”的態(tài)度。許多事例證明：有時(shí)細(xì)節(jié)決定成敗。按照對(duì)算法的影響的性質(zhì)和程度，可把細(xì)節(jié)分為如下幾種情況：、影響正確性的細(xì)節(jié)問(wèn)題。在解題過(guò)程中雖然已經(jīng)找到解決方法，卻不能通過(guò)全部測(cè)試數(shù)據(jù)，往往就是這類的細(xì)節(jié)處理不當(dāng)所致。、嚴(yán)重影響時(shí)間復(fù)雜度的細(xì)節(jié)。這類細(xì)節(jié)相當(dāng)隱蔽，往往不為人所注意。但是這種細(xì)節(jié)影響時(shí)間復(fù)雜度的階，處理得好與不好往往會(huì)使程序的時(shí)間效率有質(zhì)的區(qū)別。3、輕微影響復(fù)雜度的細(xì)節(jié)。這類細(xì)節(jié)問(wèn)題對(duì)時(shí)間復(fù)雜度沒(méi)有根本性影響，僅僅對(duì)時(shí)間復(fù)雜度的系數(shù)有影響。1.4.1必須解決導(dǎo)致錯(cuò)誤結(jié)果的細(xì)節(jié)問(wèn)題雖然已經(jīng)找到正確的解法，但在程序?qū)崿F(xiàn)的過(guò)程中，由于疏于細(xì)節(jié)而導(dǎo)致“功虧一簣”的事比比皆是，這種細(xì)節(jié)問(wèn)題對(duì)整體的危害性最大。、常見(jiàn)的錯(cuò)誤類型類型1：語(yǔ)法錯(cuò)誤類型2：書(shū)寫錯(cuò)誤類型3：輸入輸出格式的錯(cuò)誤類型4：數(shù)據(jù)范圍的錯(cuò)誤類型5：變量未初始化的錯(cuò)誤類型6：中間運(yùn)算越界類型7：局部變量與全局變量同名造成概念混亂類型8：ifThenElse語(yǔ)句混亂。類型9:實(shí)數(shù)比較出錯(cuò)。在比較兩個(gè)實(shí)數(shù)是否相等時(shí)，如果直接用等號(hào)，往往會(huì)造成錯(cuò)誤。這是浮點(diǎn)去得存在精度誤差所造成的。解決辦法是使用兩數(shù)差的絕對(duì)值與一個(gè)相對(duì)極小量進(jìn)行比較，例如，如果abs（a-b）＜1e-8，則可認(rèn)為a==b。、在程序運(yùn)行的過(guò)程中跟蹤錯(cuò)誤動(dòng)態(tài)查錯(cuò)是指通過(guò)跟蹤程序的執(zhí)行過(guò)程，核對(duì)輸出結(jié)果來(lái)發(fā)現(xiàn)錯(cuò)誤。動(dòng)態(tài)查錯(cuò)的技巧可分兩大部分：測(cè)試用例的設(shè)計(jì)和測(cè)試的方法。爭(zhēng)取降低得法時(shí)間復(fù)雜度的階提高程序的時(shí)間效率的最明顯的標(biāo)志，是降低算法時(shí)間復(fù)雜度的階數(shù)，而時(shí)間復(fù)雜度的階數(shù)，并不是非得更新算法不可。有時(shí)，只要在程序的某些細(xì)節(jié)上做一些調(diào)整和修改，同樣可以得到“牽一發(fā)而動(dòng)全身”的效果。注意降低算法時(shí)間復(fù)雜度的系數(shù)這類細(xì)節(jié)對(duì)算法的整體影響雖然不算太大，但往往在關(guān)鍵的時(shí)候，時(shí)間復(fù)雜度系數(shù)的大小對(duì)算法的效率也有比較明顯的影響。因此，應(yīng)該盡可能地優(yōu)化細(xì)節(jié)處理，精益求精，使算法的時(shí)間復(fù)雜度的系數(shù)降低到一個(gè)比較理想的程度。第2章構(gòu)造性思維“構(gòu)造法”解題，就是構(gòu)造數(shù)學(xué)模型或方法解決問(wèn)題，解題的思維方式就是所謂構(gòu)造性思維?！皹?gòu)造法”解題的思路或步驟：、審題：了解題目的來(lái)龍去脈，弄清哪些量是已知的（輸入），需要求什么（輸出），數(shù)據(jù)規(guī)模如何，等等。這是解決問(wèn)題的前提。、建模：建立一個(gè)能夠簡(jiǎn)潔地表達(dá)出原型本質(zhì)的模型。、分析和解決模型：分析模型的正確性。如果模型正確，則設(shè)計(jì)算法解決模型，解決模型的過(guò)程是否順利，取決于所建模型的正確性和可解性如何。如果模型錯(cuò)誤或不可解，則重新審題。、編程實(shí)現(xiàn)。模型的基本概念當(dāng)面對(duì)一個(gè)新問(wèn)題時(shí)，通常的想法是通過(guò)分析，不斷的轉(zhuǎn)化和轉(zhuǎn)換，得到本質(zhì)相同的熟悉的、或抽象的、簡(jiǎn)單的一個(gè)問(wèn)題，這就是化歸思想。把初始的問(wèn)題或?qū)ο蠓Q為原型，把化歸后的相對(duì)定型的模擬化或理想化的對(duì)象稱為模型。模型的一般特點(diǎn)與功能與實(shí)際問(wèn)題相比，模型有以下幾個(gè)性質(zhì)和特點(diǎn)：、等價(jià)性：模型和原型必須是本質(zhì)相同的。、抽象性：模型是實(shí)際問(wèn)題的一種抽象，它去除了實(shí)際問(wèn)題中與問(wèn)題的求解無(wú)關(guān)的部分，簡(jiǎn)明地體現(xiàn)了問(wèn)題的本質(zhì)。、高效性：模型中各個(gè)量之間的關(guān)系更為清晰，容易從中找到規(guī)律，從而提高求解的效率。由于這一點(diǎn)是由模型的抽象性決定的，因此模型的抽象化程度對(duì)模型效率的高低有重要的影響。、可推廣性：模型可以推廣到具有相同性質(zhì)的一類問(wèn)題中。換句話說(shuō)，解決了一個(gè)模型就解決了一類實(shí)際問(wèn)題。一般的，模型具有三大功能：、解釋功能：用模型說(shuō)明事物發(fā)生的原因。、判斷功能：用模型判斷認(rèn)識(shí)的可靠性。、預(yù)見(jiàn)功能：利用模型的知識(shí)、規(guī)律和未來(lái)的發(fā)展，為人們的行為提供指導(dǎo)或參考。.1.2模型的一般分類在ACM/ICPC競(jìng)賽中，常用的模型有圖論模型、數(shù)學(xué)模型和規(guī)劃（整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃）模型。1、圖論模型通過(guò)圖論化，本來(lái)復(fù)雜、凌亂的數(shù)據(jù)關(guān)系可變得簡(jiǎn)潔、明了，問(wèn)題求解的思路因此而變得相對(duì)清晰。在許多情況下，可直接套用經(jīng)典算法。通常，數(shù)據(jù)之間的離散關(guān)系錯(cuò)綜復(fù)雜可以考慮圖論模型化。建立圖論模型必須注意：模型和原型的本質(zhì)越接近越好。2、組合數(shù)學(xué)模型各種各樣的計(jì)數(shù)問(wèn)題都可考慮建立組合數(shù)學(xué)模型，最常用的組合數(shù)學(xué)模型是遞歸關(guān)系。雖然不探討問(wèn)題的數(shù)學(xué)規(guī)律而直接利用遞歸的回溯法計(jì)數(shù)，從理論上講是可行的，但先求解組合數(shù)學(xué)的遞歸模型再計(jì)數(shù)可大大降低時(shí)間復(fù)雜度。3、規(guī)劃模型規(guī)劃模型是數(shù)學(xué)模型的一類，因其常見(jiàn)，故單獨(dú)列出。它主要包括整數(shù)規(guī)劃及動(dòng)態(tài)規(guī)劃模型。整數(shù)規(guī)劃是所有變量均取整數(shù)的規(guī)劃問(wèn)題，這類問(wèn)題的算法是階乘級(jí)的。動(dòng)態(tài)規(guī)劃的決策、狀態(tài)變量也是取整數(shù)的，但它的算法復(fù)雜度卻是多項(xiàng)工級(jí)的。帶約束的多變量的求解問(wèn)題，特別是約束條件中有滿足某個(gè)函數(shù)的最大（?。┲?，可考慮建立規(guī)劃模型。建立規(guī)劃模型時(shí)，動(dòng)態(tài)規(guī)劃是首先，如果選擇整數(shù)規(guī)劃，則要注意算法的優(yōu)化。2.1.3模型與信息原型間的關(guān)系模型與信息原型間存在“多對(duì)一”或“一對(duì)多”的關(guān)系。建模的一般方法建立數(shù)學(xué)模型沒(méi)有固定的套路可言，方法比較多樣化。建模方法可分為機(jī)理分析法和統(tǒng)計(jì)分析法兩大類；從思維方式的角度，建模方法又可分為直接構(gòu)造法、分類構(gòu)造法和歸納構(gòu)造法三種形式。建模的本質(zhì)是挖掘數(shù)據(jù)間的關(guān)系和數(shù)據(jù)的變化規(guī)律，而“序”是隱藏在數(shù)據(jù)之間的一種常見(jiàn)的、卻難以發(fā)現(xiàn)的關(guān)系。在建模時(shí)，如果能夠在繁雜的數(shù)據(jù)中找到有價(jià)值的序，并加以合理應(yīng)用，往往可使問(wèn)題獲得簡(jiǎn)化，便于問(wèn)題的解決。（1）建模的機(jī)理分析方法：直接建模、套用常用模型方法、有針對(duì)性的修改常用模型、綜合創(chuàng)造。（2）建模的統(tǒng)計(jì)分析方法：通過(guò)某種方法測(cè)試得到問(wèn)題的部分解。再利用數(shù)理統(tǒng)計(jì)知識(shí)分析和處理數(shù)據(jù)，從而得到數(shù)學(xué)模型。統(tǒng)計(jì)分析法是采用逆向思維方式建模的。建模的一般思維方式構(gòu)造數(shù)學(xué)模型，設(shè)計(jì)求解模型的一般方法，統(tǒng)稱構(gòu)造法.從思維方式的角度講，常用構(gòu)造法：直接構(gòu)造法，分類構(gòu)造法和歸納構(gòu)造法.直接構(gòu)造法直接對(duì)目標(biāo)對(duì)象進(jìn)行考察的構(gòu)造方法稱之為直接構(gòu)造法.過(guò)程：①觀察目標(biāo)對(duì)象；②發(fā)現(xiàn)一般規(guī)律；③加以概括總結(jié)，并運(yùn)用至構(gòu)造中.（探索是直接構(gòu)造的靈魂）直接構(gòu)造法需要解題者大膽猜想解題方法，并結(jié)合目標(biāo)反復(fù)嘗試，調(diào)整方案和數(shù)學(xué)推理證明.在構(gòu)造多個(gè)方案的過(guò)程中，要注意從成立的方案中總結(jié)出結(jié)論，從不成立的方案中反思出正確的構(gòu)造方法.對(duì)于某些題目，很難直接給出一種"必行"的構(gòu)造方法，這時(shí)就需要為它"量身定做"多個(gè)構(gòu)造方法，這些構(gòu)造相輔相成：某種構(gòu)造成立可以導(dǎo)出結(jié)論的成立；不成立的構(gòu)造方法也可以為其他的構(gòu)造方法創(chuàng)造條件，如圖所示：構(gòu)造A不成立構(gòu)造B不成立卜I~~構(gòu)造D成立構(gòu)造C不成立」例如：區(qū)間染色問(wèn)題P103分類構(gòu)造法分類構(gòu)造是分類的思想與構(gòu)造法相結(jié)合的產(chǎn)物，簡(jiǎn)單說(shuō)，就是在分類的基礎(chǔ)上進(jìn)行構(gòu)造.分類的思想：按照剩余系分類（奇偶分類），按照數(shù)據(jù)大小分類，按照題目中涉及的定義概念分類，按照參數(shù)的變化分類等等.題例：棋盤遍歷問(wèn)題P105構(gòu)造的分類標(biāo)準(zhǔn)與問(wèn)題不同側(cè)面的性質(zhì)和選擇的構(gòu)造方法息息相關(guān).歸納構(gòu)造法這里主要指數(shù)學(xué)歸納法，歸納構(gòu)造利用了歸納的思想，是構(gòu)造法的一個(gè)經(jīng)典的實(shí)現(xiàn)形式，在競(jìng)賽中，采用得比較普遍的仍然是一般歸納法十構(gòu)造法的形式.如圖所示：構(gòu)造i=1的情況＞￡利用歸納法，推廣到假設(shè)i=1已經(jīng)構(gòu)造上匚與i=n的情況出來(lái)，構(gòu)造i=j+1題例：賽程安排問(wèn)題（1）P107賽程安排問(wèn)題（2）P108在建模過(guò)程中注意應(yīng)用序關(guān)系建模的本質(zhì)是挖掘數(shù)據(jù)間的關(guān)系和數(shù)據(jù)的變化規(guī)律，而數(shù)據(jù)之間的“序"正是數(shù)據(jù)間關(guān)系和數(shù)據(jù)變化規(guī)律的一種表現(xiàn)形式，具有普遍性和隱蔽性的特征.在建模時(shí)，如果能夠在繁雜的數(shù)據(jù)中找到有價(jià)值的序，并加以合理的應(yīng)用，往往可使問(wèn)題獲得簡(jiǎn)化，便于問(wèn)題的解決，本節(jié)結(jié)合實(shí)例，從以下三個(gè)方面討論了序的作用：①在交互式的試題中尋找合適的序，根據(jù)序的特性來(lái)進(jìn)行交互.②利用典型的序關(guān)系（例如樹(shù)和圖的遍歷）簡(jiǎn)化問(wèn)題.③通過(guò)蘊(yùn)涵在題意中的序關(guān)系來(lái)建立簡(jiǎn)潔，高效的解題模型.不同的題目隱藏著不同的、可供挖掘的序。序的應(yīng)用遠(yuǎn)遠(yuǎn)不止本節(jié)所述的這么簡(jiǎn)單。有些序不是什么典型的序關(guān)系，而是隱藏得很深。挖掘和構(gòu)造序關(guān)系，需要有厚實(shí)的知識(shí)積累以及對(duì)數(shù)據(jù)間微妙關(guān)系的敏感。如果能夠好好地利用序，那么序就像一雙慧眼，使我們?cè)谘刍潄y的數(shù)據(jù)關(guān)系中看清問(wèn)題的實(shí)質(zhì)，真正建立簡(jiǎn)潔，高效的解題模型。模型選擇由于探索信息原型的角度多種多樣，因此可能產(chǎn)生多個(gè)數(shù)學(xué)模型。當(dāng)一個(gè)信息原型對(duì)應(yīng)多個(gè)正確的數(shù)學(xué)模型時(shí)，需要我們做抉擇，并反復(fù)不斷地將整個(gè)模型加以完善。一般遵循的原則是“邊分析，邊選擇，兼顧四個(gè)標(biāo)準(zhǔn)（時(shí)間復(fù)雜度、空間復(fù)雜度、編程復(fù)雜度和思維復(fù)雜度）”。四個(gè)標(biāo)準(zhǔn)中應(yīng)以時(shí)間復(fù)雜度為首要，因?yàn)楦?jìng)賽對(duì)算法的運(yùn)行時(shí)間有明確限制。題例：最佳旅行路線問(wèn)題P124第3章目標(biāo)轉(zhuǎn)化的思想目標(biāo)轉(zhuǎn)化的形式有兩種：“降維”——縮小目標(biāo)?！吧S”——放大目標(biāo)。其中維是指一個(gè)問(wèn)題中元素的自由度，即該元素的坐標(biāo)數(shù)，如數(shù)軸上的點(diǎn)的維數(shù)是1。縮小目標(biāo)的降維思想：高維降為低維。一般降為特殊。從極端情況入手。精簡(jiǎn)法。抽象降為具體。整體降為局部。（如排列組合問(wèn)題時(shí)，先從特殊元素，特殊位置這一局部出發(fā)）。也叫著分解法。簡(jiǎn)化數(shù)據(jù)關(guān)系（如二分圖--->有向圖、圖--->樹(shù)、樹(shù)--->序列、二分圖最佳匹配--->二分圖的最大匹配）。在原數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上簡(jiǎn)化數(shù)據(jù)關(guān)系。放大目標(biāo)的升維思想：讓步假設(shè)。：先通過(guò)條件放松、給以適當(dāng)假設(shè)（猜想）等途徑將問(wèn)題求解的范圍擴(kuò)大，然后對(duì)簡(jiǎn)化了的新問(wèn)題求解，最后，“剪掉”擴(kuò)大部分，還原問(wèn)題的解。倍增思想。用途（1，在變化規(guī)則相同的情況下加速狀態(tài)轉(zhuǎn)移。2，加速區(qū)間操作）。：根據(jù)已經(jīng)得到的信息，將考慮的范圍擴(kuò)大一倍，從面加速操作，即在變化規(guī)則相同的情況下加速狀態(tài)轉(zhuǎn)移，或者加速區(qū)間的操作。割補(bǔ)法。補(bǔ)集轉(zhuǎn)化。最后有幾點(diǎn)很重要：敢于猜想，善于類比，尋找相似點(diǎn)和突破口；勇于拓展，在已解決的舊問(wèn)題上發(fā)現(xiàn)新問(wèn)題。第4章分類處分治思想分類是提示概念外延（概念所反映事物的范圍）的邏輯方法，也是求解問(wèn)題的一種基本思想方法。分治是特殊的分類，通常與遞歸聯(lián)系在一起。它的特點(diǎn)是劃分后的子問(wèn)題又是規(guī)模更小的原問(wèn)題。分類和分治的解題步驟一般為：確定對(duì)象。合理分類。逐類討論。歸納結(jié)論。常用的分類或分治法有：二分法、三分法、有限多分法。二分是最常用的分類或分治方法。它的要點(diǎn)如下：選取一個(gè)標(biāo)準(zhǔn)，按照是否符合這個(gè)標(biāo)準(zhǔn)將所需討論的問(wèn)題分成兩類。在前次分類的基礎(chǔ)上，選取另一標(biāo)準(zhǔn)將已分出的類再分成兩類。不斷重復(fù)前一個(gè)過(guò)程，直至涌夠再分為止。二分思想居四種情況下應(yīng)用形式：應(yīng)用于一般有序序列的二分法。如：在給定的序列中“二分查找”，在交互式問(wèn)題中應(yīng)用“二分插入”。應(yīng)用于退化了的有序序列的“二分枚舉”。如：用二分枚舉求可行方案，用二分枚舉求最優(yōu)性問(wèn)題。應(yīng)用研究于無(wú)序序列的“二分搜索”。如：在“二分搜索”的基礎(chǔ)上構(gòu)造可行解，在“二分搜索”的基礎(chǔ)上構(gòu)造最優(yōu)解。應(yīng)用研究于多維情況的“多重二分”。第5章逆向思維逆向思維的兩種形式：a：執(zhí)果索因型逆向思維b:由反及正型逆向思維一：執(zhí)果索因型逆向思維如果滿足條件A可得到結(jié)論B,那么由A推出B叫執(zhí)因索果，反過(guò)來(lái)，由B推A的過(guò)程叫執(zhí)果索因逆向思維。方法執(zhí)果索因型有兩種實(shí)施方案：a：設(shè)置結(jié)果參數(shù)，逆向搜索（搜索分順序搜索和二分搜索），這種方法通常用于這些問(wèn)題：求最大最小問(wèn)題（此類問(wèn)題具有單調(diào)性），使用參數(shù)搜索排除無(wú)效條件，將問(wèn)題的不確定條件變?yōu)榇_定條件。b：從目標(biāo)狀態(tài)出發(fā)逆向規(guī)劃（順序規(guī)劃一般采用自底向上的多重循環(huán)方式，逆向規(guī)劃采用自頂向下記憶化遞歸方式）這兩種方案中，參數(shù)搜索是解決最優(yōu)性問(wèn)題的一種常見(jiàn)方法，其本質(zhì)就是對(duì)問(wèn)題加入結(jié)果參數(shù)，先通過(guò)貪心、動(dòng)態(tài)規(guī)劃或圖論的一些方法判別這個(gè)參數(shù)代表的結(jié)果是否可行；反向規(guī)劃在動(dòng)態(tài)規(guī)劃中，從目標(biāo)狀態(tài)向初始化狀態(tài)倒推。采用此兩種方法時(shí)要注意時(shí)間復(fù)雜度。二：由反及正逆向思維實(shí)現(xiàn)逆向思維常有兩種方法：a：割補(bǔ)法（先補(bǔ)后割中的“補(bǔ)”是設(shè)計(jì)一個(gè)包含解的正反面的“整體”，“割”是在整體中淘汰解的反面，從而抵達(dá)解的正面），分為以下幾種割補(bǔ)法：：計(jì)算幾何中的割補(bǔ)法（直接割補(bǔ)和利用叉積割補(bǔ)）計(jì)算任意多邊形面積，計(jì)算任意多邊形的重心，判斷點(diǎn)與多邊形的位置關(guān)系。2：計(jì)數(shù)問(wèn)題中的割補(bǔ)法（欲求解一定范圍內(nèi)滿足條件的元素個(gè)數(shù)，不妨擴(kuò)大求解范圍，使用加法原理和乘法原理，抑或在統(tǒng)計(jì)中分別求解，再將多余部分刪去，例如，使用容斥原理）.加法原理和乘法原理（可先使用乘法原理分別求出可能解的全集和不符合約束條件的解元素，然后將不符合約束條件的解元素從可能解的全集中減去，剩余的解既是真正解）.容斥原理：在統(tǒng)計(jì)問(wèn)題中應(yīng)用補(bǔ)集轉(zhuǎn)化（解決統(tǒng)計(jì)問(wèn)題有一些常用解法，如離散化、極大化、二分、事件表...但是解決具有特殊性的統(tǒng)計(jì)問(wèn)題應(yīng)采用補(bǔ)集轉(zhuǎn)化）以上兩種思想作為一種非常規(guī)的解題方法，它們和一些常規(guī)的解題方法之間的關(guān)系是辯證的，大多數(shù)問(wèn)題還是適宜用常規(guī)方法的，所以靈活掌握常規(guī)方法和非常規(guī)方法，并結(jié)合具體問(wèn)題選擇合適的方法，才能正確的解決統(tǒng)計(jì)問(wèn)題。第6章猜想與實(shí)驗(yàn)相似聯(lián)想相似聯(lián)想也稱為類比聯(lián)想，指由某一問(wèn)題的條件和線索，就其形態(tài)和性質(zhì)引起與其相似的已有知識(shí)和解題經(jīng)驗(yàn)的聯(lián)想，是借助于對(duì)某一事物的認(rèn)識(shí)，通過(guò)比較它與另一事物的相似特征達(dá)到對(duì)后者的推測(cè)理解，因此它是一類對(duì)象的認(rèn)識(shí)過(guò)渡到另一類對(duì)象的認(rèn)識(shí)的思維方法。相似聯(lián)想的本質(zhì)是類比，類比是得到猜想的重要方法。類比的基本方式有兩種：1與熟悉的問(wèn)題類比，2與特殊的問(wèn)題類比。與熟悉的問(wèn)題進(jìn)行類比的基本步驟是：1分析：分析問(wèn)題的特征，抽象出出模型。聯(lián)想：與熟悉的，擁有類似特征和模型的問(wèn)題類比。比較：確定類比對(duì)象后將兩者比較，分析異同。猜想：根據(jù)已知問(wèn)題猜想新問(wèn)題的解決方法。與特殊問(wèn)題的類比的一般步驟：觀察：觀察題目條件的特征。特殊化：將一些條件的位置，數(shù)量，狀態(tài)等特殊化。分析特殊問(wèn)題。類比。將特殊問(wèn)題與原問(wèn)題比較。猜想：根據(jù)特