2013級C++第13周項目——遞歸函數

第一部分 說三道四：計134，3班、4班程式設計大pk

按照課堂訓示的座位，各組坐對位置；

按照指定的組号，建立使用者：userid形如：j1343xx或j1344xx，其中xx是組号，例（j134302和j134414），昵稱寫本組兩名同學的姓名。

第二部分 練習+上機驗證（不必送出上機報告）閱讀下列程式，寫出程式的運作結果。上機時運作程式，與你的預期進行對照、了解。

　　如果對運作結果和其背後的原理仍不了解，請通過單步執行的手段跟蹤了解。

1. 兩個有遞歸函數的程式，要求按課堂示範，畫出調用過程

(1)

預計運作結果是：__________________

實際運作結果是：__________________

(2)

2. 兩個有靜态局部變量的程式，注意靜态局部變量的生存周期及存儲類型

3．下面兩個程式中有全局變量，注意全局變量的生存周期及存儲類型

【項目1-遞歸求奇數連乘的積】類似求階乘，寫出1*3*...*n的遞歸式，并編寫出遞歸函數求解。

【項目2-fibnacci序列】

　　輸出fibnacci序列的第20個數。要求送出兩個程式，fib(int n)的實作分别用疊代方法與遞歸方法實作。提示：如實作困難，先從講義看求階乘的疊代方法與遞歸方法實作，深入體會後再進行設計。

　　參考程式如下：

【項目3-二進制轉換】

　　輸入一個整數，要求輸出對應的二進制形式，請用遞歸函數實作。

　　提示1：二進制整數轉換為二進制的方法——除2取餘，由後到前将餘數“串”起來，即為對應的二進制。如下圖，38對應的二進制數為：100110。

　　提示2：搞清楚本周第二部分練習1（1）将有助于此項目的解決。

【項目4——最大公約數】

　　分别用非遞歸函數和遞歸函數，用輾轉相除法求兩個正整數a和b的最大公約數，并體會疊代法和遞歸法在處理問題上各自的思路。

【項目5-漢諾塔】

　　漢諾塔（又稱河内塔）問題是源于印度一個古老傳說的益智玩具。古代有一個梵塔，塔内有三個座a、b、c，a座上有64個盤子，盤子大小不等，大的在下，小的在上。有一個和尚想把這64個盤子從a座移到c座，但每次隻能允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下，小盤在上。在移動過程中可以利用b座，下面左圖給出了移動方法的提示。請編制遞歸函數輸出盤子數為4時（程式調試後，試試15個、20個，直至64個，看看會如何），移動的方案。圖為盤子數為3時的輸出供參考。

參考代碼如下：

【項目5擴充】如果要求出盤子移動的次數呢？請改寫程式。

==================== 迂者 賀利堅 csdn部落格專欄=================

======== 為it菜鳥起飛鋪跑道，和學生一起享受快樂和激情的大學 =======