递回关系与演算法分析.ppt

《递回关系与演算法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、遞迴關係與演算法分析69/15/20211遞迴關係與演算法分析遞迴與遞迴關係9/15/20212遞迴關係與演算法分析遞迴地定義n!=n(n-1)!或者如果我們令f(n)=n!，那麼f(n)=nf(n-1)。顯然地，這個函數的定義方式有一個特徵：我們所要定義的名相也出現在定義之中成為定義的一部分。這就是我們所謂的遞迴地定義。9/15/20213遞迴關係與演算法分析遞迴地定義遞迴定義包括了兩個部分基礎情況，在這裡明確地給出要定義的名相之某種型式的單純狀況值。遞迴步驟，在這裡將要定義的名相之現值用之

2、前的值來表示。它跟歸納法的證明有著極高的相似性，因此遞迴定義也稱為歸納定義9/15/20214遞迴關係與演算法分析數列在定義數列或者（更廣義來說的）物件序列時，遞迴是很重要的一個觀念。所謂的物件序列S指的是一個有先後次序的物件序列，我們有第一個、第二個、乃至於第n個物件。S(n)表示序列的第n個物件。序列的定義通常是遞迴的先明確地說出第一個或者前幾個值然後再用前面的值來定義後來的值，這中間當然會包括作用在這些物件上的一些運算。9/15/20215遞迴關係與演算法分析數列9/15/20216遞迴關係

3、與演算法分析數列類似像這個範例中命題2的規則，它用了前面一個或多個值來定義後續的數列值，我們稱這種規則為遞迴關係。9/15/20217遞迴關係與演算法分析數列根據命題1，數列的第一個數，T(0)，是1。然後根據命題2，數列的第二個數，T(1)=T(0)+3=1+3=4。再據命題2，數列的第三個數，T(2)=T(1)+3=4+3=7。繼續這麼做下去，我們可以發現數列T是1,4,7,10,13,…9/15/20218遞迴關係與演算法分析數列9/15/20219遞迴關係與演算法分析遞迴定義除了數列外，我

4、們也可以用遞迴的方式來定義運算。9/15/202110遞迴關係與演算法分析線性數列9/15/202111遞迴關係與演算法分析解遞迴關係9/15/202112遞迴關係與演算法分析冪級數一個多項式或者冪級數的係數可以是實數、複數、或者是諸如Zn等其它數系的元素。多項式或者冪級數跟其它數系裡的數一樣，可以做相加以及相乘的運算。我們尤其對於可以表示成有理函數的冪級數感興趣。9/15/202113遞迴關係與演算法分析冪級數9/15/202114遞迴關係與演算法分析冪級數在使用上面這個等式要很小心，它不是對於

5、所有的x值都成立的。舉例來說，如果我們把x用2代進去，我們會得到9/15/202115遞迴關係與演算法分析冪級數這結果不是很荒謬嗎！事實上，這個級數只有當-1

6、02118遞迴關係與演算法分析證明我們將用歸納法來證明這個定理。當n=1時，左式正是上一個範例，而其逆二項式級數便是上個範例的幾何級數。現在假設這個等式在一個給定的n值時成立，我們要證明在裡的xk項之係數值為9/15/202119遞迴關係與演算法分析證明我們有9/15/202120遞迴關係與演算法分析證明其中，最後我們用到了表4.1中的等式VI（平行和）：我們因此完成了這整個證明。9/15/202121遞迴關係與演算法分析逆二項式級數9/15/202122遞迴關係與演算法分析9/15/202123

7、遞迴關係與演算法分析證明如果g(x)是f(x)的乘法倒數，那麼f(x)g(x)=1，因此f(x)跟g(x)相乘以後的常數項應該是1，而f(x)g(x)裡其它x的高冪次項係數必須為0。這是這些方程式的意思。由於這個遞迴方程式決定了g(x)的各項係數。9/15/202124遞迴關係與演算法分析範例利用這個演算法找出多項式(1-x)2的倒數。9/15/202125遞迴關係與演算法分析冪級數一個非零冪級數f(x)的乘法倒數是否一定是一個冪級數呢？倒不見得。問題是出在冪級數的常數項有可能是0，因此上面的演算

8、法就派不上用場。不過，這只是一個小問題。將x的最大可能次冪因子取出來，我們可以將f(x)重新寫成f(x)=xnh(x)其中h(x)有一個非零的常數項。9/15/202126遞迴關係與演算法分析冪級數h(x)有一個倒數k(x)，它是一個冪級數。因此，f(x)的倒數可以寫成x-nk(x)像是這一類的級數我們稱之為勞倫斯級數。以上我們所證得的是：任何一個非零的冪級數其倒數必然是一個勞倫斯級數。9/15/202127遞迴關係與演算法分析冪級數冪級數在離散數學這個領域扮演著非常重要的角色，因