2.3遞推遞歸的復雜性分析9/21/20231計算計算法設計與分析2.3遞推遞歸的復雜性分析8/6/20231計算計算法設遞歸復雜性的一般形式一般的，遞歸關系描述為遞歸方程：1n=1aT(n~b)+D(n)n＞1T(n)=其中，a是子問題個數，b是遞減步長，~表示遞減方式，D(n)是合成子問題的開銷。通常，遞歸元的遞減方式~有兩種：1、除法，即n/b，的形式；2、減法，即n–b，的形式。分治遞推9/21/20232計算計算法設計與分析遞歸復雜性的一般形式一般的，遞歸關系描述為遞歸方程：遞推關系與遞歸算術序列：h0,h0+q,h0+2q,…,h0+nq,….或為遞歸式：h(n)=h(n–1)+q，h(0)=h0。幾何序列：h0,qh0,q2h0,…,qnh0,….或為遞歸式：h(n)=qh(n–1)，h(0)=h0。如果遞歸式的遞減方式是減法的話，則遞歸式按其遞歸元就形成一個遞推序列。9/21/20233計算計算法設計與分析遞推關系與遞歸算術序列：h0,h0+q,h0+2q,…遞推遞歸的時間復雜性

k–1

i=0=akT(1)+aiD(n–ib)這里k=n/b。不失一般性令b=1，則k=n。若設D(n)為常數，則有T(n)=

O(an)。若~為減法，即n–b，則有：T(n)=aT(n–b)+D(n)=a(aT(n–2b)+D(n–b))+D(n)=

k–1

i=0=ak+aiD(n–ib)在通常的情況下遞推遞歸的時間復雜性為指數函數。9/21/20234計算計算法設計與分析遞推遞歸的時間復雜性k–1=akT(1)+n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所形成的區域數是多少？所謂相互交疊的圓是指兩個圓相交在不同的兩點。9/21/20235計算計算法設計與分析n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所形成的區域數是多少？令h(n)為平面上有n個互相交疊的圓所形成的區域數。h(n)=?讓我們先從最簡單的情況來考慮。9/21/20236計算計算法設計與分析n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所形成的區域數是多少？令h(n)為平面上有n個互相交疊的圓所形成的區域數。顯然h(0)=1。h(1)=2。h(2)=4。h(3)=8。h(4)=？h(4)=149/21/20237計算計算法設計與分析n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所形成的區域數是多少？令h(n)為平面上有n個互相交疊的圓所形成的區域數。h(n)=?我們仍然不知道。我們該怎么做呢？9/21/20238計算計算法設計與分析n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所形成的區域數是多少？令h(n)為平面上有n個互相交疊的圓所形成的區域數。這時要考慮復雜情況與較簡單情況之間關系，即復雜情況是怎樣由較簡單情況構成的。9/21/20239計算計算法設計與分析n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所形成的區域數是多少？假設前面n–1個圓形成h(n–1)個區域。現放進第n個圓與前n–1個圓交疊。讓我們來考慮把這第n個圓交疊上去會造成區域數發生什么樣的變化呢？9/21/202310計算計算法設計與分析n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所形成的區域數是多少？假設前面n–1個圓形成h(n–1)個區域。現放進第n個圓與前n–1個圓交疊。第n個圓與前n–1個圓都相交于兩點，于是有2(n–1)個交點。這2(n–1)個點將第n個圓分成2(n–1)條弧，而每條弧又將某個區域一分為二，因此新增加的區域數應為2(n–1)。9/21/202311計算計算法設計與分析n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所形成的區域數是多少？令h(n)為平面上有n個互相交疊的圓所形成的區域數。于是便得到如下的遞歸式：h(n)=h(n–1)+2(n–1)。這個遞推遞歸式有一個簡單的通項公式：h(n)=h(n–1)+2(n–1)。h(n–2)+2(n–2)+2(n–1)h(n–3)+2(n–3)+2(n–2)+2(n–1)h(1)+2(1)+2(2)+…+2(n–1)2+2n(n–1)/2=n2–n+2。注意此公式對h(0)不成立！n>0。9/21/202312計算計算法設計與分析n個互相交疊的圓的區域數在平面一般位置上有n個互相交疊的圓所棋盤覆蓋問題一個2k×2k特殊棋盤是其中含有一個特殊方格的棋盤，左下圖為k=2的一個特殊棋盤。現在任給定一個2k×2k特殊棋盤，要用右下圖所示的L型骨牌來無重疊的覆蓋它。 111222333444555在2k×2k的棋盤覆蓋中要用到(4k–1)/3個L型骨牌。9/21/202313計算計算法設計與分析棋盤覆蓋問題一個2k×2k特殊棋盤是其中含有一個特殊方格的棋棋盤覆蓋問題讓我們先來考慮最簡單的情況：什么是最簡單的情況？最簡單情況是k=0。這時棋盤有20×20=1個格子，即只有一個特殊格子。這時棋盤已被完全覆蓋，無須再做什么了。下面我們來考慮復雜情況是怎樣由較簡單情況構成的。9/21/202314計算計算法設計與分析棋盤覆蓋問題讓我們先來考慮最簡單的情況：什么是最簡單的情況？棋盤覆蓋問題的分析當k>0時，將2k×2k棋盤分割成4個2k–1×2k–1的子棋盤，如右下圖所示：2k–1×2k–12k–1×2k–12k–1×2k–12k–1×2k–1特殊方格必定位于4個子棋盤之一中。而這四個子棋盤卻不一致。遞歸求解是將問題歸結到較小規模的同一問題，這就需要將三個正常子棋盤也轉化成特殊棋盤。9/21/202315計算計算法設計與分析棋盤覆蓋問題的分析當k>0時，將2k×2k棋盤分割成4個2k棋盤覆蓋問題的分析當k>0時，將2k×2k棋盤分割成4個2k–1×2k–1的子棋盤，如右下圖所示：2k–1×2k–12k–1×2k–12k–1×2k–12k–1×2k–1特殊方格必定位于4個子棋盤之一中。為此，可用一個L型骨牌覆蓋三個正常子棋盤的會合處，如左圖所示。這次覆蓋后四個子棋盤都是特殊棋盤了。9/21/202316計算計算法設計與分析棋盤覆蓋問題的分析當k>0時，將2k×2k棋盤分割成4個2k棋盤覆蓋的算法棋盤覆蓋(參數表){⑴如果是單個格子，則返回；⑵將棋盤劃分成尺寸為一半的子棋盤；⑶判斷特殊方格在哪個子棋盤中，再用相應L型骨牌覆蓋相應結合部，即不含特殊方格的部分在結合部的三個方格；并記下它們的位置，作為各部分的特殊方格；⑷依次對左上角、右上角、右下角和左下角四個子棋盤進行棋盤覆蓋；}9/21/202317計算計算法設計與分析棋盤覆蓋的算法棋盤覆蓋(參數表){8/6/202317計算棋盤覆蓋算法中的參數算法的形參表中需要的參數有：遞歸元：棋盤尺寸為2n。每輪遞歸時將n減1，則棋盤尺寸減半；當n為0時遞歸終止。棋盤位置：棋盤左上角方格的行列號tr和tc。特殊方格位置：特殊方格的行列號dr和dc。參數表中應有哪些參數呢？遞歸元定義為intn棋盤位置定義為inttr,tc。特殊方格位置定義為intdr,dc。9/21/202318計算計算法設計與分析棋盤覆蓋算法中的參數算法的形參表中需要的參數有：參數表中應有棋盤覆蓋算法中其它變量除了形參表中的那些參數外，棋盤覆蓋程序中還需要如下的變量：表示棋盤的變量。表示L型骨牌覆蓋順序的變量。棋盤尺寸的變量。各子棋盤在結合部的方格位置。各子棋盤的特殊方格的位置。除形參外，算法中還應有哪些變量呢？內部變量全局變量為什么要設這個變量呢？9/21/202319計算計算法設計與分析棋盤覆蓋算法中其它變量除了形參表中的那些參數外，棋盤覆蓋程序棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][2n]，初值為全0。覆蓋順序變量定義為inttile，其初值為0。棋盤尺寸的變量定義為ints，其初值為2n。不設此變量也可以。但因s=2n，則每輪遞歸中都要做求2n的冪運算。設變量s后，只需初始時計算一次s=2n，以后只要做s=s/2即可。這樣降低了遞歸中的運算強度。9/21/202320計算計算法設計與分析棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][2n]，初值為全0。覆蓋順序變量定義為inttile，其初值為0。棋盤尺寸的變量定義為ints，其初值為2n。0132四個子棋盤的排序為結合部的方格位置定義為intjr[4],jc[4]。各子棋盤的特殊方格的位置定義為intSr[4],Sc[4]。9/21/202321計算計算法設計與分析棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][2n]，初值為全0。覆蓋順序變量定義為inttile，其初值為0。棋盤尺寸的變量定義為ints。結合部的方格位置定義為intjr[4],jc[4]。各子棋盤的特殊方格的位置定義為intSr[4],Sc[4]。將棋盤覆蓋程序取名為CoverBoard；9/21/202322計算計算法設計與分析棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][棋盤覆蓋的算法voiceCoverBoard(n,tr,tc,dr,dc){if(n=0)return;n=n–1;s=s/2;tile++;Coverjoin;CoverBoard(n,tr,tc,sr[0],sc[0]);CoverBoard(n,tr+s,tc,sr[1],sc[1])；CoverBoard(n,tr+s,tc+s,sr[2],sc[2])CoverBoard(n,tr,tc+s,sr[3],sc[3])}若只有一個格子，則終止遞歸。注意遞歸元的遞減是在這里做的。s是減半后的子棋盤尺寸。在對結合部覆蓋之前將覆蓋序號tile加一。9/21/202323計算計算法設計與分析棋盤覆蓋的算法voiceCoverBoard(n,tr,棋盤覆蓋的算法voiceCoverBoard(n,tr,tc,dr,dc){if(n=0)return();n=n–1;s=s/2;tile++;Coverjoin;CoverBoard(n,tr,tc,sr[0],sc[0]);CoverBoard(n,tr+s,tc,sr[1],sc[1])；CoverBoard(n,tr+s,tc+s,sr[2],sc[2])CoverBoard(n,tr,tc+s,sr[3],sc[3])}Coverjoin完成以下功能：1、計算結合部的方格的位置；2、判斷特殊方格位置；3、覆蓋子棋盤結合部并將四個特殊方格的位置寫入sr[]和sc[]。依次對四個子棋盤進行覆蓋。覆蓋左上角的子棋盤。覆蓋右上角的子棋盤。覆蓋右下角的子棋盤。覆蓋左下角的子棋盤。9/21/202324計算計算法設計與分析棋盤覆蓋的算法voiceCoverBoard(n,tr,棋盤覆蓋的算法voiceCoverBoard(n,tr,tc,dr,dc){if(n=0)return();n=n–1;s=s/2;tile++;Coverjoin;CoverBoard(n,tr,tc,sr[0],sc[0]);CoverBoard(n,tr+s,tc,sr[1],sc[1])；CoverBoard(n,tr+s,tc+s,sr[2],sc[2])CoverBoard(n,tr,tc+s,sr[3],sc[3])}依次對四個子棋盤進行覆蓋。覆蓋左上角的0號子棋盤。覆蓋右上角的1號子棋盤。覆蓋右下角的2號子棋盤。覆蓋左下角的3號子棋盤。9/21/202325計算計算法設計與分析棋盤覆蓋的算法voiceCoverBoard(n,tr,Coverjoin的實現⑴計算結合部方格位置：⑵判斷特殊方格(dr,dc)落在那個子棋盤：⑶覆蓋結合部并確定各子棋盤特殊方格位置。9/21/202326計算計算法設計與分析Coverjoin的實現⑴計算結合部方格位置：⑵判斷特殊方Coverjoin的實現⑴計算結合部方格位置：tr是0區和1區的首行，tc是0區和3區的首列;tr+s是3區和2區的首行;tc+s是1區和2區的首列0312trtcss9/21/202327計算計算法設計與分析Coverjoin的實現⑴計算結合部方格位置：tr是0區和Coverjoin的實現⑴計算結合部方格位置：0312trtcssjr[0]=tr+s–1;jc[0]=tc+s–1;jr[1]=tr+s–1;jc[1]=tc+s;jr[2]=tr+s;jc[2]=tc+s;jr[3]=tr+s;jc[3]=tc+s–1;jr[0]=tr+s–1;jc[0]=tc+s–1jr[1]=tr+s–1;jc[1]=tc+sjr[2]=tr+s;jc[2]=tc+sjr[3]=tr+s;jc[3]=tc+s–19/21/202328計算計算法設計與分析Coverjoin的實現⑴計算結合部方格位置：0312trCoverjoin的實現⑴計算結合部方格位置：⑵判斷特殊方格(dr,dc)落在那個子棋盤：我們可以依據結合部方格的行號和列號來判斷特殊方格落在哪個子棋盤中。0132trtcssjr[0]=tr+s–1;jc[0]=tc+s–1;jr[1]=tr+s;jc[1]=tc+s–1;jr[2]=tr+s;jc[2]=tc+s;jr[3]=tr+s–1;jc[3]=tc+s;9/21/202329計算計算法設計與分析Coverjoin的實現⑴計算結合部方格位置：⑵判斷特殊方Coverjoin的實現⑴計算結合部方格位置：⑵判斷特殊方格(dr,dc)落在那個子棋盤：⑶覆蓋結合部并確定各子棋盤特殊方格位置。if(dr<=jr[0]&&dc<=jc[0])r=0elseif(dr<=jr[1]&&dc>=jc[1])r=1elseif(dr>=jr[2]&&dc>=jc[2])r=2elseif(dr>=jr[3]&&dc<=jc[3])r=3;jr[0]=tr+s–1;jc[0]=tc+s–1;jr[1]=tr+s;jc[1]=tc+s–1;jr[2]=tr+s;jc[2]=tc+s;jr[3]=tr+s–1;jc[3]=tc+s;若特殊方格的行標dr<=jr[0]且列標dc<=jc[0]，則特殊方格位于在0號子棋盤中。其余類似。r指明了這點。9/21/202330計算計算法設計與分析Coverjoin的實現⑴計算結合部方格位置：⑵判斷特殊方Coverjoin的實現⑶覆蓋結合部并確定各子棋盤特殊方格位置：if(r=0){sr[0]=dr;sc[0]=dc;Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];k=1,2,3}elseif(r=1){sr[1]=dr;sc[1]=dc;Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];k=0,2,3}elseif(r=2){sr[2]=dr;sc[2]=dc;Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];k=0,1,3}elseif(r=3){sr[1]=dr;sc[1]=dc;Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];k=0,1,2};注意：此處由于幻燈片篇幅的原因，簡寫成這樣，實際表示對于k=1,2,3，執行{Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];}，即覆蓋相應格子，并將其作為對應子棋盤的特殊方格。下面亦如此。9/21/202331計算計算法設計與分析Coverjoin的實現⑶覆蓋結合部并確定各子棋盤特殊方格位Coverjoin的實現⑶覆蓋結合部并確定各子棋盤特殊方格位置也可以用如下的語句來實現：sr[r]=dr;sc[r]=dc;for(k=0,k<4,i++)if(k<>r){Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]]};特殊子棋盤的特殊方格還是原來的。對每個非特殊子棋盤，則覆蓋其結合部的方格并將其作為該子棋盤的特殊方格。由于這個操作可以用此簡單表示，所以才在上一張幻燈片上采用了簡記的方式。9/21/202332計算計算法設計與分析Coverjoin的實現⑶覆蓋結合部并確定各子棋盤特殊方格位棋盤覆蓋算法的主程序main(intn,intdr,intdc){ints=2nintBoard[s][s]=0;inttile=0;CoverBoard(n,0,0,dr,dc);}請同學們自己編程來具體實現這個程序。9/21/202333計算計算法設計與分析棋盤覆蓋算法的主程序main(intn,intdr,棋盤覆蓋算法的正確性要證明一個算法的正確性，需要證明兩點：(1)算法的部分正確性；(2)算法的終止性。下面我們用歸納法證明棋盤覆蓋算法的部分正確性：9/21/202334計算計算法設計與分析棋盤覆蓋算法的正確性要證明一個算法的正確性，需要證明兩點：8棋盤覆蓋算法的部分正確性歸納基礎：k=0時，特殊棋盤僅含一個特殊方格，顯然已經正確覆蓋。假設對2k–1的特殊棋盤均可正確覆蓋。對2k的特殊棋盤，算法劃分為四個2k–1的子棋盤。用一塊L型骨牌覆蓋三個正常子棋盤的結合處后，恰形成四個2k–1的特殊棋盤。由歸納假設，它們均可被正確覆蓋。因而也正確覆蓋了2k的特殊棋盤。由歸納法可知，棋盤覆蓋算法是部分正確。9/21/202335計算計算法設計與分析棋盤覆蓋算法的部分正確性歸納基礎：k=0時，特殊棋盤僅含棋盤覆蓋算法的終止性算法的終止性：遞歸終止條件為遞歸元size為1時遞歸終止。遞歸元size的初值為2k。每次遞歸時遞歸元減半，即size=size/2；因此，必然在有窮步內遞減為1。所以此算法必定終止。由部分正確性和終止性可知，此算法是完全正確的。9/21/202336計算計算法設計與分析棋盤覆蓋算法的終止性算法的終止性：由部分正確性和終止性可知，棋盤覆蓋算法的復雜性設T(k)是棋盤覆蓋算法覆蓋2k×2k的棋盤所需要的時間，則T(k)滿足如下遞歸方程：T(k)=O(1)k=04T(k–1)+O(1)k＞0遞歸元遞減方式是減法，故此分治法實質是遞推關系。由a=4可知T(k)=O(4k)。覆蓋2k×2k的棋盤要用(4k–1)/3個L型骨牌，故此算法是一個在漸進意義下最優的算法。9/21/202337計算計算法設計與分析棋盤覆蓋算法的復雜性設T(k)是棋盤覆蓋算法覆蓋2k×2k的小結用減法方式遞減的遞歸式按其遞歸元形成一個遞推序列。遞推關系的遞歸程序的時間復雜性T(n)通常不小于

O(an)，這里a是子問題的個數。用遞推遞歸求解的思路仍是先考慮最簡情況，再考慮復雜情況與較簡情況關系。程序的完全正確性由其部分正確性和終止性兩部分構成。9/21/202338計算計算法設計與分析小結用減法方式遞減的遞歸式按其遞歸元形成一個遞推序列。8/6通信信道上允許傳輸的單詞已知在通信信道上傳輸的單詞只能由a、b和c三個字母組成并且其中不得有兩個字母a連續出現。請編寫一個程序生成所有在通信信道上允許傳輸的長度為n的單詞。將這樣的單詞稱為長度為n的合法單詞。我們該如何來考慮編寫這個程序呢？1、先分析最簡單情況的解。2、再分析復雜情況如何由較簡情況組成。9/21/202339計算計算法設計與分析通信信道上允許傳輸的單詞已知在通信信道上傳輸的單詞只能由a、通信信道上允許傳輸的單詞應該是長度n=1的單詞。此問題中最簡單的情況是什么？長度為1的合法單詞只有三個，即a、b和c。下面我們再考慮長度為n(n>1)的合法單詞是如何由長度n–1的合法單詞構成的。9/21/202340計算計算法設計與分析通信信道上允許傳輸的單詞應該是長度n=1的單詞。此問題中通信信道上允許傳輸的單詞把長度為n合法單詞w去掉最前面的一個符號后所剩下的就是長度為n–1的單詞w’。顯然w’仍然應該是合法單詞。如何考慮用長度n–1的合法單詞來構成長度n的合法單詞呢？于是有：w=a+w’b+w’c+w’這里用符號+表示符號串的連接運算。9/21/202341計算計算法設計與分析通信信道上允許傳輸的單詞把長度為n合法單詞w去掉最前面的一通信信道上允許傳輸的單詞先考慮w=a+w’的情況：于是有：w=a+b+w’’a+c+w’’因為通信信道上的合法單詞中不允許出現連續的a，所以w’只能以b或者c開頭。于是w’=b+w’’或者w’=c+w’’。這里w’’為任意的長度為n–2的合法單詞。將長度為n的合法單詞命名為Legal(n)。9/21/202342計算計算法設計與分析通信信道上允許傳輸的單詞先考慮w=a+w’的情況：于通信信道上允許傳輸的單詞先考慮w=a+w’的情況：于是有：Legal(n)=a+b+Legal(n–2)

a+c+Legal(n–2)

因為通信信道上的合法單詞中不允許出現連續的a，所以w’只能以b或者c開頭。于是w’=b+w’’或者w’=c+w’’。這里w’’為任意的長度為n–2的合法單詞。9/21/202343計算計算法設計與分析通信信道上允許傳輸的單詞先考慮w=a+w’的情況：于通信信道上允許傳輸的單詞再考慮w=b+w’和w=c+w’的情況：于是有：Legal(n)=b+Legal(n–1)

c+Legal(n–1)

這里的w’可以為任意的長度為n–1的合法單詞。9/21/202344計算計算法設計與分析通信信道上允許傳輸的單詞再考慮w=b+w’和w=通信信道上允許傳輸的單詞綜合起來可以得到長度為n的合法單詞與長度較短的合法單詞之間有如下的關系：Legal(n)=a+b+Legal(n–2)

a+c+Legal(n–2)b+Legal(n–1)

c+Legal(n–1)

現在發生了一個新的情況！什么情況？9/21/202345計算計算法設計與分析通信信道上允許傳輸的單詞綜合起來可以得到長度為n的合法單詞與通信信道上允許傳輸的單詞綜合起來可以得到長度為n的合法單詞與長度較短的合法單詞之間有如下的關系：Legal(n)=a+b+Legal(n–2)

a+c+Legal(n–2)b+Legal(n–1)

c+Legal(n–1)

這是個兩步遞歸！可是我們只考慮了n=1這一種最簡單情況！要增加n=0的情況。9/21/202346計算計算法設計與分析通信信道上允許傳輸的單詞綜合起來可以得到長度為n的合法單詞與通信信道上允許傳輸的單詞綜合起來可以得到長度為n的合法單詞與長度較短的合法單詞之間有如下的關系：Legal(n)=a+b+Legal(n–2)

a+c+Legal(n–2)b+Legal(n–1)

c+Legal(n–1)

我們令當n=0時的合法單詞為空串

，即Legal(0)=

。9/21/202347計算計算法設計與分析通信信道上允許傳輸的單詞綜合起來可以得到長度為n的合法單詞與通信信道上允許傳輸的單詞綜合n為0和1的最簡單情況后，有：Legal(n)=

n=0bn=1cn=1an=1a+b+Legal(n–2)n>1a+c+Legal(n–2)n>1b+Legal(n–1)n>1c+Legal(n–1)n>19/21/202348計算計算法設計與分析通信信道上允許傳輸的單詞綜合n為0和1的最簡單情況后，有程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打印出所有在通信信道上傳輸的長度為n的合法單詞。現在你頭腦里想象的打印過程該是什么樣子的呢？9/21/202349計算計算法設計與分析程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打印出所有在通信信道上傳輸的長度為n的合法單詞。我想：這個程序應該是從左向右逐個符號地生成每一個長度為n的合法單詞。每生成一個合法單詞，就把它打印出去。9/21/202350計算計算法設計與分析程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打印出所有在通信信道上傳輸的長度為n的合法單詞。我想：那么，這個程序就應該有個存放這個長度為n的合法單詞的變量，就叫它w[n]。干脆把這個程序叫做Legal(w,n)好了。9/21/202351計算計算法設計與分析程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打印出所有在通信信道上傳輸的長度為n的合法單詞。我想：那么，什么時候就該打印合法單詞w[n]呢？…………那不就是n=0的時候嗎？……9/21/202352計算計算法設計與分析程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打印出所有在通信信道上傳輸的長度為n的合法單詞。aha!Igotit!按照遞歸規則，從n開始，就是從左至右，將合法的符號放進w；每放一個符號，n就減一。當n個符號全都放進去了，就是n=0了，就把w打印出去。9/21/202353計算計算法設計與分析程序設計的思考現在就讓我們來設計這個程序吧！這個程序要打打印合法單詞的程序Legal(w[n],intk){if(k=0){printw}elseif(k=1){Legal(w+a,k–1);Legal(w+b,k–1);Legal(w+c,k–1)}else{Legal(w+a+b,k–2);Legal(w+a+c,k–2);Legal(w+b,k–1);Legal(w+c,k–1)}}main(intn){intw[n]=0;Legal(w[n],n)}考慮運算w+x。9/21/202354計算計算法設計與分析打印合法單詞的程序Legal(w[n],intk){考打印合法單詞的程序Legal(w[n],intk){if(k=0){printw}elseif(k=1){Legal(w+a,k–1);Legal(w+b,k–1);Legal(w+c,k–1)}else{Legal(w+a+b,k–2);Legal(w+a+c,k–2);Legal(w+b,k–1);Legal(w+c,k–1)}}main(intn){intw[n]=0;Legal(w[n],n)}w+x就是w[n–k]=x。w+x+y就是w[n–k]=x;w[n–k+1]=y。9/21/202355計算計算法設計與分析打印合法單詞的程序Legal(w[n],intk){w打印合法單詞的程序我們讓遞歸元的初值為0，終止值為n，而遞歸元的遞減方式改成加法，即n+1。于是這個程序還可改寫成下面的樣子：考慮到運算w+x的方便我們可以改變遞歸的方向。9/21/202356計算計算法設計與分析打印合法單詞的程序我們讓遞歸元的初值為0，終止值為n，而遞歸打印合法單詞的程序Legal(w[n],intk){if(k=n){printw}elseif(k=n–1){Legal(w+a,k+1);Legal(w+b,k+1);Legal(w+c,k+1)}else{Legal(w+a+b,k+2);Legal(w+a+c,k+2);Legal(w+b,k+1);Legal(w+c,k+1)}}main(intn){intw[n]=0;Legal(w[n],0)}k=n時遞歸終止。遞歸元用加法來遞減。直接將數組w的第k個分量賦值為a。遞歸元的初值賦為0。請同學們自己變成來具體實現這個程序。9/21/202357計算計算法設計與分析打印合法單詞的程序Legal(w[n],intk){k算法的時間復雜性這個算法是一個遞推的遞歸式，并且是一個兩步遞歸。由前面的基本分析可以斷定其復雜性應該是指數的，即T(n)=O(an)。這個算法中的子任務為2，因此它的時間復雜性應該不會低于O(2n)。O((1+√3)n)。這個程序的時間復雜性是它的復雜性實際上決定于合法單詞的數量。9/21/202358計算計算法設計與分析算法的時間復雜性這個算法是一個遞推的遞歸式，并且是一個兩步遞通信信道上允許傳輸的單詞計算通信信道上允許傳輸的合法單詞個數。解：令h(n)為的長度≤n的合法單詞個數。由前面的討論我們有：最簡單情況時h(0)=1，h(1)=3。當n≥2時：h(n)=2h(n–1)+2h(n–2)求解這個遞歸方程可得：(2+√3)2√3(1+√3)n+h(n)=(–2+√3)2√3(1–√3)n這個遞歸函數也是著名的斐波拉契函數。有趣的是，對于任意的n，這個無理式的結果都是整數。9/21/202359計算計算法設計與分析通信信道上允許傳輸的單詞計算通信信道上允許傳輸