《算法語言與數(shù)據結構(第5章).ppt》由會員分享，可在線閱讀，更多相關《算法語言與數(shù)據結構(第5章).ppt（174頁珍藏版）》請在裝配圖網上搜索。

算法語言與數(shù)據結構 信息與物流管理系王健 西安財經學院管理學院 第5章函數(shù) 第5章函數(shù) 程序 6 3 cpp 驗證素數(shù)程序 作者 wuwh 編制時間 2002年10月20日 主要功能 可驗證某數(shù)是否為素數(shù) include 預編譯命令 include 預編譯命令intcheckprime int 子函數(shù)聲明intmain 主函數(shù) inta 0 定義整型變量 初始化為0cout a 鍵盤輸入一個整數(shù) 用實參a調用子函數(shù) 該子函數(shù)的 返回值作為if語句的分支條件if checkprime a checkprime a 為1cout a 是素數(shù) endl else checkprime a 為0cout a 不是素數(shù) endl 主函數(shù)結束 第5章函數(shù) 用實參a調用子函數(shù) 該子函數(shù)的 返回值作為if語句的分支條件if checkprime a checkprime a 為1cout a 是素數(shù) endl else checkprime a 為0cout a 不是素數(shù) endl 主函數(shù)結束 第5章函數(shù) Tcheckprime a Fcout a cout a 是素數(shù) endl 不是素數(shù) endl 第5章函數(shù) boolcheckprime intb 子函數(shù) b為形式參數(shù) intk 0 定義整型變量 并初始化for k 2 k sqrt double b k 循環(huán) if b k 0 如果b能夠被k整除 則返回0 可理解為 搶先 返回0 有了return0 后面的return1不起作用了return0 return1 b不能被k整除 則返回1 第5章函數(shù) boolcheckprime intb intk 0 for k 2 k sqrt double b k if b k 0 return0 return1 第5章函數(shù) boolcheckprime intb 子函數(shù) intk 0 形式參數(shù)for k 2 k sqrt double b k K 1 if b k 0 return0 return1 b不能被k整除 則返回1 說明b是質數(shù) 第5章函數(shù) 講這一程序的目的 如何定義一個函數(shù)主函數(shù)怎樣調用子函數(shù)實在參數(shù)和形式參數(shù)返回值是什么意思 主函數(shù)與子函數(shù)的配合 主函數(shù)通過實參去調用子函數(shù)將實參賦給子函數(shù)中的形參 子函數(shù)運算之后 又將調用結果返回給主函數(shù)一個值 這個值作為主函數(shù)判斷該實參是素數(shù)與否的根據 兩者配合得天衣無縫 第5章函數(shù) 在checkprime intb 函數(shù)中 有return0和return1兩處不同 如果先有return0了 后面一條return1就不起作用了 不會既執(zhí)行return0又執(zhí)行return1 第5章函數(shù) 函數(shù)的說明放在主函數(shù)之前 告訴系統(tǒng)有自定義的子函數(shù)可以被調用 例 boolcheckprime int 函數(shù)的定義函數(shù)返回值的類型函數(shù)名 類型名形式參數(shù)1 類型名形式參數(shù)2 函數(shù)體說明部分語句部分 形式參數(shù)和實在參數(shù)boolcheckprime intaf 定義af是形式參數(shù) 特點 1 未被調用不占內存單元 2 被調用后系統(tǒng)為其分配內存單元 3 調用結束釋放內存單元 4 作用域限定在子函數(shù)內 屬于局部變量 被調用函數(shù)嵌套在if語句中 a是實在參數(shù)if checkPrime a 主函數(shù)調用checkPrime af 子函數(shù)形式參數(shù) 實在參數(shù)是一個具有確定值的表達式一個函數(shù)在調用子函數(shù)時 要將實在參數(shù)賦給形式參數(shù)調用時1717實在參數(shù)a形式參數(shù)af 調用輸入a子函數(shù)if checkPrime a checkPrime af 執(zhí)行if語句for i 2 3 1 0af i 0 0輸出輸出return0return1a是質數(shù)a不是質數(shù)返回 intmain inta 0 cout a if checkprime a boolcheckprime intb intk 0 for k 2 k sqrt double b k if b k 0 return0 return1 cout a 是素數(shù) endl elsecout a 不是素數(shù) endl 美聲唱法歌手大獎賽裁判人數(shù)n 10 打分范圍60 x 100 10人中打分的最大值max10人中打分的最小值min10人打分總和為sum選手最后得分為 sum Max Min N 2 程序 6 2 cpp 作者 wuwh 編制時間 2002年10月20日 主要功能 給歌手打分 include includeintMax int int intMin int int intmain intp 0 intq 100 intsum 0 x 0 inti 1 for i 1 i x p Max x p q Min x q sum sum x cout 選手得分 sum p q 10 2 intMax inta intb if a b returna elsereturnb intMin intc intd if c d returnc elsereturnd 問題 編程求解 現(xiàn)假定n 6 k 4思路 1 該式可分解為2 定義一個函數(shù) i 1 2 nl k 讓l 4 i 1 2 6這個函數(shù)可以表示 3 再定義一個函數(shù)讓m n i 1 2 m 即可得解 程序 6 2 cpp 作者 wuwh 編制時間 2002年10月12日 主要功能 求冪函數(shù)的和 介紹函數(shù) include 預編譯命令constintn 6 定義常量n為6constintk 4 定義常量k為4intSOP intm intl 聲明函數(shù)SOPintpower intp intq 聲明函數(shù)power 輸出結果 其中SOP n k 為被調用函數(shù)intmain 主函數(shù) cout Sumof k 提示信息 fromthpowersofintegers1to n is SOP n k endl 以下函數(shù)是被主程序調用的函數(shù) 功能 計算1 2 m的l次冪的和intSOP intm intl m l為形參 inti sum sum 0 初始化累加器for i 1 i m i sum sum power i l 累加returnsum 返回值 以下函數(shù)是被函數(shù)sop n k 調用的函數(shù) 功能 計算p的q次冪intpower intp intq inti product product 1 初始化累乘器for i 1 i q i product product p 累乘returnproduct intSOP intm intl m6l4power 1 l 1intpower intp intq power 2 l 116intpower intp intq 16power m l 1296intpower intp intq 22751296 數(shù)據類型函數(shù)名 形式參數(shù)表 例 intpower intp intn power為函數(shù)名 要以英文字母開頭 int是函數(shù)值的數(shù)據類型 這里是int 整型 intp intn 括號中的p n為函數(shù)的形式參數(shù) 形式參數(shù)也要定義其數(shù)據類型 函數(shù)定義的一般格式 形式參數(shù)與實在參數(shù) 1 形式參數(shù)是在定義函數(shù)時放在函數(shù)名后括號中的參數(shù) 在未進行函數(shù)調用時 并不對形式參數(shù)分配內存單元 在發(fā)生函數(shù)調用時 立刻給形式參數(shù)分配內存單元 調用結束后 釋放掉行參所占的內存單元 2 因此 形參變量屬于局部變量 其作用域在它所在的函數(shù)體內 3 在定義函數(shù)的時候 必須指定形參變量的類型 如下所示 intpower intp intn 函數(shù)體 c 4 實在參數(shù)是一個具有確定值的表達式 函數(shù)在調用時 將實在參數(shù)賦給形式參數(shù) 比如 主函數(shù)調用SOP n k 這時 n k為實在參數(shù) n的值為6 k的值為4 在被調用函數(shù)定義中 intSOP m l 中的m l為形式參數(shù) 在SOP被調用時 系統(tǒng)給m l這兩個形式參數(shù)分配了內存單元 之后 n的值6賦給m k的值4賦給l power i l 處在SOP m l 函數(shù)中 表示SOP函數(shù)去調用power函數(shù) 其中i l為實在參數(shù) 而intpower p q 中的p q為形式參數(shù) 比如 執(zhí)行SOP 6 4 時 l 4 m 6 當i 1時 sum sum power 1 4 這里1 4為實在參數(shù) 調用power p q 兩個形式參數(shù)p q分別被賦以1 4 遞推是計算機數(shù)值計算中的一個重要算法 可以將復雜的運算化為若干重復的簡單運算 充分發(fā)揮計算機長于重復處理的特點 現(xiàn)舉一例 遞推 例5 3 A B C D E五人合伙夜間捕魚 凌晨時都疲憊不堪 各自在河邊的樹叢中找地方睡著了 日上三竿 A第一個醒來 他將魚平分作五份 把多余的一條扔回湖中 拿自己的一份回家去了 B第二個醒來 也將魚平分為五份 扔掉多余的一條 只拿走自己的一份 接著C D E依次醒來 也都按同樣的辦法分魚 問五人至少合伙捕到多少條魚 每個人醒來后看到的魚數(shù)是多少條 解題思路 假定A B C D E五人的編號分別為1 2 3 4 5 整數(shù)數(shù)組fish k 表示第k個人所看到的魚數(shù) fish 1 表示A所看到的魚數(shù) fish 2 表示B所看到的魚數(shù) fish 1 為五人合伙捕魚的總魚數(shù)fish 2 fish 1 1 4 5fish 3 fish 2 1 4 5fish 4 fish 3 1 4 5fish 5 fish 4 1 4 5 寫成一般式fish i fish i 1 1 4 5i 2 3 5這個公式可用于知A看到的魚數(shù)去推算B看到的 再推算C看到的 現(xiàn)在要求的是A看到的 能否倒過來 先知E看到的再反推D看到的 直到A看到的 為此將上式改寫為 fish i 1 fish i 5 4 1i 5 4 2 分析上式 當i 5時 fish 5 表示E醒來所看到的魚數(shù) 該數(shù)應滿足被 整除后余 即fish 5 5 12 當i 5時 fish i 1 表示D醒來所看到的魚數(shù) 這個數(shù)既要滿足fish 4 fish 5 5 4 1又要滿足fish 4 5 1顯然 fish 4 不能不是整數(shù) 這個結論同樣可以用至fish 3 fish 2 和fish 1 3 按題意要求5人合伙捕到的最少魚數(shù) 可以從小往大枚舉 可以先讓E所看到的魚數(shù)最少為6條 即fish 5 初始化為6來試 之后每次增加5再試 直至遞推到fish 1 得整數(shù)且除以5之后的余數(shù)為1 根據上述思路 我們可以構思如下的程序框圖 該圖可分為三部分 1 是說明部分 包含定義數(shù)組fish 6 并初始化為1和定義循環(huán)控制變量i 并初始化為0 2 是do while直到型循環(huán) 其循環(huán)體又含兩塊 2 1是枚舉過程中的fish 5 的初值設置 一開始fish 5 1 5 以后每次增5 2 2是一個for循環(huán) i的初值為4 終值為1 步長為 1 該循環(huán)的循環(huán)體是一個分支語句 如果fish i 1 不能被4整除 則跳出for循環(huán) 使用break語句 否則 從fish i 1 算出fish i 當由break語句讓程序退出循環(huán)時 意味著某人看到的魚數(shù)不是整數(shù) 當然不是所求 必須令fish 5 加5后再試 即重新進入直到型循環(huán)dowhile的循環(huán)體 當著正常退出for循環(huán)時 一定是控制變量i從初值4 一步一步執(zhí)行到終值1 每一步的魚數(shù)均為整數(shù) 最后i 0 表示計算完畢 且也達到了退出直到型循環(huán)的條件 3 輸出計算結果 程序名 5 3 c 五人合伙捕魚 作者 wuwh 編制時間 2002年10月2日 主要功能 遞推算法的實現(xiàn) include 預編譯命令voidmain 主函數(shù) intfish 6 1 1 1 1 1 1 整型數(shù)組 記錄每人醒來后看到的魚數(shù)inti 0 do fish 5 fish 5 5 讓E看到的魚數(shù)增5 for i 4 i 1 i if fish i 1 4 0 break 跳出for循環(huán)elsefish i fish i 1 5 4 1 計算第i人看到的魚數(shù) while i 1 當i 1繼續(xù)做do循環(huán) 輸出計算結果for i 1 i 5 i printf fish d d I fish i 3121A2496B1996C1596D1276E 遞推數(shù)列的定義一個數(shù)列從某一項起 它的任何一項都可以用它前面的若干項來確定 這樣的數(shù)列稱為遞推數(shù)列 表示某項與前面若干項的關系稱為遞推公式 例如 1 2 n 1 n 令fact n 為n的階乘fact n n fact n 1 通項公式 fact 1 1 邊界條件 遞歸 遞歸算法在可計算性理論中占有重要地位 它是算法設計的有力工具 對于拓展編程思路非常有用 就遞歸算法而言并不涉及高深數(shù)學知識 只不過初學者要建立起遞歸概念不十分容易 我們先從一個最簡單的例子導入 遞歸及其實現(xiàn) 用遞歸算法求n 定義 函數(shù)fact n n fact n 1 n 1 則有fact n nfact n 1 已知fact 1 1 為了表述得直觀清晰 我們定義兩個結點 或結點和與結點 圖示的直觀性與思維助力 1 或結點 A為 或結點 A依不同條件會有兩種不同的取值 B或C 結點用表示 如果有多于2種取值 可用下圖 條件為Z1 Z2 Zn 取值為B或C 或G 2 與結點 與結點要涂實心 相關聯(lián)的B與C之間要用弧線連起來 A為與結點 A的最終取值為C結點的值 但為了求得C的值 得先求出B結點的值 C是B的函數(shù) 仍以求n 為例畫出如下與或圖 A為或結點 B為直接可解結點 值為1 C為與結點 當n 1時 A的取值即C的值 而C的值即E的值 為了求得E的值 需要先求出D的值 D值fact n 1 乘以n即為E的值 與結點可能有多個相關聯(lián)的點 這時可描述為下圖 A結點的值最終為D的值 但為了求D需先求B和C 從圖上看 先求左邊的點才能求最右邊的點的值 我們約定最右邊D點的值就是A結點的值 下面我們以3 為例來畫與或結點圖 目的是體會遞歸的含義 C 1D 2 C 2B D 2E 3 B 3 2 6A E 6 下面畫出了調用和返回的遞歸示意圖 從圖可以想象 欲求fact 3 先要求fact 2 要求fact 2 先求fact 1 就象剝一顆圓白菜 從外向里 一層層剝下來 到了菜心 遇到1的階乘 其值為1 到達了遞歸的邊界 然后再用fact n n fact n 1 這個普遍公式 從里向外倒推回去得到fact n 的值 為了把這個問題說得再透徹一點 我們畫了如下的流程圖 為了形象地描述遞歸過程 將上圖改畫成下圖 在這個圖中 內層 與 外層 有著相同的結構 它們之間 你中有我 我中有你 呈現(xiàn)相互依存的關系 為了進一步講清遞歸的概念 將遞歸與遞推做一比較 仍以求階乘為例 遞推是從已知的初始條件出發(fā) 逐次去求所需要的階乘值 如求3 初始條件fact 1 1fact 2 2 fact 1 2fact 3 3 fact 2 6 這相當于從菜心 推到 外層 而遞歸算法的出發(fā)點不放在初始條件上 而放在求解的目標上 從所求的未知項出發(fā)逐次調用本身的求解過程 直到遞歸的邊界 即初始條件 就本例而言 讀者會認為遞歸算法可能是多余的 費力而不討好 但許多實際問題不可能或不容易找到顯而易見的遞推關系 這時遞歸算法就表現(xiàn)出了明顯的優(yōu)越性 下面我們將會看到 遞歸算法比較符合人的思維方式 邏輯性強 可將問題描述得簡單扼要 具有良好的可讀性 易于理解 許多看來相當復雜 或難以下手的問題 如果能夠使用遞歸算法就會使問題變得易于處理 下面舉一個盡人皆知的例子哈諾 Hanoi 塔問題 故事 相傳在古代印度的Bramah廟中 有位僧人整天把三根柱子上的金盤倒來倒去 原來他是想把64個一個比一個小的金盤從一根柱子上移到另一根柱子上去 移動過程中恪守下述規(guī)則 每次只允許移動一只盤 且大盤不得落在小盤上面 有人會覺得這很簡單 真的動手移盤就會發(fā)現(xiàn) 如以每秒移動一只盤子的話 按照上述規(guī)則將64只盤子從一個柱子移至另一個柱子上 所需時間約為5800億年 怎樣編寫這種程序 思路上還是先從最簡單的情況分析起 搬一搬看 慢慢理出思路 1 在A柱上只有一只盤子 假定盤號為1 這時只需將該盤從A搬至C 一次完成 記為move1fromAtoC 演示 1 2 在A柱上有二只盤子 1為小盤 2為大盤 第 1 步將1號盤從A移至B 這是為了讓2號盤能移動 第 2 步將2號盤從A移至C 第 3 步再將1號盤從B移至C 這三步記為 演示 2 1 move1fromAtoB move2fromAtoC move3formBtoC 3 在A柱上有3只盤子 從小到大分別為1號 2號 3號第 1 步將1號盤和2號盤視為一個整體 先將二者作為整體從A移至B 給3號盤創(chuàng)造能夠一次移至C的機會 這一步記為move 2 A C B 意思是將上面的2只盤子作為整體從A借助C移至B 第 2 步將3號盤從A移至C 一次到位 記為move3fromAtoC第 3 步處于B上的作為一個整體的2只盤子 再移至C 這一步記為move 2 B A C 意思是將2只盤子作為整體從B借助A移至C 所謂借助是什么意思 等這件事做完了不言自明 move 3 A B C 3 演示 移動3個盤子的分解 move 3 A B C 2 1 3 4 從題目的約束條件看 大盤上可以隨便摞小盤 相反則不允許 在將1號和2號盤當整體從A移至B的過程中move 2 A C B 實際上是分解為以下三步第 1 1步 move1formAtoC 第 1 2步 move2formAtoB 第 1 3步 move1formCtoB 經過以上步驟 將1號和2號盤作為整體從A移至B 為3號盤從A移至C創(chuàng)造了條件 同樣 3號盤一旦到了C 就要考慮如何實現(xiàn)將1號和2號盤當整體從B移至C的過程了 實際上move 2 B A C 也要分解為三步 第 3 1步 move1formBtoA 第 3 2步 move2formBtoC 第 3 3步 move1formAtoC 5 看move 2 A C B 是說要將2只盤子從A搬至B 但沒有C是不行的 因為第 1 1步就要將1盤從A移到C 給2盤創(chuàng)造條件從A移至B 然后再把1盤從C移至B 看到這里就能明白借助C的含義了 因此 在構思搬移過程的參量時 要把3個柱子都用上 6 定義搬移函數(shù)move n A B C 物理意義是將n只盤子從A經B搬到C 考慮到前面已經研究過的 1 2 3 步 可以將搬移過程用如下的與或結點圖表示 這里用與或結點的含義是分解為 1 2 3 步 這3步是相關的 相互依存的 而且是有序的 從左至右執(zhí)行 move n A B C 分解為3步 1 move n 1 A C B 理解為將上面的n 1只盤子作為一個整體從A經C移至B 2 輸出n AtoC 理解將n號盤從A移至C 是直接可解結點 3 Move n 1 B A C 理解為將上面的n 1只盤子作為一個整體從B經A移至C 這里顯然是一種遞歸定義 當著解move n 1 A C B 時又可想到 將其分解為3步 第1步 將上面的n 2只盤子作為一個整體從A經B到C move n 2 A B C 第2步 第n 1號盤子從A直接移至B 即n 1 AtoB 第3步 再將上面的n 2只盤子作為一個整體從C經A移至B move n 2 C A B 下面 我們還是以3只盤子為例畫出遞歸的與或圖 這個圖很象一顆倒置著的樹 結點move 3 A B C 是樹根 與結點是樹的分枝 葉子都是直接可解結點 程序 6 hanoi2002 cpp 作者 wuwh 編制時間 2002年10月13日 主要功能 用遞歸求解Hanoi問題 include 預編譯命令intstep 1 整型全局變量 預置1 步數(shù)voidmove intm charp charq charr 聲明要用到的被調用函數(shù)voidmain 主函數(shù) 主程序開始intn 整型變量 n為盤數(shù) printf 請輸入盤數(shù)n 提示信息scanf d 調用函數(shù)move n a b c 主函數(shù)結束 以下函數(shù)是被主程序調用的函數(shù) 函數(shù)名 move 輸入 m 整型變量 表示盤子數(shù)目 p q r為字符型變量 表示柱子標號 返回值 無voidmove intm charp charq charr 自定義函數(shù)體開始if m 1 如果m為1 則為直接可解結點 直接可解結點 輸出移盤信息printf d move1 fromptor step step 步數(shù)加1 else 如果不為1 則要調用move m 1 move m 1 p r q 遞歸調用move m 1 直接可解結點 輸出移盤信息printf d move dfromptor step m step 步數(shù)加1move m 1 q p r 遞歸調用move m 1 自定義函數(shù)體結束 m n n 1c m n m 0 n 0n mn m c m 1 n c m 1 n 1 c m 1 n c m 1 n 1 0m1 程序 6 7 cpp 編制時間 2002年10月28日 主要功能 計算組和數(shù)C m n include 預編譯命令Usingnamespacestd 計算C m n 即從m個數(shù)中取n個數(shù)的組合數(shù)intC intm intn if m 0 n 0 m n return0 if m n C m m 1return1 if n 1 C m 1 mreturnm C m n C m 1 n C m 1 n 1 returnC m 1 n C m 1 n 1 intmain 主函數(shù)開始 測試一些結果cout C 6 0 Cmn 6 0 endl cout C 6 1 Cmn 6 1 endl cout C 6 2 Cmn 6 2 endl cout C 6 6 Cmn 6 6 endl return0 主函數(shù)結束 遞歸算法舉例 青蛙過河 討論問題 青蛙過河 該題是2000年全國青少年信息學奧林匹克的一道試題 敘述如下 一條小溪尺寸不大 青蛙可以從左岸跳到右岸 在左岸有一石柱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ù) 3 先看簡單情況 河中無柱子 S 0 Jump 0 y 當y 1時 Jump 0 1 2 第一步 1 跳到荷葉上 第二步 2 從L直接跳至R上 第三步 1 再從荷葉跳至R上 如下圖 1 2 當y 2時 Jump 0 2 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 1 再看Jump S y 先看一個最簡單情況 S 1 y 1 從圖上看出需要9步 跳過4只青蛙 1 青蛙從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 表一 為了將過河過程描述得更清楚 我們給出了表1 表中L1L2L3L4表示左岸石柱上落在一起的青蛙的高度位置 L1在最上面 L4在最下面的位置 引入這個信息就可比較容易地看出對青蛙占位的約束條件 同理R1R2R3R4也是如此 對水中石柱S 也分成兩個高度位置S1S2 對荷葉Y無須分層 因為它只允許一只青蛙落在其上 t 0為初始時刻 青蛙從小到大落在石柱L上 t 1為第一步 1 從L跳至荷葉Y上 L上只剩2 3 4 T 2為第二步 2 從L跳至石柱S上 處在S2位置上 L上只剩3 和4 T 3為第三步 1 從Y跳至S 將Y清空 這時你看 S上有1 2 L上有3 4 好象是原來在L上的4只青蛙 分成了上下兩部分 上面的2只通過荷葉y轉移到了S上 這一過程是一分為二的過程 即將L上的一隊青蛙 分解為兩個隊 每隊各二只 且將上面的二只轉移到了S上 這時我們可以考慮形成兩個系統(tǒng) 一個是L Y R系統(tǒng) 一個是S Y R系統(tǒng) 前者二只青蛙號大 后者二只青蛙號小 先跳號大的 再跳號小的 從第五步到第九步可以看出的確是這么做的 2 Y R S L 3 1 L Y S 將L上的一半青蛙轉移到S上L Y R 將L上的青蛙轉移到R上S Y R 將S上的青蛙轉移到R上對于LYR系統(tǒng) 相當于Jump 0 1 對于SYR系統(tǒng) 相當于Jump 0 1 兩個系統(tǒng)之和為2 Jump 0 1 因此有 Jump 1 1 2 Jump 0 1 2 2 4 現(xiàn)在再看S 2 y 1Jump 2 1 我們將河中的兩個石柱稱作S1和S2 荷葉叫y 考慮先將L上的青蛙的一半借助于S2和y轉移到S1上 當然是一半小號的青蛙在S1上 大的留在L上 S 2 y 1 S S1 S2S1 S2 S 1LYRS2S1231 L S2 Y S1以S1為跳轉的目的地 從L經S2Y到S1 相當于JAMP 1 1 4 即S1上有4只青蛙 L上還保留4只 12Y345162L7S213S1824 L R Y S2 S1 YRLS2S1LS2YRS1S2YR 這樣LS1S2yR系統(tǒng)分解為 LS2yR系統(tǒng) S1S2yR系統(tǒng) 2 LS2yR系統(tǒng) 2 Jump 1 1 用歸納法Jump S y 2 Jump S 1 y 5 將上述分析出來的規(guī)律寫成遞歸形式的與或結點圖為 舉例 S 3 y 4 算Jump 3 4 程序 6 5 cpp 作者 wuwh 編制時間 2002年10月20日 主要功能 青蛙過河 include 預編譯命令intJump int int 聲明有被調用函數(shù)voidmain 主函數(shù) 主程序開始ints 0 y 0 sum 0 整型變量 s為河中石柱數(shù) y為荷葉數(shù)cout s 輸入正整數(shù)scout y 輸入正整數(shù)ysum Jump s y Jump s y 為被調用函數(shù)cout Jump s 輸出結果 y sum endl 主程序結束 程序 6 5 cpp 作者 wuwh 編制時間 2002年10月20日 主要功能 青蛙過河 遞歸 include 預編譯命令intJump int int 聲明有被調用函數(shù)intmain 主函數(shù) ints 0 y 0 sum 0 cout s 輸入正整數(shù)scout y 輸入正整數(shù)ysum Jump s y Jump s y 為被調用函數(shù)cout Jump s 輸出結果 y sum endl 以下函數(shù)是被主程序調用的函數(shù)intJump intr intz 自定義函數(shù) r z為形參 自定義函數(shù)體開始intk 0 整型變量if r 0 如果r為0 則為直接可解結點 k z 1 直接可解結點 k值為z 1else 如果r不為0 則要調用Jump r 1 z k 2 Jump r 1 z return k 將k的值返回給Jump s y 自定義函數(shù)體結束 遞歸算法舉例 快速排序 快速排序的思路 1 將待排序的數(shù)據放入數(shù)組a中 下標從z到y(tǒng) 2 取a z 放變量k中 通過分區(qū)處理 為k選擇應該排定的位置 這時要將比k大的數(shù)放右邊 比k小的數(shù)放左邊 當k到達最終位置后 由k劃分了左右兩個集合 然后再用同樣的思路處理左集合與右集合 3 令sort z y 為將數(shù)組元素從下標為z到下標為y的y z 1個元素從小到大排序 zm 1mm 1y m 1m 1 zmy zy k 我們畫出與或圖來闡述快速排序的思路 Asort z y z yz yBC不做事DEF分區(qū)處理sort z m 1 sort m 1 y 分區(qū)處理 1 讓k a z 2 將k放在a m 3 使a z a z 1 a m 1 y 則什么也不做 這是直接可解結點 C結點是在z y情況下A結點的解 C是一個與結點 要對C求解需分解為三步 依次為 1 先解D結點 D結點是一個直接可解結點 功能是進行所謂的分區(qū)處理 規(guī)定這一步要做的事情是 1 將a z 中的元素放到它應該在的位置上 比如m位置 這時a m a z 2 讓下標從z到m 1的數(shù)組元素小于等a m 3 讓下標從m 1到y(tǒng)的數(shù)組元素大于a m 比如a數(shù)組中a z 5 經分組處理后 5送至a 4 5到位后 其左邊a 0 a 3 的值都小于5 其右邊a 5 a 6 大于5 見下圖 a z y a m 下標 下標 z m 1 y m 1 2 再解E結點 這時要處理的是a 0 a 3 3 再解F結點 處理a 5 a 6 下面按照這種思路構思一個快速排序的程序框圖 voidsort intarray intzz intyy intz y i k 下面舉例說明排序過程 圖1a數(shù)組中有7個元素待排序1讓k a z a 0 5 z y 圖1 k 2進入直到型循環(huán)執(zhí)行 1 a y a 6 4不滿足當循環(huán)條件 y不動 執(zhí)行 2 z y 做兩件事 a z a y 即a 0 a 6 4 z z 1 0 1 1 見圖2 z y 圖2 k 執(zhí)行 3 圖2中的a 1 k 滿足當循環(huán)條件 z z 1 2 z增1后的情況如圖3 圖3的情況不再滿足當循環(huán)條件 z y 圖3 k 執(zhí)行 4 a y a z 即a 6 a 2 6 見圖4 這時z y還得執(zhí)行直到型循環(huán)的循環(huán)體 z y 圖4 k 執(zhí)行 1 a y a 6 6 6 k滿足當循環(huán)的條件 y y 1 6 1 5見圖5 之后退出當循環(huán) 因為a y 3 k z y 圖5 k 執(zhí)行 2 a z a y 并讓z z 1 3 見圖6 z y 圖6 k 執(zhí)行 3 由于a 3 1k 退出循環(huán) 見圖7 z y 圖7 k 執(zhí)行 4 a z a y a 5 7 見圖8這時仍然z y 應繼續(xù)執(zhí)行直到型循環(huán)的循環(huán)體 z y 圖8 k 執(zhí)行 1 a y 7 k 讓y y 1 4 見圖9 z y 圖9 k 之后 z y 退出直到型循環(huán) 做a z k z 4 a 4 5 這是5的最終位置 5將整個數(shù)據分成左右兩個集合 見圖10 z y 圖10 左 右 k 用上述思路去排左邊的部分從z 0到y(tǒng) 3 見圖11 讓k a z a 0 4 然后進到直到型循環(huán) 執(zhí)行 1 a y 1 k 不滿足當循環(huán)的條件 y不動 執(zhí)行 2 a z a y z z 1 1 見圖12 z y 圖12 z y 圖11 k 執(zhí)行 3 a z k z z 1 2 a 2 k z z 1 3 這時z y 不會執(zhí)行 4 同時退出直到型循環(huán) 見圖13 然后做a z k 即a 3 4 見圖14 左邊也排好了 圖14 z y 圖13 z y k k 4 用上述思路去排右邊的部分 見圖15 讓k a z a 5 7 進入直到型循環(huán) 執(zhí)行 1 a y 6 k y不動執(zhí)行 2 a z a y 6 z z 1 5 1 6 見圖16 圖16 z y 圖15 z y k 這時z y 不再執(zhí)行 3 4 退出直到型循環(huán)后 做a z k 見圖17 圖17 z y k 在有了遞歸調用函數(shù)之后 主程序很容易寫 主程序中應包含1 定義整型變量 數(shù)組a 10 i 2 用循環(huán)結構輸入待排序的數(shù) 將其放入a數(shù)組 3 調用sort函數(shù) 使用三個實際參數(shù)a 將數(shù)組a當實參 0 數(shù)組下標下界 9 數(shù)組下標上界 4 輸出排序結果下面給出參考程序 分兩頁 程序 6 6 cpp 作者 wuwh 編制時間 2002年10月28日 主要功能 快速排序 include 預編譯命令voidsort intarray intzz intyy 被調用函數(shù) 數(shù)組array zz yy為形參 函數(shù)體開始intz y i k 定義變量if zz k y 2 1 右邊的元素 k 讓y往中間移if zk 讓array z array y array z 送給array y while z y 第2件事 結束 array z k 第3件事 k已排到位for i zz i a i sort a 0 9 調用sort函數(shù) 實參為數(shù)組a和0 9cout 排序結果為 提示信息for i 0 i 10 i cout a i 輸出排序結果cout endl 主函數(shù)結束 程序 6 6 cpp 作者 wuwh 編制時間 2002年10月28日 主要功能 快速排序 include 預編譯命令voidsort intarray intzz intyy 被調用函數(shù) 數(shù)組array zz yy為形參 函數(shù)體開始intz y i k 定義變量if zz yy 如果zz yy 則做下列7件事 7件事開始z zz y yy k array z 第1件事 do 第2件事 開始 while z k y 2 1 右邊的元素 k 讓y往中間移if zk array y array z while z y 第2件事 結束 kzywhile z k y 2 1 右邊的元素 k 讓y往中間移 kzyif z y array z array y z z 1 kzywhile z y zy5261734zy4261734kzy54261736zy4231736zy4231776zy4231576 array z k 第3件事 k已排到位for i zz i yy i 第4件事 輸出 cout a i array i cout endl 第5件事 換行sort array zz z 1 第6件事 排左邊部分sort array z 1 yy 第7件事 排右邊部分 7件事結束 函數(shù)體結束 voidmain 主函數(shù)開始 inta 10 i 整型變量cout a i sort a 0 9 調用sort函數(shù) 實參為數(shù)組a和0 9cout 排序結果為 提示信息for i 0 i 10 i cout a i 輸出排序結果cout endl 主函數(shù)結束 研究sort a 0 9 主函數(shù)調用sort a 0 9 實在參數(shù)子函數(shù)中sort array zz yy 形式參數(shù)a09Arrayzzyy 研究sort a 0 9 a35614798020123456789array35614798020123456789 小結 1 數(shù)組也可作參數(shù) 數(shù)組為實參 數(shù)組為形參 2 只在被調用時系統(tǒng)才為array zz yy分配內存單元 調用后釋放掉內存單元 3 zz和yy為數(shù)組的下標 是參加排序的數(shù)組元素的左右邊界 遞歸算法舉例 分書問題 教學目標 鞏固用遞歸思想編寫程序教學內容 分書問題題目 有編號分別為0 1 2 3 4的五本書 準備分給A B C D E五個人 每個人閱讀興趣用一個二維數(shù)組加以描述 希望你寫一個程序 輸出所有分書方案 讓人人皆大歡喜 假定5個人對5本書的閱讀興趣如下表 01234ABCDE 人 書 1 定義一個整型的二維數(shù)組 將表中的閱讀喜好用初始化方法賦給這個二維數(shù)組 可定義intlike 5 5 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 2 定義一個整型一維數(shù)組book 5 用來記錄書是否已被選用 用下標作為五本書的標號 被選過元素值為1 未被選過元素值為0 初始化皆置0 intbook 5 0 0 0 0 0 解題思路 3 畫出思路圖定義Try i 試著給第i人分書 i 0 1 4 說明 1 試著給第i個人分書 先試分0號書 再分1號書 分2號書 因此有一個與結點 讓j表示書j 0 1 2 3 4 2 LP為循環(huán)結構的循環(huán)體 3 條件C是由兩部分 與 起來的 第i個人喜歡j書 且j書尚未被分走 滿足這個條件是第i人能夠得到j書的條件 4 如果不滿足C條件 則什么也不做 這是直接可解結點 5 滿足C條件 做三件事 sh1第一件事 將j書分給i 用一個數(shù)組take i j 記住書j給了i 同時記錄j書已被選用 book j 1 sh2第二件事 查看i是否為4 如果不為4 表示尚未將所有5個人所要的書分完 這時應遞歸再試下一人 即Try i 1 如果i 4 則應先使方案數(shù)n n 1 然后輸出第n個方案下的每個人所得之書 Sh3第三件事 回溯 讓第i人退回j書 恢復j書尚未被選的標志 即book j 0 這是在已輸出第n個方案之后 去尋找下一個分書方案所必需的 6 在有了上述的與或圖之后 我們很容易寫出一個程序框圖 先看被調用函數(shù)Try i 的框圖 程序 6 7 cpp 作者 wuwh 編制時間 2002年10月28日 主要功能 分書問題 include 預編譯命令inttake 5 n 整型變量intlike 5 5 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 整型變量 定義數(shù)組 初始化intbook 5 0 0 0 0 0 整型變量 定義數(shù)組 初始化 下面討論主程序應該做的事情1 將分書方案號預置02 從第0號人 A 開始試分書 調用Try 0 voidTry inti 函數(shù)體開始intj k 定義變量for j 0 j0 記錄j書待分 voidTry inti intj k for j 0 j0 記錄j書待分 includeinttake 5 n intlike 5 5 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 intbook 5 0 0 0 0 0 voidTry inti 函數(shù)體開始intj k 定義變量for j 0 j0 book j 0 如果滿足分書條件作下列事 take i j book j 1 把j號書給i 記錄j書已分if i 4 輸出分書方案 n 讓方案數(shù)加1cout 第 n 個方案 n 輸出分書方案號for k 0 k 4 k cout take k 號書分給 char k 65 endl cout endl 換行 elseTry i 1 如果i 4 繼續(xù)給下一人分書 遞歸調用Try i 1 book j 0 讓i把書退還 回溯 voidmain 主函數(shù) 主函數(shù)開始n 0 分書方案號預置0Try 0 調用Try函數(shù) 實參為0 主函數(shù)結束 結束 RelatedDocuments CompetitorsYoumaywanttoallocateoneslidepercompetitorStrengthsYourstrengthsrelativetocompetitorsWeaknessesYourweaknessesrelativetocompetitor ChartDocuments example1 2ndQtr 3rdQtr 4thQtr 92 70 50 example2 example3 example4 1stQtr ChartDocuments example1 2ndQtr 3rdQtr 4thQtr 100 75 50 example2 example3 example4 1stQtr 25 text1 RelatedDocuments text3 text2 text1 text2 text3 RelatedDocuments text1 text2 text3 text4 RelatedDocuments text4 text5 text6 RelatedDocuments text3 text2 text1