C語言課件 第27 28章.ppt

第27章 k階斐波那契序列的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第27章 k階斐波那契序列的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第27章 k階斐波那契序列的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第27章 k階斐波那契序列的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,k階斐波那契序列的實現(xiàn),斐波那契（fibonacci）序列在自然界中的出現(xiàn)是非常地頻繁，人們深信這不是偶然的。延齡草、野玫瑰、金鳳花、百合花、蝴蝶花、雛菊等它們的花瓣的數(shù)目都具有斐波那契數(shù)。本章將實現(xiàn)一個求k階斐波那契序列的程序。,27.1 問題描述,一個序列：1，1，2，3，5，8就是一個斐波那契序列。他們都是前面相鄰兩項之和，構(gòu)成了后一項，這就是斐波那契序列的定義。而k階斐波那契序列是指前k-1項均為0，第k項為1，以后的每一項都是前k項的和。本章我們就來實現(xiàn)此序列。,27.2 問題分析及實現(xiàn),27.2.1 問題分析 27.2.2 問題實現(xiàn) 27.2.3 程序運行,27.2 問題分析及實現(xiàn),由問題描述可知，我們要實現(xiàn)的是打印斐波那契序列。斐波那契的序列，計算起來比較簡單，根據(jù)定義，無非就是對一個數(shù)的累加的過程。知道了斐波那契的本質(zhì)是累加的一個過程，如何編寫呢？,27.2.1 問題分析,斐波那契的序列求解的過程，就是打印對序列各項累加顯示的過程。那么如何對一個數(shù)n累加呢？簡單可以理解為：從零開始，逐個將計算的結(jié)果值放進合計中，然后合計值又等于合計值加上循環(huán)變量。,27.2.2 問題實現(xiàn),為了實現(xiàn)這個問題求解的程序，將程序分解功能。一部分功能是程序所使用的數(shù)據(jù)結(jié)構(gòu)的聲明。在此程序中，采用隊列的方式記錄每一個元素節(jié)點。另一部分功能是將輸入、計算、輸出結(jié)果合并為一個實現(xiàn)過程。,27.2.2 問題實現(xiàn),1. 采用結(jié)構(gòu)體保存過程數(shù)據(jù) 通過定義兩個結(jié)構(gòu)體類型，分別記錄二叉樹的信息和編碼的信息，代碼如下（代碼27-1.txt）。 01 #include 02 #include 03 #define max 100 /*最大隊列長度*/ 04 typedef struct 05 06 int *m_base; /*初始化的動態(tài)分配存儲空間*/ 07 int m_front; /*頭指針,若隊列不空,指向隊列頭元素*/ 08 int m_rear; /*尾指針,若隊列不空,指向隊列尾元素的下一個位置*/ 09 sqqueue; /*定義結(jié)構(gòu)體保存隊列*/,27.2.2 問題實現(xiàn),2. 求解斐波那契的序列的主函數(shù) 分兩部分計算序列，第一部分，直接將前k項置為初始值0，第二部分，計算k-1項直到計算所得項的值超過要求的值，代碼如下（代碼27-2.txt）。,27.2.3 程序運行,單擊【調(diào)試】工具欄中的按鈕，根據(jù)提示輸入數(shù)據(jù)，按【enter】鍵，即可輸出如下結(jié)果。,27.3 開發(fā)過程常見問題及解決,開發(fā)過程常見問題及解決辦法如下，僅供參考。 開發(fā)中，要如何理解斐波那契呢？假設(shè)n為第一項，m為第二項，那么第三項就是n+m，第四項就是2m+n。這樣理解就會容易的多。 此程序的難點之一斐波那契數(shù)如何求出來。在本例中，方法采用的是簡單的循環(huán)累加求第n項。 (3) 此程序的另一難點，是如何保存斐波那契序列中已經(jīng)求出的前n項。在本例中，程序保存的前n項序列的序列，存入到了一個動態(tài)數(shù)組中。這樣，顯示結(jié)果的時候，直接通過for循環(huán)打印每一項。,第28章 最短路徑的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第28章 最短路徑的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第28章 最短路徑的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第28章 最短路徑的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,最短路徑的實現(xiàn),最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”。本章實現(xiàn)dijkstra（迪杰斯特拉）的最短路徑算法。,28.1 問題描述,最短路徑問題的形式包括以下4個： 確定起點的最短路徑問題：即已知起始結(jié)點，求最短路徑的問題。 確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題。 確定起點終點的最短路徑問題：即已知起點和終點，求兩結(jié)點之間的最短路徑。 全局最短路徑問題：求圖中所有的最短路徑。 本章就使用dijkstra算法來實現(xiàn)形式的路徑問題。,28.1 問題描述,提 示：解決最短路徑最常用的算法有：a*算法、spfa算法、bellman-ford算法、floyd-warshall算法和johnson算法等。,28.2 問題分析及實現(xiàn),28.2.1 問題分析 28.2.2 問題實現(xiàn) 28.2.3 程序運行,28.2 問題分析及實現(xiàn),dijkstra算法是很有代表性的最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。dijkstra算法能得出最短路徑的最優(yōu)解，比如動態(tài)路由協(xié)議ospf中就用到了dijkstra算法。,28.2.1 問題分析,我們一般會從原點遍歷所有與原點相聯(lián)接的點，找最短路徑，再從最短路徑中的那個點遍歷與之相聯(lián)的其他原點除外的點，以此類推。但這樣做，會產(chǎn)生很多非最短路徑。dijkstra算法則不然，其算法為：從原點出發(fā)，遍歷所有與之相聯(lián)的點，將原點與這些點存放在表s中，同時記錄兩節(jié)點間的花費代價。將代價最小的代價值和這兩個節(jié)點移動到表t，注意其中一個是原點。把這與這個節(jié)點聯(lián)接的子節(jié)點找出，放在表s，算出子節(jié)點到原點的代價。重復(fù)查代價最小的節(jié)點，直到表s空。,28.2.2 問題實現(xiàn),dijkstra算法的輸入包含了一個有權(quán)重的有向圖g，以及g中的一個來源頂點s。 為實現(xiàn)有向圖的搜索，需要定義一個數(shù)組來記錄有向圖的信息，需要定義一個保存最短路徑長度的數(shù)組。主程序初始化最短路徑長度的數(shù)組，再循環(huán)計算除原點外的其他節(jié)點與原點之間的路徑，記錄花費最小的路徑點至dist的數(shù)組。最終結(jié)果中是dist數(shù)組，保存的是原點與其他節(jié)點之間的最短路徑長度，代碼如下（代碼28-1.txt）。,28.2.3 程序運行,單擊【調(diào)試】工具欄中的按鈕，根據(jù)提示輸入數(shù)據(jù)，按【enter】鍵，即可輸出如下結(jié)果。,28.3 開發(fā)過程常見問題及解決,開發(fā)過程常見問題及解決辦法如下，僅供參考。 在編譯程序的時候，如果在編譯前只做了一個小小的改動，但卻編譯時發(fā)生很多錯誤。此時，建議使用ctrl+z鍵撤消