C#語言編程求解斐波那契數(shù)列--湖北科技職業(yè)學(xué)院

1、C#語言編程求解斐波那契數(shù)列教學(xué)設(shè)計湖北科技職業(yè)學(xué)院 宋薇所屬學(xué)科：計算機科學(xué)與技術(shù) 99所屬專業(yè)：計算機應(yīng)用所屬課程：C#程序設(shè)計適用對象：高職高專計算機應(yīng)用專業(yè)學(xué)生知 識 點： 遞歸法 迭代法1. 教學(xué)背景隨著計算機的普及，編寫程序來解決現(xiàn)實生活中的一些復(fù)雜計算問題越來越受到人們的青睞。大到登月、探火星，小到吃飯、用手機，人類發(fā)展到今天已經(jīng)脫離不開計算機程序。不管我們有沒有覺察到，我們每天的生活都至少接觸了上百個程序或系統(tǒng)。這兩年，在歐美已經(jīng)掀起了一股編程熱，從將編程教育納入小學(xué)正式課程，到CodeSchool、Codecademy等面向大眾的編程學(xué)習(xí)網(wǎng)站出現(xiàn)。大西洋雜志指出，根據(jù)美國勞工

2、統(tǒng)計局的數(shù)據(jù)顯示，計算機編程行業(yè)的擴張率比所有行業(yè)平均擴張率高出30%，2013年平均工資為90,000美元。 C#程序設(shè)計作為高職院校計算機應(yīng)用專業(yè)程序設(shè)計的入門必修課程，學(xué)好本門課程對該專業(yè)學(xué)生未來的編程生涯起到深遠的影響。本節(jié)課主要介紹如何利用迭代法和遞歸法，采用C#語言編程求解斐波拉契數(shù)列。首先通過經(jīng)典的數(shù)學(xué)問題導(dǎo)入斐波拉契數(shù)列，然后從程序分析、設(shè)計到實現(xiàn)入手，通過形象生動的流程圖、動畫及真實的程序代碼實現(xiàn)及結(jié)果分析，激發(fā)學(xué)生學(xué)習(xí)的積極性，引導(dǎo)學(xué)生主動學(xué)習(xí)。2. 教學(xué)目標2.1知識目標:了解斐波那契數(shù)列的由來與應(yīng)用、遞推公式;掌握迭代法與遞歸法的求解過程。2.2能力目標:通過斐波那契數(shù)

3、列的求解，培養(yǎng)學(xué)生分析問題，解決問題的能力，培養(yǎng)學(xué)生對實際問題進行分析并抽象出數(shù)學(xué)模型，再進行算法設(shè)計，最后轉(zhuǎn)換為程序的能力。2.3情感目標：通過感受斐波那契數(shù)列神奇的性質(zhì)，以及計算機解決問題的魅力，培養(yǎng)學(xué)生學(xué)習(xí)程序設(shè)計的積極性、主動性，讓學(xué)生覺得編寫出程序原來是這么有成就感的事情。3. 教學(xué)方法3.1啟發(fā)式教學(xué)：從生活實際出發(fā)，以啟發(fā)學(xué)生的思維為核心，調(diào)動學(xué)生的學(xué)習(xí)主動性和積極性，把被動的灌輸式教學(xué)轉(zhuǎn)變?yōu)橹鲃拥奈∈綄W(xué)習(xí)。3.2情景教學(xué)：教師有目的地引入一個生動具體的場景，以生動形象的情境激起學(xué)生學(xué)習(xí)情緒，讓學(xué)生一起探索、體驗，從而幫助學(xué)生理解知識點。4. 教學(xué)思想“微課”是通過精心的信息化

4、教學(xué)設(shè)計，以流媒體形式展示的圍繞某個知識點或教學(xué)環(huán)節(jié)開展的簡短、完整的教學(xué)活動。高職計算機應(yīng)用專業(yè)學(xué)生的教學(xué)過程，應(yīng)該從實際的崗位素質(zhì)能力、知識需求出發(fā)，以培養(yǎng)學(xué)生實際動手能力和解決問題能力為目的。遵循高職教育“夠用為度“的課堂原則，以項目實現(xiàn)過程來分解復(fù)雜的理論知識，結(jié)合一個具體的項目為案例，循序漸進，引導(dǎo)學(xué)生主動學(xué)習(xí)。5. 課程設(shè)計6.教學(xué)步驟教學(xué)內(nèi)容設(shè)計意圖1問題導(dǎo)入(1分13秒)通過電影了解斐波那契數(shù)列吸引學(xué)生注意力2問題分析(2分10秒)分析斐波那契數(shù)列遞推規(guī)律引導(dǎo)學(xué)生理解遞歸算法設(shè)計思路3編程實現(xiàn)（1分）講解遞歸法運行代碼介紹遞歸法應(yīng)用，引導(dǎo)學(xué)生發(fā)現(xiàn)遞歸法的特性4知識拓展（3分30

5、秒）講解迭代法求解思路介紹迭代法應(yīng)用，引導(dǎo)學(xué)生對不同算法進行比較5小結(jié)（40秒）小結(jié)課程回顧整節(jié)課的內(nèi)容5.1問題導(dǎo)入(1分13秒)什么是斐波那契數(shù)列？這個數(shù)列有什么應(yīng)用的意義，為什么要求解斐波那契數(shù)列呢？從nature by numbers工作室制作的微電影中了解這一答案。讓我們首先從一個數(shù)列開始，它的前面幾個數(shù)是：1、1、2、3、5、8、13、21、34、55、89、144這個數(shù)列的名字叫做“斐波那契數(shù)列”，這些數(shù)被稱為“斐波那斐數(shù)”。斐波那契數(shù)列是一個非常美麗、和諧的數(shù)列，它的形狀可以用排成螺旋狀的一系列正方形來說明，起始的正方形的邊長為1，在它左邊的那個正方形的邊長也是我，在這兩個正方

6、形的上方再放一個正方形，其邊長為2，以后順次加上邊長為3、5、8、13、21等等的正方形。這些數(shù)字每一個都等于前面兩個數(shù)這和，它們正好構(gòu)成了斐波那契數(shù)列。以斐波那契數(shù)為邊的正方形，然后在正方形里面畫一個90度的扇形，連起來的弧線就是斐波那契螺旋線。自然界中存在許多斐波那契螺旋線的圖案，大到銀河系的圖形，小到人類耳朵的形狀，從樹梢的松樹果球，到來自大海的海螺都明顯的符合斐波那契螺旋線，因此也被稱為“黃金螺旋”。如果我們統(tǒng)計相鄰兩個斐波那契數(shù)的比值，我們將發(fā)現(xiàn)，這個比值隨著序號的增加而逐漸趨于黃金分割比。即(a+b)/a->1.618。剛才的微電影，相信已經(jīng)讓同學(xué)們了解了斐波那契數(shù)列的神奇魅

7、力，當然，不僅僅只有影片所介紹的自然生物領(lǐng)域，斐波那契數(shù)列廣泛應(yīng)用于現(xiàn)代物理、化學(xué)與經(jīng)濟學(xué)領(lǐng)域。那么，既然這個數(shù)列如此重要，我們又應(yīng)該如何計算這個數(shù)列呢？5.2問題分析(2分10秒)公元1200年，意大利數(shù)學(xué)家列昂納多.斐波那契在計算之書中第一次將斐波那契數(shù)列推上了歷史的舞臺。在數(shù)學(xué)上，費波那契數(shù)列是這樣來定義的：（1） 分析手工計算數(shù)列的難度仔細觀察一下數(shù)列，你會發(fā)現(xiàn)當數(shù)列中的數(shù)據(jù)增長得越來越快時，僅用手工計算的方法就會表現(xiàn)的越來越困難。(例如，你愿意用列表的方法求出第40個數(shù)嗎？)我們需要研究計算規(guī)律，找出一般的方法，利用計算機解決這個問題。（2） 通過PPT動畫演示斐波那契數(shù)列的求解過程

8、，引導(dǎo)學(xué)生發(fā)現(xiàn)在前進中規(guī)?？s小與回退中得到最終結(jié)果的求解思路。（3） 介紹遞歸法的應(yīng)用與條件遞歸有兩個基本條件：1、是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決。2、在函數(shù)實現(xiàn)時，這個解決問題的函數(shù)必須有明顯的結(jié)束條件，否則就會產(chǎn)生無限遞歸的情況。讓我們來看看斐波那契數(shù)列是如何滿足遞歸的兩個條件的：1、對于一個n>2, 求f(n)只需求出f(n-1)和f(n-2)，也就是說規(guī)模為n的問題，轉(zhuǎn)化成了規(guī)模更小的問題；2、對于n=0和n=1，存在著簡單情境：f(0) = 0, f(1) = 1。5.3編程實現(xiàn)(1分)（1） 介紹用迭代法求解的完整源程序,并運行程序分析結(jié)果。這里我們希望統(tǒng)計

9、程序運行時間，因此我們使用了System.Diagnostics命名空間，通過調(diào)用StopWatch類來監(jiān)視代碼，統(tǒng)計程序運行的時間，并以毫秒為單位。int fibRE(n) if(n <2) return n; else return f(n-1) + f(n-2);編寫遞歸調(diào)用的函數(shù)的時候，一定要把對簡單情境的判斷寫在最前面，以保證函數(shù)調(diào)用在檢查到簡單情境的時候能夠及時地中止遞歸，否則，你的函數(shù)可能會永不停息的在那里遞歸調(diào)用了(2) 運行代碼，引導(dǎo)學(xué)生發(fā)現(xiàn)問題，遞歸算法的計算效率較低。分析討論產(chǎn)生這一問題的原因。PPT動畫演示，利用遞歸算法計算Fib(5)的過程中，F(xiàn)ib(1)計算了

10、兩次、Fib(2)計算了3次，F(xiàn)ib(3)計算了兩次，本來只需要5次計算就可以完成的任務(wù)卻計算了9次。事實上，用遞歸法求解斐波那契數(shù)列的復(fù)雜度為指數(shù)級。這個Fibonacci的遞歸實現(xiàn)在計算值時，每次遞歸調(diào)用都觸發(fā)另外兩個遞歸，而這兩個遞歸在調(diào)用的時候每個都還要觸發(fā)兩外的兩個遞歸調(diào)用，再接下去的調(diào)用也是如此?，F(xiàn)在，我們知道，這個冗余的遞歸調(diào)用是以幾何級數(shù)增長的。例如，在遞歸計算Fibonacci(10)時，F(xiàn)ibonacci(3)的值被計算了21次。而在遞歸計算Fibonacci(30)，這個調(diào)用的次數(shù)是駭人的317811次！這個問題隨著規(guī)模的增加會愈發(fā)凸顯，以至于Fib(1000)已經(jīng)無法再

11、可接受的時間內(nèi)算出。隨著參數(shù)增大，計算中重復(fù)增長迅速，最快的微機上一分鐘大約可以算出fib(45)參數(shù)加1，fib多用近一倍時間(指數(shù)增長)。最快的微機一小時算不出fib(55)，算fib(100)要數(shù)萬年。計算需要時間，復(fù)雜計算需要很長時間。這是計算機的本質(zhì)特征和弱點。說明它不是萬能，有些事情“不能”做。大量的遞歸調(diào)用會建立函數(shù)的副本， 耗費大量的時間和內(nèi)存，因此，對于要求執(zhí)行效率較高的問題，比如大規(guī)模的斐波那契數(shù)列求解，并不適合遞歸法求解。5.4問題拓展遞歸(3分30秒)（1）介紹遞歸到非遞歸算法的轉(zhuǎn)換方法遞歸算法是一種自然且合乎邏輯的解決問題的方式，但是遞歸算法的執(zhí)行效率通常比較差。因此

12、，在求解某些問題時，常采用遞歸算法來分析問題，用非遞歸算法來求解問題。把遞歸算法轉(zhuǎn)化為非遞歸算法有如下兩種基本方法：a直接轉(zhuǎn)換法。直接求值，不需要回溯，使用一些變量保存中間結(jié)果，直接用循環(huán)結(jié)構(gòu)實現(xiàn)求值過程。b間接轉(zhuǎn)換法。不能直接求值，需要回溯。利用堆棧的后進先出特性模擬遞歸算法的執(zhí)行過程, 使用堆棧保存中間結(jié)果，從而用非遞歸算法替代遞歸算法。（2）采用第一種方法為大家講解遞歸算法的非遞歸變換。我們現(xiàn)在已經(jīng)得到了迭代公式，那么如何用程序來求解斐波那契數(shù)列呢？首先，我們總結(jié)出斐波那契數(shù)列的特點：第1，2個數(shù)都是1，從第3個數(shù)開始，每個數(shù)都是它前面兩個數(shù)之和。然后，我們可以看出，這是一個迭代問題，不

13、斷用變量的新值取代變量的舊值。當一個問題的求解過程能夠由一個初值使用一個迭代表達式進行反復(fù)的迭代時，就可以由重復(fù)程序描述，即由循環(huán)結(jié)構(gòu)來實現(xiàn)。下面我們用N-S流程圖來描述求解斐波拉契數(shù)列的過程。i=1 ,f1=1 ,f2=1輸入 n 的值當i<=n時假真i<=2f=1f=f1+f2輸出f的值f1=f2f2=f5.5總結(jié)(40秒)了解斐波那契數(shù)列的由來與應(yīng)用、遞推公式;掌握迭代法與遞歸法的求解過程。對于這樣有規(guī)律的數(shù)列問題，我們應(yīng)該總結(jié)出規(guī)律，計算出通用公式，然后進行算法分析，找出求解方法，再用程序語句來實現(xiàn)。7. 教學(xué)特色在教學(xué)過程中，遵循“提出問題-分析問題-解決問題”的步驟，讓學(xué)生在一個具體的學(xué)習(xí)情境中掌握知識點，提高思維分析能力。(1)引用斐波那契數(shù)列這個充滿神奇色彩的數(shù)學(xué)問題，激發(fā)了學(xué)生的學(xué)習(xí)積極性。多媒體課件與動畫等表達方式豐富多彩，形象逼真。(2)運用程序設(shè)計中經(jīng)典的兩種算法：迭代法和遞歸法，詮釋了分析問題、算法設(shè)計和程序?qū)崿F(xiàn)的全過程。8. 教學(xué)小結(jié) 傳統(tǒng)的程序設(shè)計課程存在著各種弊端，在講課時大段代碼令學(xué)生摸不著頭腦。本課程采用項目式教學(xué)，在課堂從需求到實現(xiàn)，逐步引導(dǎo)學(xué)生發(fā)現(xiàn)問題、解決問題，讓學(xué)生主動思考，從而使得學(xué)生對知