《算法語言與數(shù)據(jù)結(jié)構(gòu)(第5章).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法語言與數(shù)據(jù)結(jié)構(gòu)(第5章).ppt（174頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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