C语言课件 第27 28章.ppt

第27章 k阶斐波那契序列的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第27章 k阶斐波那契序列的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第27章 k阶斐波那契序列的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第27章 k阶斐波那契序列的实现,问题描述 问题分析及实现 开发过程常见问题及解决,k阶斐波那契序列的实现,斐波那契（fibonacci）序列在自然界中的出现是非常地频繁，人们深信这不是偶然的。延龄草、野玫瑰、金凤花、百合花、蝴蝶花、雏菊等它们的花瓣的数目都具有斐波那契数。本章将实现一个求k阶斐波那契序列的程序。,27.1 问题描述,一个序列：1，1，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 问题分析,斐波那契的序列求解的过程，就是打印对序列各项累加显示的过程。那么如何对一个数n累加呢？简单可以理解为：从零开始，逐个将计算的结果值放进合计中，然后合计值又等于合计值加上循环变量。,27.2.2 问题实现,为了实现这个问题求解的程序，将程序分解功能。一部分功能是程序所使用的数据结构的声明。在此程序中，采用队列的方式记录每一个元素节点。另一部分功能是将输入、计算、输出结果合并为一个实现过程。,27.2.2 问题实现,1. 采用结构体保存过程数据 通过定义两个结构体类型，分别记录二叉树的信息和编码的信息，代码如下（代码27-1.txt）。 01 #include 02 #include 03 #define max 100 /*最大队列长度*/ 04 typedef struct 05 06 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 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。 开发中，要如何理解斐波那契呢？假设n为第一项，m为第二项，那么第三项就是n+m，第四项就是2m+n。这样理解就会容易的多。 此程序的难点之一斐波那契数如何求出来。在本例中，方法采用的是简单的循环累加求第n项。 (3) 此程序的另一难点，是如何保存斐波那契序列中已经求出的前n项。在本例中，程序保存的前n项序列的序列，存入到了一个动态数组中。这样，显示结果的时候，直接通过for循环打印每一项。,第28章 最短路径的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第28章 最短路径的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第28章 最短路径的实现,问题描述 问题分析及实现 开发过程常见问题及解决,第28章 最短路径的实现,问题描述 问题分析及实现 开发过程常见问题及解决,最短路径的实现,最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。本章实现dijkstra（迪杰斯特拉）的最短路径算法。,28.1 问题描述,最短路径问题的形式包括以下4个： 确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题：求图中所有的最短路径。 本章就使用dijkstra算法来实现形式的路径问题。,28.1 问题描述,提 示：解决最短路径最常用的算法有：a*算法、spfa算法、bellman-ford算法、floyd-warshall算法和johnson算法等。,28.2 问题分析及实现,28.2.1 问题分析 28.2.2 问题实现 28.2.3 程序运行,28.2 问题分析及实现,dijkstra算法是很有代表性的最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。dijkstra算法能得出最短路径的最优解，比如动态路由协议ospf中就用到了dijkstra算法。,28.2.1 问题分析,我们一般会从原点遍历所有与原点相联接的点，找最短路径，再从最短路径中的那个点遍历与之相联的其他原点除外的点，以此类推。但这样做，会产生很多非最短路径。dijkstra算法则不然，其算法为：从原点出发，遍历所有与之相联的点，将原点与这些点存放在表s中，同时记录两节点间的花费代价。将代价最小的代价值和这两个节点移动到表t，注意其中一个是原点。把这与这个节点联接的子节点找出，放在表s，算出子节点到原点的代价。重复查代价最小的节点，直到表s空。,28.2.2 问题实现,dijkstra算法的输入包含了一个有权重的有向图g，以及g中的一个来源顶点s。 为实现有向图的搜索，需要定义一个数组来记录有向图的信息，需要定义一个保存最短路径长度的数组。主程序初始化最短路径长度的数组，再循环计算除原点外的其他节点与原点之间的路径，记录花费最小的路径点至dist的数组。最终结果中是dist数组，保存的是原点与其他节点之间的最短路径长度，代码如下（代码28-1.txt）。,28.2.3 程序运行,单击【调试】工具栏中的按钮，根据提示输入数据，按【enter】键，即可输出如下结果。,28.3 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。 在编译程序的时候，如果在编译前只做了一个小小的改动，但却编译时发生很多错误。此时，建议使用ctrl+z键撤消