【正文】 11/10 計算機算法設計與分析 94 通信信道上允許傳輸?shù)膯卧~ ? 再考慮 w = b + w’和 w = c + w’的情況： ? 于是有： Legal(n) = b + Legal(n – 1) c + Legal(n – 1) ? 這里的 w’可以為任意的長度為 n – 1的合法單詞。 2021/11/10 計算機算法設計與分析 95 通信信道上允許傳輸?shù)膯卧~ ? 綜合起來可以得到長度為 n的合法單詞與長度較短的合法單詞之間有如下的關系： Legal(n) = a + b + Legal(n – 2) a + c + Legal(n – 2) b + Legal(n – 1) c + Legal(n – 1) 現(xiàn)在發(fā)生了一個新的情況！ 什么情況？ 2021/11/10 計算機算法設計與分析 96 通信信道上允許傳輸?shù)膯卧~ ? 綜合起來可以得到長度為 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的情況。 2021/11/10 計算機算法設計與分析 97 通信信道上允許傳輸?shù)膯卧~ ? 綜合起來可以得到長度為 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) = ?。 2021/11/10 計算機算法設計與分析 98 通信信道上允許傳輸?shù)膯卧~ ? 綜合 n 為 0和 1的最簡單情況后，有： Legal(n) = ? n = 0 b n = 1 c n = 1 a n = 1 a + b + Legal(n – 2) n 1 a + c + Legal(n – 2) n 1 b + Legal(n – 1) n 1 c + Legal(n – 1) n 1 2021/11/10 計算機算法設計與分析 99 程序設計的思考 現(xiàn)在就讓我們來設計這個程序吧！ ? 這個程序要打印出所有在通信信道上傳輸?shù)拈L度為 n的合法單詞。 現(xiàn)在你頭腦里想象的打印 過程該是什么樣子的呢？ 2021/11/10 計算機算法設計與分析 100 程序設計的思考 現(xiàn)在就讓我們來設計這個程序吧！ ? 這個程序要打印出所有在通信信道上傳輸?shù)拈L度為 n的合法單詞。 ? 我想： ? 這個程序應該是從左向右逐個符號地生成每一個長度為 n的合法單詞。 ? 每生成一個合法單詞，就把它打印出去。 2021/11/10 計算機算法設計與分析 101 程序設計的思考 現(xiàn)在就讓我們來設計這個程序吧！ ? 這個程序要打印出所有在通信信道上傳輸?shù)拈L度為 n的合法單詞。 ? 我想： ? 那么，這個程序就應該有個存放這個長度為 n的合法單詞的變量，就叫它 w[n]吧。 ? 干脆把這個程序叫做 Legal(w, n)好了。 2021/11/10 計算機算法設計與分析 102 程序設計的思考 現(xiàn)在就讓我們來設計這個程序吧！ ? 這個程序要打印出所有在通信信道上傳輸?shù)拈L度為 n的合法單詞。 ? 我想： ? 那么，什么時候就該打印合法單詞 w[n]呢？ ………… ? 那不就是 n = 0的時候嗎？ …… 2021/11/10 計算機算法設計與分析 103 程序設計的思考 現(xiàn)在就讓我們來設計這個程序吧！ ? 這個程序要打印出所有在通信信道上傳輸?shù)拈L度為 n的合法單詞。 aha! I got it! ? 按照遞歸規(guī)則，從 n開始，就是從左至右，將合法的符號放進 w；每放一個符號， n就減一。當 n個符號全都放進去了，就是 n = 0了，就把 w打印出去。 2021/11/10 計算機算法設計與分析 104 打印合法單詞的程序 ? Legal(w[n], int k) { ? if (k=0) {print w} else ? if (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(int n) ? {int w[n] = 0。 Legal(w[n], n) } 考慮運算 w +x。 2021/11/10 計算機算法設計與分析 105 打印合法單詞的程序 ? Legal(w[n], int k) { ? if (k=0) {print w} else ? if (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(int n) ? {int w[n] = 0。 Legal(w[n], n) } w+x就是 w[n–k]=x。 w+x+y就是 w[n–k]=x。 w[n–k+1]=y。 2021/11/10 計算機算法設計與分析 106 打印合法單詞的程序 ? 我們讓遞歸元的初值為 0，終止值為 n，而遞歸元的遞減方式改成加法，即 n+1。于是這個程序還可改寫成下面的樣子： 考慮到運算 w+x的方便我們 可以改變遞歸的方向。 2021/11/10 計算機算法設計與分析 107 打印合法單詞的程序 ? Legal(w[n], int k) { ? if (k=n) {print w} else ? if (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(int n) ? {int w[n] = 0。 Legal(w[n], 0) } k = n時遞歸終止。 遞歸元用加法來遞減。 直接將數(shù)組 w的第 k個分量賦值為 a。遞歸元的初值賦為 0。 請同學們自己編程來具體實現(xiàn)這個程序。 2021/11/10 計算機算法設計與分析 108 打印合法單詞的程序 ? 打印長度為 3的合法單詞： Legal(w[3], 0) Legal(w[ab], 2)。 Legal(w[ac], 2)。 Legal(w[b], 1)。 Legal(w[c], 1) Legal(w[aba], 3)。 Legal(w[abb], 3)。 Legal(w[abc], 3)。 aba。 abb。 abc。 2021/11/10 計算機算法設計與分析 109 打印合法單詞的程序 ? 打印長度為 3的合法單詞： Legal(w[3], 0) Legal(w[ac], 2)。 Legal(w[b], 1)。 Legal(w[c], 1) Legal(w[aca], 3)。 Legal(w[acb], 3)。 Legal(w[acc], 3)。 aba。 abb。 abc。 aca。 acb。 acc。 2021/11/10 計算機算法設計與分析 110 打印合法單詞的程序 ? 打印長度為 3的合法單詞： Legal(w[3], 0) Legal(w[b], 1)。 Legal(w[c], 1) aba。 abb。 abc。 aca。 acb。 acc。 bab。 bac。 Legal(w[bab], 3)。 Legal(w[bac], 3)。 Legal(w[bb], 2)。 Legal(w[bc], 2)。 2021/11/10 計算機算法設計與分析 111 打印合法單詞的程序 ? 打印長度為 3的合法單詞： Legal(w[3], 0) Legal(w[b], 1)。 Legal(w[c], 1) aba。 abb。 abc。 aca。 acb。 acc。 bab。 bac。 bba。 bbb。 bbc。 Legal(w[bb], 2)。 Legal(w[bc], 2)。 Legal(w[bba], 3)。 Legal(w[bbb], 3)。 Legal(w[bbc], 3)。 2021/11/10 計算機算法設計與分析 112 打印合法單詞的程序 ? 打印長度為 3的合法單詞： Legal(w[3], 0) Legal(w[b], 1)。 Legal(w[c], 1) aba。 abb。 abc。 aca。 acb。 acc。 bab。 bac。 bba。 bbb。 bbc。 Legal(w[bc], 2)。 Legal(w[bca], 3)。 Legal(w[bcb], 3)。 Legal(w[bcc], 3)。 bca。 bcb。 bcc。 2021/11/10 計算機算法設計與分析 113 打印合法單詞的程序 ? 打印長度為 3的合法單詞： Legal(w[3], 0) Legal(w[c], 1) aba。 abb。 abc。 aca。 acb。 acc。 bab。 bac。 bba。 bbb。 bbc。 bca。 bcb。 bcc。 Legal(w[cab], 3)。 Legal(w[cac], 3)。 Legal(w[cb], 2)。 Legal(w[cc], 2)。 cab。 cac。 2021/11/10 計算機算法設計與分析 114 打印合法單詞的程序 ? 打印長度為 3的合法單詞： Legal(w[3], 0) Legal(w[c], 1) aba。 abb。 abc。 aca。 acb。 acc。 bab。 bac。 bba。 bbb。 bbc。 bca。 bcb。 bcc。 Legal(w[cb], 2)。 Legal(w[cc], 2)。 cab。 cac。 Legal(w[cba], 3)。 Legal(w[cbb], 3)。 Legal(w[cbc], 3)。 cba。 cbb。 cbc。 2021/11/10 計算機算法設計與分析 115 打印合法單詞的程序 ? 打印長度為 3的合法單詞： Legal(w[3], 0) Legal(w[c], 1) aba。 abb。 abc。 aca。 acb。 acc。 bab。 bac。 bba。 bbb。 bbc。 bca。 bcb。 bcc。 Legal(w[cc], 2)。 cab。 cac。 Legal(w[cca], 3)。 Legal(w[ccb], 3)。 Legal(w[ccc], 3)。 cba。 cbb。 cbc。 cca。 ccb。 ccc。 ? 程序執(zhí)行完畢，上面打印的就是所有長度為 3的合法單詞。 2021/11/10 計算機算法設計與分析 116 算法的時間復雜性 ? 這個算法是一個遞推的遞歸式，并且是一個兩步遞歸。由前面的基本分析可以斷定其復雜性應該是指數(shù)的，即 f(n) = O(an)。 ? 這個算法中的子任務為 2，因此它的時間復雜性應該不會低于 O(2n)。 。 ? 這個程序的時間復雜性是 O(n(1+√3 )n)， 其中打印一個單詞的時間復雜性為 O(n)。 ? 它的復雜性實際上取決于合法單詞的數(shù)量。 2021/11/10 計算機算法設計與分析 117 通信信道上允許傳輸?shù)膯卧~ ? 計算通信信道上允許傳輸?shù)暮戏▎卧~個數(shù)。 ? 解：令 h(n)為的長度 ≤n的 合法單詞個數(shù)。 ? 由前面的討論我們有： ? 最簡單情況時 h(0) = 1， h(1) = 3。