《C语言课件 第27 28章.ppt》由会员分享，可在线阅读，更多相关《C语言课件 第27 28章.ppt（27页珍藏版）》请在三一办公上搜索。
1、第27章K阶斐波那契序列的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第27章K阶斐波那契序列的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第27章K阶斐波那契序列的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第27章K阶斐波那契序列的实现,问题描述 问题分析及实现 开发过程常见问题及解决,K阶斐波那契序列的实现,斐波那契（Fibonacci）序列在自然界中的出现是非常地频繁，人们深信这不是偶然的。延龄草、野玫瑰、金凤花、百合花、蝴蝶花、雏菊等它们的花瓣的数目都具有斐波那契数。本章将实现一个求K阶斐波那契序列的程序。,27.1 问题描述,一个序列：1，1，2
2、，3，5，8就是一个斐波那契序列。他们都是前面相邻两项之和，构成了后一项，这就是斐波那契序列的定义。而K阶斐波那契序列是指前K-1项均为0，第k项为1，以后的每一项都是前K项的和。本章我们就来实现此序列。,27.2 问题分析及实现,27.2.1 问题分析27.2.2 问题实现27.2.3 程序运行,27.2 问题分析及实现,由问题描述可知，我们要实现的是打印斐波那契序列。斐波那契的序列，计算起来比较简单，根据定义，无非就是对一个数的累加的过程。知道了斐波那契的本质是累加的一个过程，如何编写呢？,27.2.1 问题分析,斐波那契的序列求解的过程，就是打印对序列各项累加显示的过程。那么如何对一个数
3、N累加呢？简单可以理解为：从零开始，逐个将计算的结果值放进合计中，然后合计值又等于合计值加上循环变量。,27.2.2 问题实现,为了实现这个问题求解的程序，将程序分解功能。一部分功能是程序所使用的数据结构的声明。在此程序中，采用队列的方式记录每一个元素节点。另一部分功能是将输入、计算、输出结果合并为一个实现过程。,27.2.2 问题实现,1.采用结构体保存过程数据通过定义两个结构体类型，分别记录二叉树的信息和编码的信息，代码如下（代码27-1.txt）。01#include 02#include 03#define MAX 100/*最大队列长度*/04 typedef struct 05 0
4、6 int*m_Base;/*初始化的动态分配存储空间*/07 int m_Front;/*头指针,若队列不空,指向队列头元素*/08 int m_Rear;/*尾指针,若队列不空,指向队列尾元素的下一个位置*/09 SqQueue;/*定义结构体保存队列*/,27.2.2 问题实现,2.求解斐波那契的序列的主函数分两部分计算序列，第一部分，直接将前K项置为初始值0，第二部分，计算K-1项直到计算所得项的值超过要求的值，代码如下（代码27-2.txt）。,27.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入数据，按【Enter】键，即可输出如下结果。,27.3 开发过程常见问题及解
5、决,开发过程常见问题及解决办法如下，仅供参考。开发中，要如何理解斐波那契呢？假设N为第一项，M为第二项，那么第三项就是N+M，第四项就是2M+N。这样理解就会容易的多。此程序的难点之一斐波那契数如何求出来。在本例中，方法采用的是简单的循环累加求第N项。(3)此程序的另一难点，是如何保存斐波那契序列中已经求出的前N项。在本例中，程序保存的前N项序列的序列，存入到了一个动态数组中。这样，显示结果的时候，直接通过For循环打印每一项。,第28章最短路径的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第28章最短路径的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第28章最短路径的
6、实现,问题描述 问题分析及实现 开发过程常见问题及解决,第28章最短路径的实现,问题描述 问题分析及实现 开发过程常见问题及解决,最短路径的实现,最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。本章实现Dijkstra（迪杰斯特拉）的最短路径算法。,28.1 问题描述,最短路径问题的形式包括以下4个：确定起点的最短路径问题：即已知起始结点，求最短路径的问题。确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点
7、的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。全局最短路径问题：求图中所有的最短路径。本章就使用Dijkstra算法来实现形式的路径问题。,28.1 问题描述,提 示：解决最短路径最常用的算法有：A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法和Johnson算法等。,28.2 问题分析及实现,28.2.1 问题分析28.2.2 问题实现28.2.3 程序运行,28.2 问题分析及实现,Dijkstra算法是很有代表性的最短路径算法，用于计算一个节点到其他所有
8、节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，比如动态路由协议OSPF中就用到了Dijkstra算法。,28.2.1 问题分析,我们一般会从原点遍历所有与原点相联接的点，找最短路径，再从最短路径中的那个点遍历与之相联的其他原点除外的点，以此类推。但这样做，会产生很多非最短路径。Dijkstra算法则不然，其算法为：从原点出发，遍历所有与之相联的点，将原点与这些点存放在表S中，同时记录两节点间的花费代价。将代价最小的代价值和这两个节点移动到表T，注意其中一个是原点。把这与这个节点联接的子节点找出，放在表S，算出子节点到原点的
9、代价。重复查代价最小的节点，直到表S空。,28.2.2 问题实现,Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。为实现有向图的搜索，需要定义一个数组来记录有向图的信息，需要定义一个保存最短路径长度的数组。主程序初始化最短路径长度的数组，再循环计算除原点外的其他节点与原点之间的路径，记录花费最小的路径点至Dist的数组。最终结果中是Dist数组，保存的是原点与其他节点之间的最短路径长度，代码如下（代码28-1.txt）。,28.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入数据，按【Enter】键，即可输出如下结果。,28.3 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。在编译程序的时候，如果在编译前只做了一个小小的改动，但却编译时发生很多错误。此时，建议使用Ctrl+Z键撤消最后一次所做的更改，重新编译。OSPF是什么？OSPF（open shortest path first,开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。怎么理解这一算法呢？我们可以这样理解：就是不管它下面有多少个结点，取权值最小的那个，依此类推遍历完所有结点为止！,
