算法合集之“約制、放寬”方法在解題中的應(yīng)用(編輯修改稿)
2025-07-04 21:21 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 下兩個(gè)向量。新任務(wù)被解決了，這為解決研究對(duì)象鋪開了一條光明大道。相信聰明的讀者已經(jīng)知道下一步該怎么做了。設(shè)須要等價(jià)轉(zhuǎn)化的三個(gè)向量分別為、和，則把三個(gè)向量等價(jià)替換為兩個(gè)向量的步驟如下：當(dāng)并且時(shí)，向量之所以可以代替和是因?yàn)橄蛄磕鼙硎竞偷某浞直匾獥l件是?！净氐狡瘘c(diǎn)】經(jīng)過一番深入研究探索之后，最終詳細(xì)的解題方法已是不言而喻了。只須每次從剩下的向量中任取三個(gè)向量，按照上述的步驟將它們等價(jià)替換為兩個(gè)向量。不斷重復(fù)該過程直至只剩下兩個(gè)向量，此時(shí)剩下的兩個(gè)向量即為所求。復(fù)雜度分析：每次把三個(gè)向量等價(jià)轉(zhuǎn)為兩個(gè)向量的時(shí)間復(fù)雜度為O(logn)（求gcd所用的時(shí)間），總的時(shí)間復(fù)雜度為O(nlogn)?？臻g復(fù)雜度為O(1)。編程復(fù)雜度很低?！拘〗Y(jié)】“約制”方法的本質(zhì)是為了縮小研究范圍，增加約束性的條件限制，而保證能在該條件下找到解。在本題中，“約制”方法可謂是表現(xiàn)得淋漓盡致：在確定算法時(shí)，約制必須采取化三為二的算法；在把三個(gè)向量等價(jià)轉(zhuǎn)化兩個(gè)向量時(shí)，約制轉(zhuǎn)化的方式必須為先將其中兩個(gè)向量轉(zhuǎn)化成特殊的兩個(gè)向量；在確定特殊的兩個(gè)向量時(shí)，約制特殊的含義為其中一個(gè)為堅(jiān)直向量；在把兩個(gè)非堅(jiān)直向量轉(zhuǎn)化為特殊的兩個(gè)向量時(shí)，約制它們?yōu)楹?，在證明中多次約制某些變量為常量……。[例二]友好的動(dòng)物 選自NOI 2005冬令營(yíng)的《友好的動(dòng)物》【問題描述】W星球是一個(gè)和地球一樣氣候適宜、物種聚集的星球。經(jīng)過多年的研究，外星生物學(xué)家們已經(jīng)發(fā)現(xiàn)了數(shù)萬種生物，而且這個(gè)數(shù)字還在不斷增大。W星球上的生物很有趣，有些生物之間很友好，朝夕相伴，形影不離；但有些卻很敵對(duì)，一見面就難免發(fā)生戰(zhàn)斗。為了能夠更好地了解它們之間的友好程度，外星生物學(xué)家希望進(jìn)行一些量化的計(jì)算。他們發(fā)現(xiàn)，兩種生物之間的友好程度和它們的k種屬性有關(guān)，暫且將它們編號(hào)為屬性屬性……、屬性k，這些屬性都是可以進(jìn)行量化的。外星生物學(xué)家研究發(fā)現(xiàn)，如果前k1種屬性的差別越大，這兩種生物就越友好；但是屬性k與眾不同，這種屬性差別越小的兩種生物越友好。因此他們猜想是不是可以用這樣一個(gè)公式量化兩種生物之間的友好程度：，其中Ci是非負(fù)常數(shù)。如果知道了每種生物的各種屬性，利用上述公式就很容易算出它們之間的友好程度了?，F(xiàn)在，外星生物學(xué)家們想問一問：在目前發(fā)現(xiàn)的這些生物當(dāng)中，關(guān)系最友好的那對(duì)生物是哪一對(duì)呢？它們之間的友好程度是多少？【問題分析】【數(shù)學(xué)模型】首先，把題目的任務(wù)轉(zhuǎn)化為簡(jiǎn)明的數(shù)學(xué)語(yǔ)言：令,求出兩種動(dòng)物的編號(hào)：1=ab=n使得目標(biāo)函數(shù) ①最大化?！驹妓惴ǖ拿堋匡@然最原始的算法是枚舉所有可能的a和b，求出最大的。但這樣做程序的時(shí)間復(fù)雜度是O（nk），顯然無法通過所有的數(shù)據(jù)?！緮?shù)據(jù)范圍分析】一個(gè)很顯眼的條件k≤5，便令人不禁會(huì)想到時(shí)間復(fù)雜度為Ｏ(n2)、Ｏ（nk!），Ｏ（nlogn）之類的指數(shù)級(jí)算法,并促使人向該方面的算法思考。【數(shù)據(jù)結(jié)構(gòu)優(yōu)化時(shí)的矛盾】考慮從數(shù)據(jù)結(jié)構(gòu)上優(yōu)化原始算法。首先，把函數(shù)①中的絕對(duì)值去掉，目標(biāo)函數(shù)變成 ②其中小括號(hào)內(nèi)前面是加號(hào)的數(shù)不小于前面是減號(hào)的數(shù)這樣就有2種情況需要考察。然后，對(duì)于每一種動(dòng)物a,考察a的屬性在函數(shù)②中前面的符號(hào)的情況，用0到21一個(gè)二進(jìn)制BN表示正負(fù)情況：如果BN的第i位為1，則前面的符號(hào)為正，令SIGN(BN,i)=1,否則為負(fù)，令SIGN(BN,i)=。定義表示正負(fù)情況為BN動(dòng)物a的值總和。則Friendliness的最大值為 ③其中a≠b,并且對(duì)于任意的i∈[1,k],都有 ?、軐?shí)現(xiàn)時(shí)，只要先枚舉a和 BN，然后查找滿足性質(zhì)④并且值最大的b(ab)。這時(shí)的查找依懶于2棵第k層以max{F}為元素、第1到第k1層以線段樹為元素的線段樹。復(fù)雜度分析：每次查找和插入的時(shí)間復(fù)雜度都為O（logn），總的時(shí)間復(fù)雜度為O (n2logn),空間復(fù)雜度為O(n logn)，編程復(fù)雜度高。此時(shí)矛盾重重，時(shí)間復(fù)雜度依然很高，空間復(fù)雜度太大，編程復(fù)雜度令人難以忍受?！痉治雒堋坎浑y發(fā)現(xiàn)，產(chǎn)生這些矛盾的根本原因是性質(zhì)④的要求太茍刻了。因此，此時(shí)須要放寬限制?！尽胺艑挕狈椒ɑ饷堋空^退一步海闊天空，試著放寬性質(zhì)④的要求。嘗試將茍刻的要求去掉，但這樣編出來的程序和用原始算法編出來的程序的運(yùn)行結(jié)果是不正確的。因?yàn)檫@樣做實(shí)在太武斷了。先來對(duì)性質(zhì)④做個(gè)詳細(xì)分析：注意到一個(gè)特殊性：越大，F(xiàn)riendliness的值越小，其余的（ik）越大，F(xiàn)riendliness的值越小。因此，試著把性質(zhì)④放寬為只要保證 ⑤結(jié)果，這樣編
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1