C語言課件 第27 28章.ppt

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