递回关系与演算法分析
80页1、2018/10/19,遞迴關係與演算法分析,1,遞迴關係與演算法分析,6,2018/10/19,遞迴關係與演算法分析,2,遞 迴 與 遞 迴 關 係,2018/10/19,遞迴關係與演算法分析,3,遞 迴 地 定 義,n!=n(n-1)! 或者 如果我們令 f(n)=n!,那麼 f(n)=nf(n-1)。 顯然地,這個函數的定義方式有一個特徵:我們所要定義的名相也出現在定義之中成為定義的一部分。 這就是我們所謂的遞迴地定義。,2018/10/19,遞迴關係與演算法分析,4,遞 迴 地 定 義,遞迴定義包括了兩個部分 基礎情況,在這裡明確地給出要定義的名相之某種型式的單純狀況值。 遞迴步驟,在這裡將要定義的名相之現值用之前的值來表示。 它跟歸納法的證明有著極高的相似性 ,因此遞迴定義也稱為歸納定義,2018/10/19,遞迴關係與演算法分析,5,數 列,在定義數列或者(更廣義來說的)物件序列時,遞迴是很重要的一個觀念。 所謂的物件序列 S 指的是一個有先後次序的物件序列,我們有第一個、第二個、乃至於第 n個物件。 S(n) 表示序列的第 n 個物件。 序列的定義通常是遞迴的 先明確地說出
2、第一個或者前幾個值 然後再用前面的值來定義後來的值, 這中間當然會包括作用在這些物件上的一些運算。,2018/10/19,遞迴關係與演算法分析,6,數 列,2018/10/19,遞迴關係與演算法分析,7,數 列,類似像這個範例中命題 2 的規則,它用了前面一個或多個值來定義後續的數列值,我們稱這種規則為遞迴關係。,2018/10/19,遞迴關係與演算法分析,8,數 列,根據命題 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, ,2018/10/19,遞迴關係與演算法分析,9,數 列,2018/10/19,遞迴關係與演算法分析,10,遞 迴 定 義,除了數列外,我們也可以用遞迴的方式來定義運算。,2018/10/19,遞迴關係與演算法分析,11,線 性 數 列,2018/10/19,遞迴關係與演算法分析,12,解 遞 迴 關 係,2018/10/19,遞迴關係與演算法分析,13,冪 級
3、數,一個多項式或者冪級數的係數可以是實數、複數、或者是諸如 Zn 等其它數系的元素。 多項式或者冪級數跟其它數系裡的數一樣,可以做相加以及相乘的運算。 我們尤其對於可以表示成有理函數的冪級數感興趣。,2018/10/19,遞迴關係與演算法分析,14,冪 級 數,2018/10/19,遞迴關係與演算法分析,15,冪 級 數,在使用上面這個等式要很小心,它不是對於所有的 x 值都成立的。 舉例來說,如果我們把 x 用 2 代進去,我們會得到,2018/10/19,遞迴關係與演算法分析,16,冪 級 數,這結果不是很荒謬嗎! 事實上,這個級數只有當 -1x1 時才收斂到。 但是,在這以下我們將只是把這個等式視為是一種正式表示法,而不去管到底 x是在什麼範圍時這個收斂情況才成立。,2018/10/19,遞迴關係與演算法分析,17,冪 級 數,2018/10/19,遞迴關係與演算法分析,18,逆 二 項 式 級 數,在第四章我們介紹了二項式定理,利用它我們可以計算出 (1-x)n 的各項係數。 下面這個定理則可以計算出 的係數。,2018/10/19,遞迴關係與演算法分析,19,證 明,我們將用
4、歸納法來證明這個定理。 當 n=1 時,左式正是上一個範例,而其逆二項式級數便是上個範例的幾何級數。 現在假設這個等式在一個給定的 n 值時成立,我們要證明在 裡的 xk 項之係數值為,2018/10/19,遞迴關係與演算法分析,20,證 明,我們有,2018/10/19,遞迴關係與演算法分析,21,證 明,其中,最後我們用到了表4.1中的等式VI(平行和): 我們因此完成了這整個證明。,2018/10/19,遞迴關係與演算法分析,22,逆 二 項 式 級 數,2018/10/19,遞迴關係與演算法分析,23,2018/10/19,遞迴關係與演算法分析,24,證 明,如果 g(x) 是 f(x) 的乘法倒數,那麼 f(x)g(x)=1,因此 f(x) 跟 g(x) 相乘以後的常數項應該是1,而 f(x)g(x) 裡其它 x 的高冪次項係數必須為 0。 這是這些方程式的意思。由於 這個遞迴方程式決定了 g(x) 的各項係數。,2018/10/19,遞迴關係與演算法分析,25,範 例,利用這個演算法找出多項式 (1-x)2 的倒數。,2018/10/19,遞迴關係與演算法分析,26,冪 級
《递回关系与演算法分析》由会员kms****20分享,可在线阅读,更多相关《递回关系与演算法分析》请在金锄头文库上搜索。
高三文科数学(长方体模型1)
高一生物:必修2 1.1孟德尔的豌豆杂交实验
遗传学第1章 绪言
高等代数课件--第三章 线性方程组§3.3 线性相关性
高二数学(1.1-1空间几何体及棱柱、棱锥的结构特征)
递回关系与演算法分析
过程是vb的基本组成单位
营养器官的生长
细菌真菌在生物圈中的作用课件(济南版七年级上)
自动化-ab变频器的原理及其应用
网络操作系统-第16章 windows server 2003安全管理
网络安全+第4讲+防火墙
素材-接触网施工技术-双线隧道吊柱安装
系统结构第5章
计算机体系结构实验2008
计算机系统安全
高考词汇总常用词v
软件测试tmap
电脑文件被删除怎么恢复图文教程
电子教案--第9章
2023-10-12 28页
2022-07-12 126页
2022-06-07 89页
2022-06-07 158页
2022-06-07 60页
2022-06-07 122页
2022-06-07 76页
2022-06-07 79页
2022-06-06 38页
2022-06-06 47页