C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程：第14章 函數(shù)進(jìn)階

1、第第14章章 函數(shù)進(jìn)階函數(shù)進(jìn)階C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程程序設(shè)計(jì)快速進(jìn)階大學(xué)教程C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-212第第14章章 函數(shù)進(jìn)階函數(shù)進(jìn)階本章要點(diǎn)本章要點(diǎn) 分解與抽象分解與抽象 遞歸遞歸C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-21314.1 分解與抽象分解與抽象知識點(diǎn)知識點(diǎn) 功能分解與抽象功能分解與抽象 再認(rèn)識遞歸再認(rèn)識遞歸C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-21414.1 分解與抽象分解與抽象 給定日期由年、月、日（三個(gè)整數(shù)，年的取值給定日期由年、月、日（三個(gè)整數(shù)，年的取值在在19702050之間）組成，完成以下功能：之間）組成，完成以下功能：（1）判斷給定日期的合法性

2、；）判斷給定日期的合法性；（2）計(jì)算兩個(gè)日期相差的天數(shù)；）計(jì)算兩個(gè)日期相差的天數(shù)；（3）計(jì)算一個(gè)日期加上一個(gè)整數(shù)后對應(yīng)的日期；）計(jì)算一個(gè)日期加上一個(gè)整數(shù)后對應(yīng)的日期；（4）計(jì)算一個(gè)日期減去一個(gè)整數(shù)后對應(yīng)的日期；）計(jì)算一個(gè)日期減去一個(gè)整數(shù)后對應(yīng)的日期；（5）計(jì)算一個(gè)日期是星期幾。）計(jì)算一個(gè)日期是星期幾。問題問題1: 日期運(yùn)算日期運(yùn)算 C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-21514.1 分解與抽象分解與抽象問題問題1: 日期運(yùn)算日期運(yùn)算 C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-21614.1 分解與抽象分解與抽象日期合法性日期合法性C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-21714.1 分解與

3、抽象分解與抽象日期合法性日期合法性閏年判斷上面的盒圖中未給出，閏年判斷上面的盒圖中未給出，因?yàn)楣δ茌^為獨(dú)立，可單獨(dú)做一個(gè)函數(shù)，因?yàn)楣δ茌^為獨(dú)立，可單獨(dú)做一個(gè)函數(shù)，并且在后面的模塊中還會使用并且在后面的模塊中還會使用C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-21814.1 分解與抽象分解與抽象計(jì)算兩個(gè)日期相差的天數(shù)計(jì)算兩個(gè)日期相差的天數(shù) 計(jì)算日期計(jì)算日期A（yearA、monthA、dayA）和日期）和日期B（yearB、monthB、dayB）相差天數(shù)，假定）相差天數(shù)，假定A小于小于B并且并且A和和B不在同一年份，把天數(shù)分成不在同一年份，把天數(shù)分成3段：段： 1 A日期到日期到A所在年份所在年份

4、12月月31日的天數(shù)；日的天數(shù)； 2 A之后到之后到B之前的整年的天數(shù)（之前的整年的天數(shù)（A、B相鄰年份相鄰年份這部分沒有）；這部分沒有）； 3 B日期所在年份日期所在年份1月月1日到日到B日期的天數(shù)。日期的天數(shù)。C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-21914.1 分解與抽象分解與抽象計(jì)算一個(gè)日期加上一個(gè)整數(shù)天數(shù)后對應(yīng)的日期計(jì)算一個(gè)日期加上一個(gè)整數(shù)天數(shù)后對應(yīng)的日期 計(jì)算日期計(jì)算日期A（yearA、monthA、dayA）加上一個(gè)整）加上一個(gè)整數(shù)天數(shù)數(shù)天數(shù)days對應(yīng)的日期。對應(yīng)的日期。 若若days小于小于A日期到日期到A所在年份所在年份12月月31日的天數(shù)則日的天數(shù)則 對應(yīng)結(jié)果日期在本年

5、中計(jì)算，對應(yīng)結(jié)果日期在本年中計(jì)算，yearA不變。不變。 否則否則 若天數(shù)剩下的部分夠整年（閏年問題）則循環(huán)若天數(shù)剩下的部分夠整年（閏年問題）則循環(huán) yearA加加1；days去掉一年天數(shù)；去掉一年天數(shù)； 對對days剩下的不夠一年的天數(shù)，在該年計(jì)算日期。剩下的不夠一年的天數(shù)，在該年計(jì)算日期。C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-211014.1 分解與抽象分解與抽象計(jì)算一個(gè)日期減去一個(gè)整數(shù)天數(shù)后對應(yīng)的日期計(jì)算一個(gè)日期減去一個(gè)整數(shù)天數(shù)后對應(yīng)的日期 計(jì)算日期計(jì)算日期A（yearA、monthA、dayA）減去一個(gè)）減去一個(gè)整數(shù)天數(shù)整數(shù)天數(shù)days對應(yīng)的日期。對應(yīng)的日期。若若days小于小于A所

6、在年份所在年份1月月1日到日到A日期的天數(shù)，則日期的天數(shù)，則 對應(yīng)結(jié)果日期在本年中計(jì)算，對應(yīng)結(jié)果日期在本年中計(jì)算，yearA不變。不變。否則否則 若若days剩下的部分夠整年（閏年問題），則循環(huán)剩下的部分夠整年（閏年問題），則循環(huán) yearA減減1；days去掉一年天數(shù)；去掉一年天數(shù)； 對對days剩下的不夠一年的天數(shù)，在計(jì)算對應(yīng)日期。剩下的不夠一年的天數(shù)，在計(jì)算對應(yīng)日期。C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-211114.1 分解與抽象分解與抽象計(jì)算一個(gè)日期是星期幾計(jì)算一個(gè)日期是星期幾 計(jì)算日期計(jì)算日期A（yearA、monthA、dayA）為星期）為星期幾，需要找到一個(gè)參照的日期幾，需要

7、找到一個(gè)參照的日期B，只需要知道日期，只需要知道日期B為星期幾，然后計(jì)算出為星期幾，然后計(jì)算出A和和B相差的天數(shù)，就很容相差的天數(shù)，就很容易計(jì)算出易計(jì)算出A為星期幾。此處又需要用到為星期幾。此處又需要用到計(jì)算兩個(gè)日計(jì)算兩個(gè)日期的差期的差。C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-211214.1 分解與抽象分解與抽象綜合分析綜合分析 幾種功能都在計(jì)算一段日期天數(shù)，這種一段日期幾種功能都在計(jì)算一段日期天數(shù)，這種一段日期天數(shù)分為天數(shù)分為3種：種：年內(nèi)年內(nèi)1月月1日到某日期的天數(shù)日到某日期的天數(shù)(年內(nèi)的前半段年內(nèi)的前半段)；年內(nèi)某日期到年內(nèi)某日期到12月月31日的天數(shù)日的天數(shù)(年內(nèi)的后半段年內(nèi)的后半段

8、)；整年的天數(shù)。整年的天數(shù)。只有整年天數(shù)容易計(jì)算，其他只有整年天數(shù)容易計(jì)算，其他兩種較為復(fù)雜，能不能回避呢？兩種較為復(fù)雜，能不能回避呢？C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-211314.1 分解與抽象分解與抽象綜合分析綜合分析 對于日期對于日期A和和B的差的差:1.可以選定日期可以選定日期C（1970年年1月月1日）日）;2.計(jì)算計(jì)算C到到A的天數(shù)的天數(shù)CA;3.計(jì)算計(jì)算C到到B的天數(shù)的天數(shù)CB;4.CB減減CA為為A到到B的天數(shù)。的天數(shù)。而對而對C到到A，只需要計(jì)算整年（因?yàn)?，只需要?jì)算整年（因?yàn)镃為為1月月1日）日）加上加上A的年內(nèi)前半段，的年內(nèi)前半段，C到到B同理。這樣就回避掉同理。

9、這樣就回避掉了計(jì)算年內(nèi)后半段的問題。了計(jì)算年內(nèi)后半段的問題。C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-211414.1 分解與抽象分解與抽象開始抽象開始抽象 選定參照日期選定參照日期C（1970年年1月月1日），日），C到到A的天的天數(shù)用函數(shù)數(shù)用函數(shù)dateToDays(A)來描述。來描述。 為了解決日期加減天數(shù)問題，可以把日期為了解決日期加減天數(shù)問題，可以把日期A通過通過dateToDays函數(shù)轉(zhuǎn)化為天數(shù)，再加減一個(gè)整數(shù)，函數(shù)轉(zhuǎn)化為天數(shù)，再加減一個(gè)整數(shù)，變成一個(gè)新的天數(shù)，只需要再定義一個(gè)函數(shù)變成一個(gè)新的天數(shù)，只需要再定義一個(gè)函數(shù)daysToDate(days)把天數(shù)轉(zhuǎn)換為從把天數(shù)轉(zhuǎn)換為從197

10、0年年1月月1日日經(jīng)過該天數(shù)對應(yīng)的日期即可。經(jīng)過該天數(shù)對應(yīng)的日期即可。daysToDate函數(shù)也函數(shù)也只需要處理若干整年（因?yàn)閺闹恍枰幚砣舾烧辏ㄒ驗(yàn)閺?970年年1月月1日起）日起）和結(jié)果年份內(nèi)的前半段。和結(jié)果年份內(nèi)的前半段。C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-211514.1 分解與抽象分解與抽象抽象結(jié)果抽象結(jié)果本例共抽象出本例共抽象出3個(gè)公用的函數(shù)：個(gè)公用的函數(shù)： leap：判斷閏年函數(shù)。：判斷閏年函數(shù)。 dateToDays：把一個(gè)日期轉(zhuǎn)換成從：把一個(gè)日期轉(zhuǎn)換成從1970年年1月月1日到該日期的天數(shù)。日到該日期的天數(shù)。 daysToDate：把天數(shù)轉(zhuǎn)換成從：把天數(shù)轉(zhuǎn)換成從1970

11、年年1月月1日經(jīng)日經(jīng)過該天數(shù)所到的日期。過該天數(shù)所到的日期。C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-211614.1 分解與抽象分解與抽象新的解決方案新的解決方案模塊模塊2. 日期日期A（yearA、monthA、dayA）和日期）和日期B（yearB、monthB、dayB）相差天數(shù)：）相差天數(shù)：dateToDays（B）- dateToDays（A）模塊模塊3. 日期日期A（yearA、monthA、dayA）加上一個(gè)整）加上一個(gè)整數(shù)天數(shù)數(shù)天數(shù)days對應(yīng)的日期：對應(yīng)的日期：daysToDate (dateToDays（A）+ days)模塊模塊4. 日期日期A（yearA、monthA、

12、dayA）減去一個(gè)整）減去一個(gè)整數(shù)天數(shù)數(shù)天數(shù)days對應(yīng)的日期：對應(yīng)的日期：daysToDate (dateToDays（A）- days)模塊模塊5. 日期日期A（yearA、monthA、dayA）為星期幾：）為星期幾：(dateToDays（A）+Offset-2)%7+1Offset是是1970年年1月月1日星期值，值為日星期值，值為4。C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-211714.1 分解與抽象分解與抽象抽象實(shí)現(xiàn)抽象實(shí)現(xiàn)dateToDaysC程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-211814.1 分解與抽象分解與抽象抽象實(shí)現(xiàn)抽象實(shí)現(xiàn)daysToDate C程序設(shè)計(jì)快速進(jìn)階大學(xué)

13、教程2022-2-211914.2 遞歸遞歸遞歸算法設(shè)計(jì)的基本思想是：遞歸算法設(shè)計(jì)的基本思想是： 對于一個(gè)復(fù)雜的問題，把原問題分解為若干對于一個(gè)復(fù)雜的問題，把原問題分解為若干個(gè)相對簡單的同類子問題，繼續(xù)下去直到子問題個(gè)相對簡單的同類子問題，繼續(xù)下去直到子問題簡單到能夠直接求解，也就是說到了遞歸出口，簡單到能夠直接求解，也就是說到了遞歸出口，這樣原問題就通過遞歸解決了。這樣原問題就通過遞歸解決了。 問題規(guī)模變?。ㄟf歸過程）問題規(guī)模變?。ㄟf歸過程）簡單到問題有解（遞歸出口）簡單到問題有解（遞歸出口）遞歸兩要素：遞歸兩要素：C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-212014.2 遞歸遞歸漢諾塔問題

14、描述：漢諾塔問題描述： 有三根桿，分別稱為有三根桿，分別稱為A、B、C。A桿上套有桿上套有64個(gè)大小不等的圓盤，大的在下，小的在上。要把個(gè)大小不等的圓盤，大的在下，小的在上。要把這這64個(gè)圓盤從個(gè)圓盤從A桿移動(dòng)桿移動(dòng)C桿上，每次只能移動(dòng)一桿上，每次只能移動(dòng)一個(gè)圓盤，移動(dòng)可以借助個(gè)圓盤，移動(dòng)可以借助B桿進(jìn)行。但在任何時(shí)候桿進(jìn)行。但在任何時(shí)候，任何桿上的圓盤都必須保持大盤在下，小盤在，任何桿上的圓盤都必須保持大盤在下，小盤在上。求移動(dòng)的步驟。上。求移動(dòng)的步驟。 C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程2022-2-212114.2 遞歸遞歸算法分析算法分析 :【簡化條件【簡化條件】當(dāng)當(dāng)n大于等于大于等于2時(shí)，時(shí)

15、， 移動(dòng)的過程可分解為三個(gè)步驟：移動(dòng)的過程可分解為三個(gè)步驟：1. 把把A上的上的n-1個(gè)圓盤移到個(gè)圓盤移到B上；上；2. 把把A上的一個(gè)圓盤移到上的一個(gè)圓盤移到C上；上；3. 把把B上的上的n-1個(gè)圓盤移到個(gè)圓盤移到C上；上； 其中第其中第1步和第步和第3步和把步和把n個(gè)圓盤從個(gè)圓盤從A移動(dòng)到移動(dòng)到C是類同是類同的。的?！具f歸出口【遞歸出口】當(dāng)當(dāng)n等于等于1時(shí)，直接把一個(gè)圓盤從時(shí)，直接把一個(gè)圓盤從A移到移到C上。上。 C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程22例例14.2 漢諾塔漢諾塔#includeint main() int h; void hannoi(int n,char x,char y,cha

16、r z); printf(input number:n); scanf(%d,&h); printf(the step to moving %2d diskes:n,h); /* 把把n個(gè)圓盤從個(gè)圓盤從A桿借用桿借用B桿移動(dòng)到桿移動(dòng)到C桿桿 */ hannoi(h,A,B,C); return 0;C程序設(shè)計(jì)快速進(jìn)階大學(xué)教程23void hannoi(int n,char x,char y,char z) if(n=1) /* 從從x桿到桿到z桿移動(dòng)一個(gè)圓盤桿移動(dòng)一個(gè)圓盤 */ printf(%c-%cn,x,z); else /* 首先把首先把n-1個(gè)圓盤從個(gè)圓盤從x桿借用桿借用z桿移動(dòng)到桿移動(dòng)到y(tǒng)桿桿 */ hannoi(n-1,x,z,y); /* 從從x桿到桿到z桿移動(dòng)一個(gè)圓盤桿移動(dòng)一個(gè)圓盤 */ printf(%c-%cn,x,z); /* 再把再把n-1個(gè)圓盤從個(gè)圓