递推递归的复杂性分析课件

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计算计算法设计与分析通信信道上允许传输的单词计算通信信道上允许传输