算法题的演示

Ⅰ 数学建模第四章 图论 part4.2最短路径问题-Dijkstra算法

1.Dijkstra算法介绍

算法特点：

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

算法的思路

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。 

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点， 

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

2、Dijkstra算法示例演示

我求下图，从顶点v1到其他各个顶点的最短路径.

首先第一步，我们先声明一个dis数组，该数组初始化的值为：

我们的顶点集T的初始化为：T={v1}

既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。 

为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果： 

因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值.另外，v1-v5-v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。更新后的dis数组如下图： 

然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下： 

因此，从图中，我们可以发现v1-v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为：

Ⅱ 《选择排序算法分析及程序实现》教学案例:十大排序算法

本节教学内容选自浙江教育出版社出版的《算法与程序设计》。出于理论与实践相结合的考虑，将教材第二章第三节的“排序”和第五章第三节的“排序算法的程序实现”教学内容合并起来教学，以加深学生对算法和程序设计的关系的体会。排序算法是程序设计中的重要算法，对它的学习既是对已经学过的三种程序设计结构的综合运用，又能为后续对分查找的学习作好铺垫。
一、教学目标
知识与技能：理解选择排序算法；能解释冒泡排序、选择排序的优势；能由此及彼，归纳排序中的数字规律，探索更有效率的排序算法；能在VB中规范地编写程序。
过程与方法：在回顾冒泡排序算法的过程中自然引出选择排序，并以任务分解、逐级递进的方式化解难点。以讲授法和探究法相结合的方式，让学生在自主探索中思考发现、归纳总结，逐步将排序方法用程序语言表达出来，最终实现程序，解决问题。
情感、态度与价值观：培养学生对程序设计的兴趣，激发学生探索新知的欲望和热情，让学生体会将自己的逻辑思维通过程序设计的方式实现的喜悦感和成就感。
二、学情分析
选择排序算法的学习是在学生学习了“冒泡排序”的基础上进行的，而且学生对VB的基本语句、三种程序结构、数组变量、随机数的生成，以及事件、过程等能较好地理解、应用，因此，程序界面的设计、无序的随机数的生成、通用变量（n、数组变量）的定义等预备工作事先由教师准备。
三、教学重点、难点
教学重点：理解选择排序算法，以及算法在VB中的实现。
教学难点：如何找到一组数中的最小数（或最大数），用来记录最小值（或最大值）的变量t的初值为什么是i，用来记录查找的位置的循环变量j的初值与终值的确定。
四、素材准备
1.学生素材：Form1.frm
该窗体的程序界面如图1所示，其中“自动生成数据”这一事件已能实现，“选择排序”的代码留空。
2.教师素材：PPT课件
五、教学过程
1.复习回顾，自然引出选择排序
问题：若要将34、45、32、12、33这组数据按从小到大的顺序进行冒泡排序，则需进行几次冒泡排序，每次的排序结果分别是什么，整个排序过程中进行了几次数据交换，是否能减少交换次数？
设计意图：复习冒泡排序算法，并通过分析数据交换的次数，提问学生是否有办法让数据交换的次数变少，引发学生思考与发现，进而引出选择排序算法。
2.实例示范，初步了解选择排序
教师以对四个无序整数进行递增排序处理为例（假定数据已存放在数组中），简要阐述选择排序算法。
第一遍：从第一个位置到最后一个位置中，找出最小值所在的位置，将该位置的值与第一个位置的值亏拿交换。
第二遍：从第二个位置到最后一个位置中，找出最小值所在的位置，将该位置的值与第二个位置的值交换。
依次类推，直到所有数都有序（如图2）。
随后，学生在了解选择排序的基础上完成以下课堂练习：
若要将34、45、32、12、33这一组数据按从小到大的顺序进行选择排序，则需进行几次选择排序，每次的排序结果分别是什么，整个排序过程中进行了几次数据交换？
学生在完成的过程中，与一开始对这组数据进行冒泡排序的过程进行比较，发现对这组数据来说，选择排序的交换次数仅为三次，大大优于销搭搭冒泡排序。
设计意图：本部分仅对选择排序作简要阐述，枝数未对其中“如何找到最小数问题”进行具体说明，旨在让学生先了解选择排序算法，对其有总体认识，树立信心。
3.层层递进，深入理解选择排序
在学生初步了解选择排序后，教师进而引导学生将选择排序的每一遍排序分解为两个步骤，即：
第一步：从位置1到位置n中，找到最小数的位置；若最小数不在位置1，则将最小数与位置1的数据进行交换。
第二步：从位置2到位置n中，找到最小数的位置；若最小数不在位置2，则将最小数与位置2的数据进行交换。
……
步骤分解后，接下来的关键是如何将这些步骤一一实现。教师以第一遍选择排序为例，对算法进行演示，具体如下：
先预设两个变量：变量t和j。其中变量t用来记录最小值所在的位置；变量j用来记录查找的位置。
【算法演示】
第一步：从位置1到位置4中，找到最小数的位置，具体过程如图3所示。
【分析】第一遍选择时，令记录最小值所在的位置的初始值为1，即t=1。故将d(t)依次与d(2)、d（3）、d(4)进行比较，每次比较可描述为：
第一次：当 j=2时
如果d(t)>d(j)，则令t=j
第二次：当 j=3时
如果d(t)>d(j)，则令t=j
第三次：当 j=4时
如果d(t)>d(j)，则令t=j
经过这样三次比较后，就完成了第一遍选择排序。
【观察】学生比较上述三次描述，发现j=2、3、4时，所执行的操作都是“如果d(t)>d(j)，则令t=j”，也就是说执行的是重复操作，继而就想到了用循环语句来实现这个操作，也就是说，上面三次比较可整合为如下语句：
t=1
for j=2 to 4
如果d(t)>d(j)，则令t=j
Next j
第二步：若最小数不在位置1，则将最小数与位置1的数据进行交换。
这一步学生普遍较容易理解，教师给出伪代码：如果t>1，则交换d(1)和d(t)。
此时，教师引导学生到教师事先分发的form1窗体中完成第一次选择排序的程序代码，并进行调试运行。
当然，调试运行过程中，学生会发现单击“选择排序”按钮后，不能将排好序的数据输出到列表框2中，随后找到原因，将输出语句补充完整。由于输出语句学生已在冒泡排序中接触过，故能自行完成。
当学生完成了第一遍选择排序后，略有成就感，教师顺势提出第二遍选择排序。理解了第一遍选择排序，学生对第二遍、第三遍就不再那么陌生了，理解起来也更容易了。教师简单演示第二遍、第三遍选择排序算法后，学生便能在第一遍选择排序的基础上对代码略作修改，完成第二遍、第三遍选择排序的程序代码。
设计意图：分解问题难点，并能让学生自己总结归纳出解决的办法，既能落实知识点，又能激发学生的求知与探索欲望。
4.归纳总结，由特殊到一般
当学生通过三遍选择排序完成了对四个数进行排序的操作时，便跃跃欲试，想要对更多的数进行排序，于是就开始找寻规律，他们会发现这三部分程序的主体大部分是相似的，只不过变量t与变量j的值有所变化。教师再继续引导学生去找出变量t和变量j的变化规律。
为了便于学生更好地发现规律，教师在PPT上将三遍选择的代码放在一起，并将关键部分用红色字体标出，如图4所示。经过观察、分析，学生得出第i遍选择的程序代码。
至此，选择排序的核心代码已基本完成，只要学生将变量i的范围确定即可，而i的范围即为选择排序进行的遍数。这一点学生已经在一开始的算法分析中明确了，即：如果有n个数，需进行的选择遍数为n-1次。
故，学生可得出选择排序代码如下：
Fori= 1 to n-1
t = i
For j = i+1 to n
If d(t) > d(j) Thent=j
Next j
If t > i Then
temp = d(i)
d(i)=d(t)
d(t) = temp
End If
Next i
整个过程下来，算法的基本框架以及程序的结构变得一目了然。
设计意图：将选择排序像剥洋葱一样一层层剥离，又慢慢地将其整合。整个过程中引导学生自己探索、发现规律、找寻方法，进而解决问题，不仅排除了学生对复杂算法的畏惧感，同时还激发了学生的学习热情。
5.调试运行，完成课堂任务
基本任务：学生先完成将一组数进行从小到大顺序排序的程序调试。然后，修改程序，使其能将一组无序数据进行降序排列。
拓展任务：时间充裕的学生可以根据知识拓展内容比较冒泡排序和选择排序的耗时，并在程序中体现出交换次数。
知识拓展：比较冒泡排序和选择排序的消耗时间。
T1=timer (timer是取得当前时间的函数)
T2=timer
Label4.caption=“冒泡排序运行时间:”& t2-t1 &“秒”
设计意图：通过由将一组数据进行递增排序改为递减排序，使学生明白程序中决定递增或递减的关键语句是什么。而拓展任务则是为了给有能力的学生提供更多的学习机会和展示自我的平台。
（作者单位：浙江宁波市北仑中学）

Ⅲ 图的相关算法（二）：最小生成树算法

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

例如，对于上图中的连通网可以有多棵权值总和不相同的生成树。

克鲁斯卡尔（Kruskal）算法，是用来求加权连通图的最小生成树的算法。

基本思想 ：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法 ：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林羡册乎中，并使得森林不产生回路，直到森林变成一棵树为止。

以图G4为例（更详细的可以参考《算法导论》p367），对Kruskal进行演示（假设，用数组R保存最小生成树结果）。

第1步 ：将边<E,F>加入R中。
边<兄悉E,F>的权值最小，因此将它加入到最小生成树结果R中。
第2步 ：将边<C,D>加入R中。
上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。
第3步 ：将边<D,E>加入R中。
上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。
第4步 ：将边<B,F>加入R中。
上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。
第5步 ：将边<E,G>加入R中。
上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。
第6步 ：将边<A,B>加入R中。
上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。

此时，最小生成树构造完成！它包括的边依次是： <E,F> <C,D> <D,E> <B,F> <E,G> <A,B> 。

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：
问题一 对图的所有边按照权值大小进行排序。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一用排序算法排序即可。
问题二，处理方式：记录顶点在“最小生成树”中的终点，顶点的终点是“在最小生成树中与它连通的最大顶点"(关于这一点，后面会通过图片给出说明)。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 以下图来进行说明：

在将<E,F> <C,D> <D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点：

关于终点，姿迹就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 因此，接下来，虽然<C,E>是权值最小的边。但是C和E的重点都是F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。

普里姆（Prim）算法，也是求加权连通图的最小生成树的算法。

基本思想
对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有顶点）的边中选取权值最小的边（u，v），将顶点v加入U中，将边（u,v）加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，此时集合T中包含了最小生成树中的所有边。

以上图G4为例，来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。

初始状态 ：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步 ：将顶点A加入到U中。
此时，U={A}。
第2步 ：将顶点B加入到U中。
上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。
第3步 ：将顶点F加入到U中。
上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。
第4步 ：将顶点E加入到U中。
上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。
第5步 ：将顶点D加入到U中。
上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。
第6步 ：将顶点C加入到U中。
上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。
第7步 ：将顶点G加入到U中。
上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(F,G)的权值最小。将顶点G添加到U中；此时，U=V。

此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。

Ⅳ 题目1:一个简单的算法演示程序(JAVA语言实现)

1. 选择一个算法（提供选择见下），利用各种方法（图形、动画等）演示算法的演示过程。
2. 可以进行手动演示，也可以自动步进式演示。
3. 允许用户设置算法的各个输入参数，以及自动步进式演示中的时间间隔。
4. 不同的算法输入要求见下。
界面要求：
1. 尽量使用图形界面实现，要符合日常软件使用规范来设计菜单和界面。
2. 如果无法实现图形界面，则在命令行方式下也需要提供菜单，方便用户操作。
其他要求：
1. 标识符命名遵循Windows命名规范。
2. 能够注意各种异常处理，注重提高程序运行效率。
提交内容：
1. 全部源代码。
2. 软件设计和使用说明书（UML类图；实现的功能、主要技术；使用帮助文档）
参考算法：
1. 最小生成树算法：Prim算法、Kruskal算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
2. 单源最短路算法：Dijkstra算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
3. 最优编码算法：Huffman编码算法。允许用户输入一段英文文字，或者打开一个txt文档（英文内容），据此文档内容进行编码。要求动态列出每个字符的出现概率统计结果以及对应编码。
4. 其他可供演示的具有一定难度的算法，如关键路径问题、有向图的极大连通分支等。

Ⅳ 经典笔试面试知识整理，数据结构与算法(代码演示)

题目描述：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

输入描述: array： 待查找的二维数组 target：查找的数字

输出描述:

查找到返回true，查找不到返回false

题目描述：

请实现一个函数，将漏祥一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题目描述： 输入一个链表，从尾到头打印链表每个节点的值。

输入描述： 输入为链表的表头

输出描述： 输出为需要打印的“新链表”的表头

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一喊搜铅个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

1、题目描述：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

2、题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

3、题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

4、题目描述：

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

1、题目描述：

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

2、题目描述：

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

题目描述：

输入一个整数数组，实现一个函数来调整郑好该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作， 队列中的元素为int类型。

题目描述：

输入一个链表，输出该链表中倒数第k个结点。

Ⅵ 对给定的网和起点，实现求解最小生成树的PRIM算法，并给出动态演示。万分火急

最近忙着考试，没时间做图形界面来动态演示部分啦，先给你一个基本的Prim程序吧，希望有所帮助。
/**
* PRIM(简单版) 最小生成树算法 (Minimum Spanning Tree)
* 输入：图g； // 有向图或者无向图
* 输出：(1)最小生成树长sum；
* (2)最小生成树prev。
* 结构: 图g用邻接矩阵表示，最短边长dist用数组表示。
* 算法：Prim算法
* 复杂度：O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n; // n : 顶点个数
vector<vector<int> > g; // g : 图(graph)(用邻接矩阵(adjacent matrix)表示)
vector<bool> known; // known : 各点是否已经选取
vector<早扰int> dist; // dist : 已选取点集到凳枯未选取点的最小边长
vector<int> prev; // prev : 最小生成树中各点的前一顶点
int s; // s : 起点(start)
int sum; // sum : 最小生成树长

bool Prim() // 贪心算法(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化起点到自身的路径长为0。
int i;
for (i = 0; i < n; ++i)
{
int min = INT_MAX, v;
for (int i = 0; i <陆粗旦 n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 寻找未知的最短路径长的顶点v，
if (min == INT_MAX) break; // 如果找不到，退出；
known[v] = true; // 如果找到，将顶点v设为已知，
sum += dist[v]; // 调整最小生成树长
for (int w = 0; w < n; ++w) // 遍历所有v指向的顶点w，
if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
dist[w] = g[v][w], prev[w] = v; /* 调整顶点w的最短路径长dist和最短路径的前一顶点 prev。 */
}
return i == n; // 如果选取顶点个数为n，成功。
}

int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;
g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
g[4][6] = g[6][4] = 6;
g[5][6] = g[6][5] = 1;

s = 0; // 起点任选
sum = 0;
if (Prim())
{
cout << sum << endl;
for (int i = 1; i < n; ++i)
if(i != s) cout << prev[i] << "->" << i << endl;
}
else
{
cout << "Some vertex cann't be reached." << endl;
}

system("pause");
return 0;
}