c語言_遞歸算法.ppt

計算機語言與程序設計 諶衛(wèi)軍 清華大學軟件學院 IntroductiontoComputerProgramming 第八章遞歸算法 1 3 2 基本概念 基于回溯策略的遞歸 基于分治策略的遞歸 從前有座山 山上有座廟 廟里有一個老和尚和一個小和尚 老和尚正在給小和尚講故事 講的是什么故事呢 他說 從前 Recursion See Recursion Inordertounderstandrecursion onemustfirstunderstandrecursion C語言允許嵌套地調(diào)用函數(shù) 也就是說 在調(diào)用一個函數(shù)的過程中 又去調(diào)用另一個函數(shù) 函數(shù)的嵌套調(diào)用 voidmain study english voidstudy english reading listening writing voidlistening 函數(shù)的嵌套調(diào)用有一個特例 即遞歸調(diào)用 也就是說 在調(diào)用一個函數(shù)的過程中 又出現(xiàn)了直接或間接地去調(diào)用該函數(shù)本身 voidtell story intold monk young monk tell story tell story函數(shù)的遞歸調(diào)用 函數(shù)的遞歸調(diào)用 voidtell story staticintold monk young monk old monk old monk 1 年齡大了一歲young monk young monk 1 if old monk 60 遞歸形式tell story elseprintf 對不起 已退休 遞歸邊界 在語法上 簡單 遞歸即為普通的函數(shù)調(diào)用 在算法上 難 如何找到遞歸形式 如何找到遞歸邊界 如何編寫遞歸程序 遞歸算法的類型 遞歸算法可以分為兩種類型 基于分治策略的遞歸算法 基于回溯策略的遞歸算法 第八章遞歸算法 1 3 2 基本概念 基于回溯策略的遞歸 基于分治策略的遞歸 分而治之 divide and conquer 的算法設計思想 Divide 把問題劃分為若干個子問題 Conquer 以同樣的方式分別去處理各個子問題 Combine 把各個子問題的處理結(jié)果綜合起來 形成最終的處理結(jié)果 8 2 1分而治之 瑪特露什卡 調(diào)用 調(diào)用 調(diào)用 調(diào)用 調(diào)用 調(diào)用 如何編寫基于分治策略的遞歸程序 在算法分析上 要建立分治遞歸的思維方式 在編程實現(xiàn)上 要建立遞歸信心 Totursttherecursion JerryCain stanford 如何建立分治遞歸的思維方式 基本原則 目標驅(qū)動 計算n n n n 1 且1 1 fact 3 fact 2 fact 1 voidmain intn printf 請輸入一個整數(shù) scanf d 請輸入一個整數(shù) 33 6 調(diào)用和返回的遞歸示意圖 如何建立遞歸信心 函數(shù)的遞歸調(diào)用到底是如何進行的呢 在遞歸調(diào)用時 執(zhí)行的是不是相同的代碼 訪問的是不是相同的數(shù)據(jù) 如果是的話 那么大家會不會相互干擾 相互妨礙 voidmain intm printf 請輸入一個整數(shù) scanf d 8 2 2尋找最大值 問題描述 給定一個整型數(shù)組a 找出其中的最大值 如何設計相應的遞歸算法 如何來設計相應的遞歸算法 目標 max a 0 a 1 a n 1 可分解為 max a 0 max a 1 a n 1 另外已知max x x這就是遞歸算法的遞歸形式和遞歸邊界 據(jù)此可以編寫出相應的遞歸函數(shù) intMax inta intfirst intn intmax if first n 1 returna first max Max a first 1 n if max a first returna first elsereturnmax Max a 0 n 8 2 3折半查找法 問題描述 查找 Searching 根據(jù)給定的某個值 在一組數(shù)據(jù) 尤其是一個數(shù)組 當中 確定有沒有出現(xiàn)相同取值的數(shù)據(jù)元素 順序查找 折半查找 前提 數(shù)據(jù)是有序排列的 基本思路 將目標值與數(shù)組的中間元素進行比較 若相等 查找成功 否則根據(jù)比較的結(jié)果將查找范圍縮小一半 然后重復此過程 請問 4565926是否在此列表當中 請問 4565926是否在此列表當中 數(shù)組正中間的元素 請問 4565926是否在此列表當中 不予考慮 請問 4565926是否在此列表當中 正中間的元素 請問 4565926是否在此列表當中 正中間的元素 不予考慮 4565925 voidmain intb 05 13 19 21 37 56 64 75 80 88 92 intx 21 printf x位于數(shù)組的第 d個元素 n bsearch b x 0 10 如何用遞歸來實現(xiàn) 函數(shù)原型 intbsearch intb intx intL intR 遞歸的形式 遞歸的邊界 問題分析 intbsearch intb intx intL intR intmid if L R return 1 mid L R 2 if x b mid returnmid elseif x b mid returnbsearch b x L mid 1 elsereturnbsearch b x mid 1 R 8 2 4漢諾 Hanoi 塔問題 相傳在古印度Bramah廟中 有位僧人整天把三根柱子上的金盤倒來倒去 原來他是想把64個一個比一個小的金盤從一根柱子上移到另一根柱子上去 移動過程中遵守以下規(guī)則 每次只允許移動一只盤 且大盤不得落在小盤上 簡單嗎 若每秒移動一只盤子 需5800億年 A B C 怎樣編寫這種程序 思路上還是先從最簡單的情況分析起 搬一搬看 慢慢理出思路 1 在A柱上只有一只盤子 假定盤號為1 這時只需將該盤直接從A搬至C 記為movefromAtoC A B C 1 2 在A柱上有二只盤子 1為小盤2為大盤 分三步進行 A B C 2 1 movefromAtoB movefromAtoC moveformBtoC 3 在A柱上有3只盤子 從小到大分別為1號 2號 3號 怎么移 2 1 3 分七步 分三步進行 move2discsfromAtoBusingC movefromAtoC move2discsfromBtoCusingA 3 4 在A柱上有n個盤子 從小到大分別為1號 2號 3號 n號 第1步 將1號 2號 n 1號盤作為一個整體 在C的幫助下 從A移至B 第2步 將n號盤從A移至C 第3步 再將1號 2號 n 1號盤作為一個整體 在A的幫助下 從B移至C 這三步記為 moven 1discsfromAtoBusingC move1discsfromAtoC moven 1discsfromBtoCusingA 遞歸形式 定義函數(shù)move intn charL charM charR 表示movendiscsfromLtoRusingM 如果n 1 即表示movefromLtoR includevoidmove intn charL charM charR voidmain intn printf 請輸入一個整數(shù) scanf d L Leftpost M Middlepost R Rightpostvoidmove intn charL charM charR if n 1 printf move 1from cto c n L R else move n 1 L R M printf move dfrom cto c n n L R move n 1 M L R 請輸入一個整數(shù) 3move 1fromAtoCmove 2fromAtoBmove 1fromCtoBmove 3fromAtoCmove 1fromBtoAmove 2fromBtoCmove 1fromAtoC 一次運行結(jié)果 8 2 5青蛙過河 一條小溪尺寸不大 青蛙可以從左岸跳到右岸 在左岸有一石柱L 面積只容得下一只青蛙落腳 同樣右岸也有一石柱R 面積也只容得下一只青蛙落腳 有一隊青蛙從尺寸上一個比一個小 我們將青蛙從小到大 用1 2 n編號 規(guī)定初始時這隊青蛙只能趴在左岸的石頭L上 按編號一個落一個 小的落在大的上面 不允許大的在小的上面 在小溪中有S根石柱 有y片荷葉 規(guī)定溪中的柱子上允許一只青蛙落腳 如有多只同樣要求按編號一個落一個 大的在下 小的在上 而且必須編號相鄰 對于荷葉只允許一只青蛙落腳 不允許多只在其上 對于右岸的石柱R 與左岸的石柱L一樣允許多個青蛙落腳 但須一個落一個 小的在上 大的在下 且編號相鄰 當青蛙從左岸的L上跳走后就不允許再跳回來 同樣 從左岸L上跳至右岸R 或從溪中荷葉或溪中石柱跳至右岸R上的青蛙也不允許再離開 問在已知溪中有S根石柱和y片荷葉的情況下 最多能跳過多少只青蛙 這題看起來較難 但是如果我們認真分析 理出思路 就可化難為易 思路 1 簡化問題 探索規(guī)律 先從個別再到一般 要善于對多個因素作分解 孤立出一個一個因素來分析 化難為易 2 定義函數(shù)Jump S y 最多可跳過河的青蛙數(shù)其中 S 河中柱子數(shù)y 荷葉數(shù) 2說明 河中有一片荷葉 可以過兩只青蛙 起始時L上有兩只青蛙 1 在2 上面 第一步 1 跳到荷葉上 第二步 2 從L直接跳至R上 第三步 1 再從荷葉跳至R上 如下圖 3 先看簡單情況 河中無柱子 S 0 Jump 0 y 當y 1時 Jump 0 1 3說明 河中有兩片荷葉時 可以過3只青蛙 起始時 1 2 3 3只青蛙落在L上 第一步 1 從L跳至葉1上 第二步 2 從L跳至葉2上 第三步 3 從L直接跳至R上 第四步 2 從葉2跳至R上 第五步 1 從葉1跳至R上 采用歸納法 Jump 0 y 當y 2時 Jump 0 2 y 1 意思是 在河中沒有石柱的情況下 過河的青蛙數(shù)僅取決于荷葉數(shù) 數(shù)目是荷葉數(shù) 1 再看Jump S y 先看一個最簡單情況 S 1 y 1 從圖上看出需要步 跳過只青蛙 941 青蛙從L Y 2 青蛙從L S 1 青蛙從Y S 3 青蛙從L Y 4 青蛙從L R 3 青蛙從Y R 1 青蛙從S Y 2 青蛙從S R 1 青蛙從Y R 對于S 1 y 1的情形 從另外一個角度來分析若沒有石柱S 最多可過y 1 2只青蛙 有了石柱S后 最多可過2 2 4只青蛙 步驟1 1 和2 從L S 步驟2 3 和4 從L R 步驟3 1 和2 從S R Y S L R 1 2 3 4 1 2 Y Y Y 對于S 1 y 1的情形若沒有石柱S 最多可過y 1只青蛙 有了石柱S后 最多可過2 y 1 只青蛙 步驟1 前y 1只從L S 步驟2 后y 1只從L R 步驟3 前y 1只從S R Y S L R 前y 1只 后y 1只 前y 1只 Y Y Y 對于S 2 y 1的情形若只有石柱S1 最多可過2 y 1 只青蛙 有了石柱S2后 最多可過只青蛙 Y S1 L R 4 y 1 S2 采用歸納法 可得出如下的遞歸形式 Jump S y 2 Jump S 1 y 意思是 先讓一半的青蛙利用y片荷葉和S 1根石柱 落在河中剩下的那根石柱上 然后讓另一半的青蛙利用y片荷葉和S 1根石柱 落在右岸的R上面 最后再讓先前的一半青蛙 利用y片荷葉和S 1根石柱 落在右岸的R上面 遞歸邊界 Jump 0 y y 1 voidmain intS y printf 請輸入石柱和荷葉的數(shù)目 scanf d d 8 2 6快速排序 快速排序的基本思路 1 在數(shù)組a中 有一段待排序的數(shù)據(jù) 下標從l到r 2 取a l 放在變量value中 通過由右 左兩邊對value的取值的比較 為value選擇應該排定的位置 這時要將比value大的數(shù)放右邊 比它小的數(shù)放左邊 當value到達最終位置后 如下標m 由它劃分了左右兩個集合 l m 1 m 1 r 然后轉(zhuǎn)第1步 再用相同的思路分別去處理左集合和右集合 令qsort l r 表示將數(shù)組元素從下標為l到下標為r的共r l 1個元素進行從小到大的快速排序 目標 1 讓value a l 2 將value放在a m 中 l m r3 使a l a l 1 a m 1 a m 4 使a m a m 1 a m 2 a r 例子 數(shù)組a當中有7個元素等待排序 l r 首先 讓value a l a 0 5 value 5 a 0 1 2 3 4 5 6 下標 第二步 從r 6開始 將a r 與value進行比較 若a r value 則r 繼續(xù)比較 否則 a l a r l value 5 a 0 1 2 3 4 5 6 下標 4 第三步 從l 1開始 將a l 與value進行比較 若a l value 則l 繼續(xù)比較 否則 a r a l r value 5 a 0 1 2 3 4 5 6 下標 6 又回到第二步 從r 5開始 將a r 與value進行比較 若a r value 則r 繼續(xù)比較 否則a l a r l value 5 a 0 1 2 3 4 5 6 下標 3 又回到第三步 從l 3開始 將a l 與value進行比較 若a l value 則l 繼續(xù)比較 否則 a r a l r value 5 a 0 1 2 3 4 5 6 下標 7 現(xiàn)在l r 已經(jīng)找到了value的正確位置 把value中的值放回到數(shù)組當中 value 5 a 0 1 2 3 4 5 6 下標 5 下面的任務 用剛才介紹的方法 對5左 右兩側(cè)的兩段數(shù)據(jù) 分別進行排序 a 0 1 2 3 4 5 6 下標 最后的結(jié)果 a 0 1 2 3 4 5 6 下標 具體實現(xiàn) 幾重循環(huán)語句 參考程序 略 第八章遞歸算法 1 3 2 基本概念 基于回溯策略的遞歸 基于分治策略的遞歸 在程序設計當中 有相當一類求一組解 或求全部解或求最優(yōu)解的問題 不是根據(jù)某種確定的計算法則 而是利用試探和回溯 Backtracking 的搜索技術(shù)求解 回溯法也是設計遞歸算法的一種重要方法 它的求解過程實質(zhì)上是一個先序遍歷一棵 狀態(tài)樹 的過程 只不過這棵樹不是預先建立的 而是隱含在遍歷的過程當中 8 3 1分書問題 有五本書 它們的編號分別為1 2 3 4 5 現(xiàn)準備分給A B C D E五個人 每個人的閱讀興趣用一個二維數(shù)組來加以描述 希望編寫一個程序 輸出所有的分書方案 讓人人皆大歡喜 假定這5個人對這5本書的閱讀興趣如下表 12345ABCDE 人 書 解題思路 1 定義一個整型的二維數(shù)組 將上表中的閱讀喜好用初始化的方法賦給這個二維數(shù)組 可定義 intLike 6 6 0 0 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 2 定義一個整型一維數(shù)組BookFlag 6 用來記錄書是否已被選用 用后五個下標作為五本書的標號 被選用的元素值為1 未被選用的值為0 初始化皆為0 intBookFlag 6 0 3 定義一個整型一維數(shù)組BookTaken 6 用來記錄每一個人選用了哪一本書 用數(shù)組元素的下標來作為人的標號 用數(shù)組元素的值來表示書號 如果某個人還沒有選好書 則相應的元素值為0 初始化時 所有的元素值均為0 intBookTaken 6 0 4 循環(huán)變量i表示人 j表示書 i j 1 2 3 4 5 一種方法 枚舉法 把所有可能出現(xiàn)的分書方案都枚舉出來 然后逐一判斷它們是否滿足條件 即是否使得每個人都能夠得到他所喜歡的書 缺點 計算量太大 如何抽取出遞歸形式 voidperson inti intLike 6 6 0 0 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 intBookFlag 6 0 intBookTaken 6 0 voidmain person 1 voidperson inti 嘗試給第i個人分書 intj k for j 1 j 5 j 嘗試把每本書分給第i個人 if BookFlag j 0 Like i j 0 continue 失敗BookTaken i j 把第j本書分給第i個人BookFlag j 1 if i 5 已找到一種分書方案for k 1 k 5 k printf d BookTaken k printf n else person i 1 給第i 1個人分書 BookTaken i 0 回溯 把這一次分得的書退回BookFlag j 0 8 3 2下樓問題 從樓上走到樓下共有h個臺階 每一步有三種走法 走一個臺階 走二個臺階 走三個臺階 問可以走出多少種方案 希望用遞歸思想來編程 數(shù)據(jù)的定義 j 1 2 3 表示在每一步可以試著走的臺階數(shù)s 表示步數(shù)i 表示當前的高度 pace s 保存第s步走過的臺階數(shù) 基本思路 讓i先取h值 然后在下樓時 試著一步一步地走 從高到低 每走一步i的值就會減去這一步所走的臺階數(shù)j 即i h 初值 以后i i j j 1 2 3 當i 0時 說明已走到樓下 每一步都要試j的三種不同取值 即或者為1 或者為2 或者為3 這時可用for循環(huán)結(jié)構(gòu) 每一步走法都用相同的策略 故可以用遞歸算法 定義TryStep i s 站在第i級臺階上往下試走第s步的過程 如何實現(xiàn) 第一步 j 1 第二步 如果j i 表明這一步不可能走j級臺階 函數(shù)返回 否則 轉(zhuǎn)第三步 第三步 這一步走j級臺階 即pace s j 如果i j 0 說明已經(jīng)到達地面了 也就是已經(jīng)找到一種方案了 把它顯示出來 否則的話 接著走下一步 TryStep i j s 1 第四步 j j 1 如果j 3 轉(zhuǎn)第二步 否則函數(shù)結(jié)束 能否用分治策略 8 3 3八皇后問題 在8 8的棋盤上 放置8個皇后 棋子 使兩兩之間互不攻擊 所謂互不攻擊是說任何兩個皇后都要滿足 1 不在棋盤的同一行 2 不在棋盤的同一列 3 不在棋盤的同一對角線上 因此可以推論出 棋盤共有8行 故至多有8個皇后 即每一行有且僅有一個皇后 這8個皇后中的每一個應該擺放在哪一列上是解該題的任務 數(shù)據(jù)的定義 1 i 第i行 個 皇后 1 i 8 j 第j列 1 j 8 Queen i 第i行皇后所在的列 Column j 第j列是否安全 0 1 12345678 1 2 3 4 5 6 7 8 數(shù)據(jù)的定義 2 Down 7 7 記錄每一條從上到下的對角線 是否安全 0 1 Up 2 16 記錄每一條從下到上的對角角線 是否安全 0 1 利用以上的數(shù)據(jù)定義 當我們需要在棋盤的 i j 位置擺放一個皇后的時候 可以通過Column數(shù)組 Down數(shù)組和Up數(shù)組的相應元素 來判斷該位置是否安全 當我們已經(jīng)在棋盤的 i j 位置擺放了一個皇后以后 就應該去修改Column數(shù)組 Down數(shù)組和Up數(shù)組的相應元素 把相應的列和對角線設置為不安全 voidTryQueen inti intQueen 9 0 intColumn 9 0 intDown 15 0 intUp 15 0 voidmain TryQueen 1 voidTryQueen inti 擺放第i行的皇后 intj k for j 1 j 8 j 嘗試把該皇后放在每一列 if Column j Down i j 7 Up i j 2 continue 失敗Queen i j 把該皇后放在第j列上Column j 1 Down i j 7 1 Up i j 2 1 if i 8 已找到一種解決方案 for k 1 k 8 k printf d Queen k printf n elseTryQueen i 1 擺放第i 1行的皇后Queen i 0 回溯 把該皇后從第j列拿起Column j 0 Down i j 7 0 Up i j 2 0 共92組解 部分答案如下 方案1 15863724方案2 16837425方案3 17468253方案4 17582463方案5 24683175方案6 25713864方案7 25741863方案8 26174835方案9 26831475方案10 27368514 假設在棋盤上事先已經(jīng)擺放了一個國王 位置為 即第X行第Y列 在擺放八個皇后時 要求皇后間不能互相攻擊且不能被國王攻擊 國王的攻擊范圍如下圖所示 思考題 對題目做如下的修改 先輸入某一個皇后所在的位置 即第X行第Y列 在此情形下 如何擺放其余的7個皇后 要求找到所有解決方案 8 3 4過河問題 問題描述 M條狼和N條狗 N M 渡船過河 從河西到河東 在每次航行中 該船最多能容納2只動物 且最少需搭載1只動物 安全限制 無論在河東 河西還是船上 狗的數(shù)量不能小于狼的數(shù)量 請問 能否找到一種方案 使所有動物都能順利過河 如果能 移動的步驟是什么 如何描述系統(tǒng)的當前狀態(tài) 位置 河西岸 河東岸 河 對象 船 狼 狗 問題分析 三元組 W D B Wolf Dog Boat 例如 2 2 W 若M 2 N 2 2 2 W 0 2 E 1 2 W 0 0 E 2 0 W 1 0 E 問題實質(zhì) 在一個有向圖中尋找一條路徑 狀態(tài)轉(zhuǎn)換 如何從一個結(jié)點跳轉(zhuǎn)到另一個結(jié)點 狀態(tài)樹 問題分析 如何避免訪問重復的結(jié)點 如何用簡練的語句實現(xiàn)狀態(tài)的轉(zhuǎn)換 如何將5種情形歸納為同一種形式 技術(shù)難點 include defineMAX M20 defineMAX N20intM N structStatus intW D B steps 1000 ints 0 num 0 intflags MAX M MAX N 2 0 voidCrossRiver intW intD intB intIsValid intw intd intb voidmain scanf d d if B 0 f 1 elsef 1 for j 1 j 5 j switch j case1 w W f 1 d D break case2 w W f 2 d D break case3 d D f 1 w W break case4 d D f 2 w W break case5 w W f 1 d D f 1 break b 1 B if IsValid w d b flags w d b 1 steps s W w steps s D d steps s B b s if w 0 intIsValid intw intd intb if wM return0 if dN return0 if flags w d b 1 return0 if d 0 22Solutions1 220021120101200001Solutions2 220021120101110001 Solutions3 220111120101200001Solutions4 220111120101110001 8 3 5排列問題 n個對象的一個排列 就是把這n個不同的對象放在同一行上的一種安排 例如 對于三個對象a b c 總共有6個排列 abcacbbacbcacabcban個對象的排列個數(shù)就是n 如何生成排列 基于分治策略的遞歸算法 假設這n個對象為1 2 3 n 對于前n 1個元素的每一個排列a1a2 an 1 1 ai n 1 通過在所有可能的位置上插入數(shù)字n 來形成n個所求的排列 即 na1a2 an 1a1na2 an 1 a1a2 nan 1a1a2 an 1n 例如 生成1 2 3的所有排列 permutation 3 permutation 2 permutation 1 permutation 1 1 permutation 2 21 12 permutation 3 321 231 213 312 132 123 基于回溯策略的遞歸算法 基本思路 每一個排列的長度為N 對這N個不同的位置 按照順序逐一地枚舉所有可能出現(xiàn)的數(shù)字 定義一維數(shù)組NumFlag N 1 用來記錄1 N之間的每一個數(shù)字是否已被使用 1表示已使用