《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)一》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》實(shí)驗(yàn)一（17頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 學(xué) 號(hào) 1421050102 《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告一 學(xué) 生 姓 名 Cherish 專 業(yè) 、 班 級(jí) 地 理 指 導(dǎo) 教 師 唐 國(guó) 峰 成 績(jī) 計(jì)算機(jī)與信息工程學(xué)院軟件工程系 2017 年 3 月 14 日

2、實(shí)驗(yàn)一：遞歸策略運(yùn)用練習(xí) 一、實(shí)驗(yàn)?zāi)康? 本次 是 算法的算法 及 用 ，  旨在加深學(xué)生 算法原理的理解，  提高 學(xué)生運(yùn)用 算法解決 的能力。 二、實(shí)驗(yàn)步驟與要求 1． 前復(fù) 程所學(xué)知 以及 和理解指定的 外 材料； 2．學(xué)生獨(dú)自完成 指定內(nèi)容； 3． 束后，用 一的 告模板 寫(xiě) 告 。 4． 提交 明： （ 1） 子版提交 明： a 需要提交 Winrar 包，文件名 “ 《算法 與分析》 一 _學(xué)號(hào)

3、_姓名”， 如“《算法 與分析》 一 _09290101_ 三”。 b 包內(nèi) 一個(gè)“ 《算法 與分析》 一 _學(xué)號(hào) _姓名”命名的 文件 ， 其下 兩個(gè)文件 ，一個(gè)文件 命名 “源程序” ，另一個(gè)文件 命名 “ 告 子版” 。其下分 放置 成果物。 （ 2）打印版提交 明： a 不可隨意更改模板 式。 b 字體：中文 宋體，大小 10 號(hào)字，英文 Time New Roman ，大小 10 號(hào) 字。 c 行 距： 倍行距。 （ 3）提交截止 ： 2017 年 3

4、月 28 日 16:00。 三、 實(shí)驗(yàn)項(xiàng)目 1．運(yùn)用 策略 算法 下述 目的求解 程。 目列表如下： 【必做 】 （ 1）運(yùn) 會(huì)開(kāi)了 N 天，一共 出金牌 M 枚。第一天 金牌 1 枚加剩下的七分之一枚，第 二天 金牌 2 枚加剩下的七分之一枚， 第 3 天 金牌 3 枚加剩下的七分之一枚， 以后每天都照此 理。到了第 N 天 好 有金牌 N 枚，到此金牌全部 完。 程求 N 和 M 。 （ 2）國(guó)王分 。某國(guó)王 前 兒子 分 。他把 分 若干份，然后 第一個(gè)兒 子一份，再加上剩余 的 1/10 ；

5、第二個(gè)兒子兩份，再加上剩余 的 1/10 ；??； 第 個(gè)兒子 i 份，再加上剩余 的 1/10 。每個(gè)兒子都竊竊自喜。以 得到了父王的偏 ，孰不知國(guó)  i 王是“一碗水端平”的。 用程序回答，老國(guó)王共有幾個(gè)兒子？ 共分成了多少份？ （ 3）出售金 ：第一次 出全部金 的一半加二分之一條金 ；第二次 出乘余金 的三分之一加三分之一條金 ； 第三次 出剩余金 的四分之一加四分之一條金 ； 第四次 出剩余金 的五分之一加五分之一條金 ； 在 剩下 11 條金 ，在出售金 不能把金

6、切開(kāi)或者有任何破 的。 缸里原有多少條金 ？ （ 4）某路公共汽 ， 共有八站，從一號(hào)站 上已有 n 位乘客，到了第二站先下一 半乘客，再上來(lái)了六位乘客；到了第三站也先下一半乘客， 再上來(lái)了五位乘客， 以后每到一站都 先下 上已有的一半乘客，再上來(lái)了乘客比前一站少一個(gè)??，到了 點(diǎn)站 上 有乘客六人， 上的乘客有多少？ （ 5）猴子吃桃。有一群猴子摘來(lái)了一批桃子，猴王 定每天只準(zhǔn)吃一半加一只（即第二天吃剩下的一半加一只，以此 推） ，第九天正好吃完， 猴子 摘來(lái)了多少桃子？ （ 6）小 。第一天 了全 的一半加二 ，第二天 了

7、剩下的一半加二 ，以后天天 如此??，第六天 完了最后的三 ， 全 有多少 ？ （ 7）日本著名數(shù)學(xué)游 家中村 作教授提出 一個(gè) ： 父 將 2520 個(gè)桔子分 六個(gè) 兒子。分完 后父 ： “老大將分 你的桔子的 1/8 老二；老二拿到后 同原先的桔子分 1/7 老三；老三拿到后 同原先的桔子分 1/6 老四；老四拿到后 同原先的桔子分 1/5 老五； 老五拿到后 同原先的桔子分 1/4 老六；老六拿到后 同原先的桔子分 1/3 老大”。 果大 家手中的桔子正好一 多。 六兄弟原來(lái)手中各有多少桔子？ （ 8）某種 染病第一天只有一

8、個(gè)患者，前 5 天 潛伏期，不 作也不會(huì) 染人，第 6 天開(kāi) 始 作，從 作到治愈需要 5 天 ，期 每天 染 3 個(gè)人，求第 N 天共有多少患者。 【 做 】（ 5 選 3） （ 1） 了保障社會(huì)秩序，保 人民群眾生命 安全，警察叔叔需要與罪犯斗智斗勇，因而需要 常性地 行體力 和智力 ！某批警察叔叔正在 行智力 ： 1 2 3 4 5 6 7 8 9 = 110; 看上 的算式， 了使等式成立，需要在數(shù)字 填入加號(hào)或者減號(hào) （可以不填， 但不能填 入其它符號(hào)） 。之 沒(méi)有填入符號(hào)的數(shù)字 合成一個(gè)數(shù)，例如： 12+34+56+7-8+9 就是一

9、種合格 的填法； 123+4+5+67-89 是另一個(gè)可能的答案。 你利用 算機(jī)的 ，幫助警察叔叔快速找到所有答案。 每個(gè)答案占一行。形如： 12+34+56+7-8+9 123+4+5+67-89 （ 2） 將一個(gè)整數(shù) 出。形如654321， 出 1,2,3,4,5,6 （ 3）用 分解 因數(shù)。形如：12=2*2*3 （ 4）50 個(gè) 梯，你一次可以上一 或兩 ，走上去，共有多少種走法？ （ 5） 號(hào) 的字符 合。  目：在 或者手機(jī)上，  一個(gè)數(shù)字如  2 著字母 

10、 ABC ， 7 著 PQRS。那么數(shù)字串 27 所 的字符的可能 合就有 3*4=12 種（如 AP， BR 在 入一個(gè) 3 到 11 位 的 號(hào) ， 打印出 個(gè) 號(hào) 所 的字符的所有可能 合和  等）。 合數(shù)。 四、實(shí)驗(yàn)過(guò)程 以下程序都是在  VS2010 下編譯與  VC6.0  代碼稍有不同。 （1）運(yùn) 會(huì)開(kāi)了 N 天，一共 出金牌 M 枚。第一天 金牌 1 枚加剩下的七分之一枚，第二天 金牌 2 枚加剩下的七分之一枚， 第 3 天 金牌 3 枚加剩下的七分之一枚，

11、以后每天都照此 理。 到了第 N 天 好 有金牌 N 枚，到此金牌全部 完。 程求 N 和 M 。 目分析 依據(jù) 目可寫(xiě)出 式：  (F(n)-n)*6/7=F(n+1);F(n)  是第  n天 牌 數(shù)即第  n-1天剩余的包括第  n天 的和剩下的。每天 放的金牌數(shù)：當(dāng)天天數(shù) +（前一天剩余金牌 -當(dāng)天天數(shù)） /7，所以判 的條件是（前一天剩余金牌 -當(dāng)天天數(shù)） 為 7的整數(shù)倍， 第 i+1 天的金牌數(shù)即 i天剩下的必 是 6的整數(shù) 倍。 算法構(gòu)造 遞歸函數(shù)：

12、 nSum(i+1,n)=(nSum(i,n)-i)*6/7.  篩選條件：  (nSum(i,n)-i)%7==0&&(nSum(i,n)%6==0) 算法實(shí)現(xiàn) #include #define devide 7; //  不知什么原因這樣定義下面不能用？  vc6.0  未安上，不知與  vs2010 有和區(qū)別？ int nSum(int i,int n)  //nSum()  函數(shù)定義第  i 天

13、的金牌數(shù)即  i-1  天剩下  . { int result=0; if(i==n) { return n; } else { result=((nSum(i+1,n)*7)/6+i); // 遞歸函數(shù)： nSum(i+1,n)=(nSum(i,n)-i)*6/7. } return result; } void main() { for(int n=2;n<=10;n++) // 遞增比賽天數(shù)逐個(gè)驗(yàn)證 { int skip=0; for(int i=1;

14、i<=n;i++) // 依次篩選從 i=1 到 n符合條件的 n值 { 剩余金牌  if((nSum(i,n)-i)%7==0&&(nSum(i,n)%6==0)) // 每天發(fā)放的金牌數(shù)：當(dāng)天天數(shù) - 當(dāng)天天數(shù)） /7 ，即（前一天剩余金牌 - 當(dāng)天天數(shù)）為 7的整數(shù)倍  +（前一天 { int skip=1; // 遞歸函數(shù)： nSum(i+1,n)=(nSum(i,n)-i)*6/7 即 nSum(i,n)=nSum(i+1,n)*7/6+i ，第 i+1 天的金牌數(shù)即 i 天剩下的必須是 6的整數(shù)倍

15、 printf( " 共有金牌 %d枚, 共進(jìn)行 %d天 \n" ,nSum(1,n),n); // 金牌總數(shù)即第一天金牌數(shù) for(int j=1;j<=n;j++) { printf( " 第 %d天, 發(fā)放 %d+%d枚, 還剩 %d枚\n",j,j,(nSum(j,n)-j)/7,(nSum(j,n)-j)*6/7); } break; } } if(skip==1 ) / / 用于跳出雙層循環(huán)結(jié)構(gòu)即 n遞增時(shí)第一個(gè)滿足時(shí)即可輸出，可運(yùn)行結(jié)果卻 不然 break;// 會(huì)有在 n上界內(nèi)更多的結(jié)構(gòu)輸出，只有第一個(gè) n值滿足不知

16、為何？？ } getchar(); } 運(yùn)行 果 經(jīng)驗(yàn)歸納 式容易想出，但是相 的 條件比 確定。 （2）國(guó)王分 。某國(guó)王 前 兒子 分 。他把 分 若干份，然后 第一個(gè)兒子一 份，再加上剩余 的 1/10 ； 第二個(gè)兒子兩份，再加上剩余 的 1/10 ；??； 第 i 個(gè)兒子 i 份，再加上剩余 的 1/10 。每個(gè)兒子都竊竊自喜。 以 得到了父王的偏 ， 孰不知國(guó)王是 “一 碗水端平”的。

17、 用程序回答，老國(guó)王共有幾個(gè)兒子？ 共分成了多少份？ 目分析 道國(guó)王分 的 和上 運(yùn) 會(huì) 金牌 似，不 在 條件 由 意略不同其 也是一 ，每個(gè)兒子分到的 相同即：  E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n)  ，且第  i 個(gè)兒子分  i 份及剩下的 1/10，即  E(i,n)-i  的差是  10 的整數(shù)倍。 算法構(gòu)造 函數(shù)： E(i+1,n)=(E(i,n)-n)*9/10;E(i,n) 條件： 每個(gè)兒子分到的 相同

18、即  當(dāng)要分 第 i 個(gè)兒子 有的份數(shù)； E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n) ；且第 i個(gè)兒子分  i 份及剩下的 1/10，即 E(i,n)-i  的差是  10的整數(shù)倍。 算法 #include #define devide 10; // 定 到后面不知怎么卻出 。 int E(int i,int n) // 函數(shù)： E(i+1,n)=(E(i,n)-n)*9/10;E(i,n)  當(dāng)要分 第

19、  i 個(gè)兒子 有的 份數(shù)； { int sum=0; if(i==n) return n; // 當(dāng)份到最后一個(gè)兒子 分完，往前求解； else sum=(E(i+1,n)*10)/9+i; // 依次 ； return sum; } void main() { for(int n=3;n<=10;n++) { int skip=0; for(int i=2;i

20、 E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n)  ； // 且第 i  個(gè)兒子分  i 份及剩下的  1/10  ，即 E(i,n)-i  的差是  10的整數(shù)倍； if((2*E(i,n)-E(i-1,n)-E(i+1,n)==0)&&(E(i,n)-i)%10==0)  // 用這兩個(gè)條件篩選； { int skip=1; printf( " 國(guó)王共有 %d個(gè)兒子 , 財(cái)產(chǎn)共分成  %d份。\n" ,n,E(1,n));  // 總份數(shù)即要分第

21、 一個(gè)兒子時(shí)有的分?jǐn)?shù) E(1,n) for(int j=1;j<=n;j++) printf ( " 第%d個(gè)兒子，分 %d+%d份，還剩 %d份。 \n",j,j,(E(j,n)-j)/10,(E(j,n)-j)*9/10); break; } } if(skip==1) break; } getchar(); } 運(yùn)行結(jié)果 經(jīng)驗(yàn)歸納 由于和第一題類似，此題較為順利，類似多練

22、習(xí)也會(huì)得心應(yīng)手。 （3）出售金魚(yú)問(wèn)題：第一次賣(mài)出全部金魚(yú)的一半加二分之一條金魚(yú)；第二次賣(mài)出乘余金魚(yú)的三 分之一加三分之一條金魚(yú)； 第三次賣(mài)出剩余金魚(yú)的四分之一加四分之一條金魚(yú)； 第四次賣(mài)出剩余金魚(yú)的五分之一加五分之一條金魚(yú)；現(xiàn)在還剩下 11 條金魚(yú)，在出售金魚(yú)時(shí)不能把金魚(yú)切開(kāi)或者有任何破損的。問(wèn)這魚(yú)缸里原有多少條金魚(yú)？ 題目分析 與上題類似出口為第四次買(mǎi)之前還有減去第四次買(mǎi)的還有  11 條。 算法 #include #define n 4; int Fish

23、(int i)// 構(gòu)造函數(shù) {  Fish(i) 第 i天 之前 剩多少，  Fish(1) 即 數(shù)； int result=0; if(i<4) result=(Fish(i+1)+(Fish(i+1)+1)/i); else return 14; // 第四天 之前的 - 第四天 的 =11，即 Fish(4)-(Fish(4)/5+1/5)=11,F(4)=11 return result; } void main() { prin

24、tf(" 共有金 %d 條。 \n",Fish(1)); for(int i=1;i<=4;i++) { printf(" 第 %d 天 ,賣(mài) %d 條， 剩 %d條。 \n",i,(Fish(i)+i)/(i+1),(Fish(i)-(Fish(i)+i)/(i+1))); } getchar(); } 運(yùn)行 果 ：以上 目 似可 比做出。 4.某路公共汽 ， 共有八站，從一號(hào)站 上已有 n 位乘客，到了第二站先下一半乘客，

25、 再上來(lái)了六位乘客； 到了第三站也先下一半乘客， 再上來(lái)了五位乘客， 以后每到一站都先下 上 已有的一半乘客， 再上來(lái)了乘客比前一站少一個(gè)??， 到了 點(diǎn)站 上 有乘客六人， 問(wèn)發(fā)車時(shí) 上的乘客有多少？ 目分析 此 與以上幾 似，略有不同而已。 算法構(gòu)造 由于從第一站出 沒(méi)有任何 ，故將第二站作 始 站； 函數(shù) Bus(i) 到達(dá)第 i站 未上下乘客 上人 數(shù)量； 算法實(shí)現(xiàn) #include i nt Bus(int i) // 由于從第一站出發(fā)沒(méi)有任何變動(dòng)，故將第二站作為始

26、發(fā)站； { // 函數(shù) Bus(i) 為到達(dá)第 i 站還未上下乘客時(shí)車上人員數(shù)量； int sum=0; if(i<6)// sum=2*(Bus(i+1)+i-7); // 有遞歸函數(shù)： Bus(i+1)=Bus(i)/2+7-i; else return 10; / / 由最后還剩 6人推的 Bus(6)=10; r eturn sum; } void main() { printf(" 發(fā)車時(shí)車上共有 %d 人。 \n",Bus(1)); for(int i=1;i<6;i++) printf(" 第 %d 站

27、 ,上來(lái) %d 人 ,下去 %d 人 ,剩下 %d 人 \n",i+1,(7-i),(Bus(i)/2),Bus(i+1)); getchar(); } 運(yùn)行結(jié)果 （ 5）猴子吃桃。有一群猴子摘來(lái)了一批桃子，猴王規(guī)定每天只準(zhǔn)吃一半加一只（即第二天吃剩下的一半加一只，以此類推） ，第九天正好吃完，問(wèn)猴子們摘來(lái)了多少桃子？ 題目分析 與上題類似 算法構(gòu)造 遞推函數(shù) Monkey(i) 表示第 i 天吃的和剩下的和；由 Monkey(i+1)=Monk

28、ey(i)/2-1 推得； 由 Monkey(9)=Monkey(9)/2+1, 得出口 Monkey(9)=2 。 算法實(shí)現(xiàn) #include int Monkey(int i)  // 遞推函數(shù)  Monkey(i)  表示第  i 天吃的和剩下的和； { int sum=0; if(i<9) sum=2*(Monkey(i+1)+1);  / / 由 Monkey(i+1)=Monkey(i)/2-1  推得； else

29、 return 2; //  由 Monkey(9)=Monkey(9)/2+1,  得出口  Monkey(9)=2; return sum; } void main() { printf(" 共有桃子 %d 個(gè)。 \n",Monkey(1)); for(int i=1;i<=9;i++) printf(" 第 %d 天，吃 %d+%d 個(gè)，剩下 %d個(gè)。 \n",i,Monkey(i)/2,1,Monkey(i)/2-1); getchar(); } 運(yùn)行 果

30、 （ 6）小 。第一天 了全 的一半加二 ，第二天 了剩下的一半加二 ，以后天天如此??，第六天 完了最后的三 ， 全 有多少 ？ 目分析 與以上 目 似。 算法構(gòu)造 構(gòu)造 推函數(shù)： Book(i); 表示第 i 天要 剩的 數(shù)；由 Book(i+1)=Book(i)-(Book(i)/2+2) 得出； 由 Book(5)-(Book(5)+2)=3 可得出口；算法 #include int Book(int i)

31、 // 構(gòu)造 推函數(shù)：  Book(i);  表示第  i 天要 剩的 數(shù)； { int sum=0; if(i<5) sum=2*(Book(i+1)+2); // 由 Book(i+1)=Book(i)-(Book(i)/2+2)  得出； else return 10; // 由 Book(5)-(Book(5)+2)=3 return sum;  可得出口； } void main() { printf(" 全書(shū)共 %

32、d 頁(yè)。 \n",Book(1)); for(int i=1;i<=5;i++) printf(" 第 %d 天，看 %d+%d 頁(yè)，還剩 %d頁(yè)。 \n",i,Book(i)/2,2,Book(i)/2-2); getchar(); } 運(yùn)行結(jié)果 （ 7）日本著名數(shù)學(xué)游戲?qū)＜抑写辶x作教授提出這樣一個(gè)問(wèn)題：父親將 2520 個(gè)桔子分給 六個(gè)兒子。分完 后父親說(shuō)： “老大將分給你的桔子的 1/8 給老二；老二拿到后連同原先 的桔子分 1/7 給老三；老三拿到

33、后連同原先的桔子分 1/6 給老四；老四拿到后連同原先 的桔子分 1/5 給老五；老五拿到后連同原先的桔子分 1/4 給老六；老六拿到后連同原先 的桔子分 1/3 給老大”。結(jié)果大家手中的桔子正好一樣多。 問(wèn)六兄弟原來(lái)手中各有多少桔 子？ 題目分析 由老大開(kāi)始分給老二，當(dāng)老大拿到老六的后總數(shù)達(dá)到平均數(shù)，以此為入口進(jìn)行遞推。 算法構(gòu)造 第一個(gè)孩子從國(guó)王那里分到的桔子總數(shù)應(yīng)為平均數(shù)減去最后一個(gè)孩子分出去的部分后乘以 8/7 。 算法實(shí)現(xiàn) #include #define DENOMINATOR_MAX

34、8 // 分母最大值 #define DENOMINATOR_MIN 3 // 分母最小值 //a[i][0] 表示第 i 個(gè)孩子分出的桔子總數(shù) //a[i][1] 表示第 i 個(gè)孩子從國(guó)王那里分到的桔子總數(shù) int Orange(int a[5][2],int i) { int average=2520/6; int p; if (i==0) { // 第一個(gè)孩子從國(guó)王那里分到的桔子總數(shù)應(yīng)為平均數(shù)減去最后一個(gè)孩子分出去的部分后乘以 8/7 。 a[i][1] = (average-average/(DENOMINATOR

35、_MIN-1))*(DENOMINATOR_MAX-i)/(DENOMINA TOR_MAX -1-i); // 第一個(gè)孩子分給第二個(gè)孩子的桔子數(shù)量。 a[i][0] = a[i][1] - (average-average/(DENOMINATOR_MIN-1)); } else { // 第 i 個(gè)孩子從國(guó)王那里分到的桔子總數(shù)。 a[i][1] = average *(DENOMINATOR_MAX-i)/(DENOMINATOR_MAX-1-i) - Orange(a,i-1); // 第 i 個(gè)孩子分給第 i+

36、1 個(gè)孩子的桔子數(shù)量。 a[i][0] = a[i][1] + Orange(a,i-1) - average; } p=a[i][0]; return p; } // 主函數(shù) void main() { int ora[5][2]={{0,0},{0,0},{0,0},{0,0},{0,0}}; Orange(ora,5); for(int j=0;j<=5;j++) { printf("  第 %d 個(gè)孩子分出  %d 個(gè)橘子。  \n",j+1,ora[j][0]); 

37、 } printf("  國(guó)王最初分配桔子狀況如下所示：  \n"); for(int k=0;k<=5;k++) { printf("  第 %d個(gè)孩子從國(guó)王那里分得  %d 個(gè)橘子。  \n",k+1,ora[k][1]);  } getchar(); } 運(yùn)行結(jié)果 （ 8）某種傳染病第一天只有一個(gè)患者，前 5 天為潛伏期，不發(fā)作也不會(huì)傳染人，第 始發(fā)作，從發(fā)作到治愈需要 5 天時(shí)間，期間每天傳染 3 個(gè)人，求第 N 天共有多少患者。 

38、 6 天開(kāi) 題目分析 第n天的病總?cè)藬?shù)包括 n-1天潛伏的和發(fā)作的在當(dāng)天又傳染的人數(shù)再去掉當(dāng)天治愈的； 算法構(gòu)造 遞推函數(shù)：該病五天內(nèi)潛伏第六天發(fā)病后五天內(nèi)治愈。 Day(n)=Day(n-5)*3+Day(n-1); 算法實(shí)現(xiàn) #include #include int Day(int n) // 遞推函數(shù)：該病五天內(nèi)潛伏第六天發(fā)病后五天內(nèi)治愈。 { int sum=0; if(n<=5) // 五天內(nèi)只有一個(gè)潛伏病人。 return 1; else

39、 { sum=Day(n-5)*3+Day(n-1) ; // 第 n天的病總?cè)藬?shù)包括 n-1 天潛伏的和發(fā)作的在當(dāng)天又傳染的人數(shù)再去掉當(dāng)天治愈的； } //Day(n)=Day(n-5)*3+Day(n-1); return sum; } void main() { int n printf( " 請(qǐng)輸入傳染病發(fā)生后的天數(shù)： \n" ); scanf_s( "%d",&n,2); for(int i=1;i<=n;i++) printf(" 第 %d天 ,得病的人數(shù) %d\n",i,Day(i)); syst

40、em( "pause" ); } 運(yùn)行結(jié)果 選做題：（ 5 選 3） （ 4） 50 個(gè)階梯，你一次可以上一階或兩階，走上去，共有多少種走法？題目分析 這道題讓我想到高中時(shí)做過(guò)的同樣的一道排列組合題， 但此題要用計(jì)算機(jī)編程求出具體 數(shù)字，不像高中時(shí)只用代數(shù)式表達(dá)。 算法構(gòu)造

41、 假設(shè)為 20 階： C（ 0 20）+ C（ 1 19）+ C（ 2 18） + C（ 3 17）+ C（ 4 16）+ C（5 15） + C（ 6 14）+ C （ 7 13） + C（ 8 12）+ C （9 11） + C（ 10 10） 算法實(shí)現(xiàn) #include #include int stairs(int n) { if(n==1)return 1; if(n==0)return 1; return stairs(n-1)+stairs(n-2); // 根據(jù)有 1階

42、依次往上遞推發(fā)現(xiàn)符合斐波那契數(shù)列 } // a[n]=a[n-1]+a[n-2] void main() { int j; printf(" 請(qǐng)輸入樓梯階數(shù)： \n"); scanf_s("%d",&j,2); for(int i=1;i<=j;i++) { printf(" 當(dāng)有 %d 階樓梯 ,共有 %d種走法。 \n",i,stairs(i)); } system("pause"); } 運(yùn)行結(jié)果 數(shù)據(jù)可能過(guò)大或者電腦太 low 等了幾分鐘未見(jiàn)結(jié)果，根據(jù)后幾階時(shí)可判斷是對(duì)的。

43、 經(jīng)驗(yàn)歸納 有些題看似困難當(dāng)理清思路也可有據(jù)可循。 （ 2）遞歸將一個(gè)整數(shù)輸出。形如654321，輸出 1,2,3,4,5,6 題目分析 將一個(gè)整數(shù)逆序輸出可以看做把一個(gè)字符串逆序輸出，用指針逐個(gè)輸出。 算法構(gòu)造 reverse( const char *p) 字符串遞推函數(shù)：設(shè)定字符串指針 *p ； 算法實(shí)現(xiàn) 程序源代碼 #include void reverse(const char *p) // 字符串遞推函數(shù)：

44、設(shè)定字符串指針 *p ； { if(*p==\0) // 指針從右向左移動(dòng)由于判斷字符串尾部位置； return; reverse(p+1); // 指針向前移動(dòng) p+1 printf("%c ， ",*p);/ / 輸出當(dāng)前指針指向的字符； } void main() { char *pString; pString="123456"; printf(" 輸入的字符串： %s\n",pString); reverse(pString); getchar(); } 運(yùn)行結(jié)果

45、 經(jīng)驗(yàn)歸納 巧用字符串指針可以簡(jiǎn)化程序。 （ 3）用遞歸實(shí)現(xiàn)分解質(zhì)因數(shù)。形如：12=2*2*3 題目分析 質(zhì)因數(shù) n 即只能被本身和 1 整除的數(shù)，在 2 到 可分解。 算法構(gòu)造  n-1  間篩選能被  n 整除且是質(zhì)因數(shù)的數(shù)即 bool IsPrime(int num)//  判斷質(zhì)因數(shù)；  if((IsPrime(i))&&( num % i == 0 ))//  判斷除數(shù)是否為質(zhì)因數(shù)；

46、 num = num / i;PrimeFactorization(num); 若是其一則保留對(duì)剩下的商繼續(xù)判別；算法實(shí)現(xiàn) #include #include // 質(zhì)因數(shù)判斷函數(shù) bool IsPrime(int num) // 判斷質(zhì)因數(shù)； { int i; for (i = 2; i < num; i++) { if ( num % i == 0 ) { // 如果從 2到 num-1的數(shù)里有能被整除的，說(shuō)明num不是質(zhì)因數(shù)。 return false;

47、 } } / / 如果從 2到 num-1的數(shù)里沒(méi)有能被整除的，說(shuō)明 num是質(zhì)因數(shù)。 return true; } void PrimeFactorization(int num) { int i; for (i=2; i<=num; i++) { if(i == num) { printf("%d",i); } else if((IsPrime(i))&&( num % i == 0 )) // 質(zhì)因數(shù)判斷函數(shù)； { // 將找到的質(zhì)因數(shù)追加到字符串中。 printf(

48、"%d*",i); // 將剩下部分遞歸分解。 num = num / i; PrimeFactorization(num); break; } } } void main() { int num; printf(" 請(qǐng)輸入一個(gè)小于 10 位的整數(shù)： \n"); scanf_s("%d",&num,10); printf(" 質(zhì)因數(shù)分解： \n%d=",num); //調(diào)用分解質(zhì)因數(shù)函數(shù)。 PrimeFactorization(num); printf("\n"); system("pause"); } 運(yùn)行結(jié)果 經(jīng)驗(yàn)歸納 弄清題目關(guān)鍵字的概念對(duì)編程很是關(guān)鍵。 五、實(shí)驗(yàn)總結(jié) 編程蠻有意思，在這里能夠格物致知看到不一樣的世界。