算法演示

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

题目描述：

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

输入描述: 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个结点。

‘贰’ 题目1:一个简单的算法演示程序(java语言实现)

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

‘叁’ 如何利用matlab gui制作典型算法的演示系统

步骤/方法 1、新建GUI，保存，并按图示部署各控件（edit text，static texe,listbox,axes），按图修改各String 2、右击“曲线绘图”--View Callbacks--Callback，输入以下程序 3、右击“关闭”--View Callbacks--Callback，输入以下程序 4、右击“listbox控件”--View Callbacks--Callback，输入以下程序 5、运行四大环节，如下（依次为比例环节、惯性环节、比例微分环节、比例积分环节绘图） 6、自行输入函数程序，绘制任意图像，以y=sin(x)为例，点击“曲线绘制”

‘肆’ 基于DES算法的CBC演示程序实现（java）

基于DES算法的CBC演示程序实现（java）
package des;

import java.io.*;
import java.nio.*;
import java.nio.channels.FileChannel;

public class FileDES{
private static final boolean enc=true; //加密
private static final boolean dec=false; //解密

‘伍’ 十大经典算法之动图演示

前面好奇心已经带大家从 冒泡排序 开始，一直到 基数排序 ，从头过了一遍，那么这里归纳一下，将 十个经典算法 的 演示图 都放出来，供大家对比参考学习。

每张图都会附带详细 解说链接 ，有需要的同学可以 点击详细了解学习 。

Python 实现经典算法之冒泡排序

Python 实现经典算法之选择排序

Python 实现经典算法之插入排序

Python 实现经典算法之希尔排序

Python 实现经典算法之归并排序

Python 实现经典算法之堆排序

Python 实现经典算法之快速排序

Python 实现经典算法之计数排序

Python 实现经典算法之桶排序

Python 实现经典算法之基数排序

好了，上面就是 经典十大排序算法 的图片演示了，我 尽可能 的都是放了动图。

部分文章里面可能不止一张图片，我这里碍于篇幅和排版，就没放。有需要的同学也可以 点击 附带的 链接 详细 学习

‘陆’ 一文彻底搞懂BP算法：原理推导+数据演示+项目实战（上篇）

反向传播算法（Backpropagation Algorithm，简称BP算法）是深度学习的重要思想基础，对于初学者来说也是必须要掌握的基础知识！本文希望以一个清晰的脉络和详细的说明，来让读者彻底明白BP算法的原理和计算过程。

全文分为上下两篇，上篇主要介绍BP算法的原理（即公式的推导），介绍完原理之后，我们会将一些具体的数据带入一个简单的三层神经网络中，去完整的体验一遍BP算法的计算过程；下篇是一个项目实战，我们将带着读者一起亲手实现一个BP神经网络（不使用任何第三方的深度学习框架）来解决一个具体的问题。

图 1 所示是一个简单的三层（两个隐藏层，一个输出层）神经网络结构，假设我们使用这个神经网络来解决二分类问题，我们给这个网络一个输入样本 ，通过前向运算得到输出 。输出值 的值域为 ，例如 的值越接近0，代表该样本是"0"类的可能性越大，反之是"1"类的可能性大。

为了便于理解后续的内容，我们需要先搞清楚前向传播的计算过程，以图1所示的内容为例：

输入的样本为：

第一层网络的参数为：

第二层网络的参数为：

第三层网络的参数为：

第一层隐藏层有三个神经元： 、 和 。该层的输入为：

以 神经元为例，则其输入为：

同理有：

假设我们选择函数 作为该层的激活函数（图1中的激活函数都标了一个下标，一般情况下，同一层的激活函数都是一样的，不同层可以选择不同的激活函数），那么该层的输出为： 、 和 。

第二层隐藏层有两个神经元： 和 。该层的输入为：

即第二层的输入是第一层的输出乘以第二层的权重，再加上第二层的偏置。因此得到和的输入分别为：

该层的输出分别为： 和 。

输出层只有一个神经元 ：。该层的输入为：

即：

因为该网络要解决的是一个二分类问题，所以输出层的激活函数也可以使用一个Sigmoid型函数，神经网络最后的输出为： 。

在1.1节里，我们已经了解了数据沿着神经网络前向传播的过程，这一节我们来介绍更重要的反向传播的计算过程。假设我们使用随机梯度下降的方式来学习神经网络的参数，损失函数定义为 ，其中 是该样本的真实类标。使用梯度下降进行参数的学习，我们必须计算出损失函数关于神经网络中各层参数（权重 和偏置 ）的偏导数。

假设我们要对第 层隐藏层的参数 和 求偏导数，即求 和 。假设 代表第 层神经元的输入，即 ，其中 为前一层神经元的输出，则根据链式法则有：

因此，我们只需要计算偏导数 、 和 。

前面说过，第k层神经元的输入为： ，因此可以得到：

上式中， 代表第 层神经元的权重矩阵 的第 行， 代表第 层神经元的权重矩阵 的第 行中的第 列。

我们以1.1节中的简单神经网络为例，假设我们要计算第一层隐藏层的神经元关于权重矩阵的导数，则有：

因为偏置b是一个常数项，因此偏导数的计算也很简单：

依然以第一层隐藏层的神经元为例，则有：

偏导数 又称为 误差项（error term，也称为“灵敏度”） ，一般用 表示，例如 是第一层神经元的误差项，其值的大小代表了第一层神经元对于最终总误差的影响大小。

根据第一节的前向计算，我们知道第 层的输入与第 层的输出之间的关系为：

又因为 ，根据链式法则，我们可以得到 为：

由上式我们可以看到，第 层神经元的误差项 是由第 层的误差项乘以第 层的权重，再乘以第 层激活函数的导数（梯度）得到的。这就是误差的反向传播。
现在我们已经计算出了偏导数 、 和 ，则 和 可分别表示为：

下面是基于随机梯度下降更新参数的反向传播算法：

单纯的公式推导看起来有些枯燥，下面我们将实际的数据带入图1所示的神经网络中，完整的计算一遍。

我们依然使用如图5所示的简单的神经网络，其中所有参数的初始值如下：

输入的样本为（假设其真实类标为"1"）：

第一层网络的参数为：

第二层网络的参数为：

第三层网络的参数为：

假设所有的激活函数均为Logistic函数： 。使用均方误差函数作为损失函数：

为了方便求导，我们将损失函数简化为：

我们首先初始化神经网络的参数，计算第一层神经元：

上图中我们计算出了第一层隐藏层的第一个神经元的输入 和输出 ，同理可以计算第二个和第三个神经元的输入和输出：

接下来是第二层隐藏层的计算，首先我们计算第二层的第一个神经元的输入z₄和输出f₄(z₄)：

同样方法可以计算该层的第二个神经元的输入 和输出 ：

最后计算输出层的输入 和输出 ：

首先计算输出层的误差项 ，我们的误差函数为 ，由于该样本的类标为“1”，而预测值为 ，因此误差为 ，输出层的误差项为：

接着计算第二层隐藏层的误差项，根据误差项的计算公式有：

最后是计算第一层隐藏层的误差项：

‘柒’ 什么是演示程序比如要求编写查找算法的演示程序，意思就是编一个程序，可以实现查找算法的功能就行吗

就是demo
一般是个有需要界面的假程序，先做出个样子，让人家知道你能做成什么结果
比如人家要你做一个酒店管理系统，给你一堆要求
你的demo就是一个界面，上面是具体这些要求的实现结果
各种表格，各种录入界面
至于怎么实现的，是后面再说的，里面不需要有真正的功能

你说的查找算法也是这样
有个界面，是查找参数
然后有个结果界面，是查找的结果
至于具体算法，后面再说，现在都弄好了，那还怎么说是演示呢？

‘捌’ 递归算法 汉诺塔 演示

整理分析结果：把第1步中化简问题的条件作为递归 结束条件，将第3步分析得到的算法作为递归算法。
定义函数movedisc( n，fromneedle，toneedle，usingneedle)。将 fromneedle 杆上的 N 个圆盘，借助 usingneedle 杆，移动到 toneedle 杆上。
移动N个圆盘的递归算法描述如下：
movedisc ( n，fromneedle，toneedle，usingneedle )
{ if ( n==1 ) 将 n 号圆盘从 fromneedle 上移到 toneedle;
else {
① movedisc ( n-1，fromneedle，usingneedle，toneedle )
② 将 n 号圆盘从 fromneedle 上移到 toneedle;
③ movedisc ( n-1，usingneedle，toneedle，fromneedle )
}
}

下面是程序
int i=0; /* 移动圆盘数量计数器 */
main( )
{ unsigned n;
scanf ("%d", &n);
movedisc ( n,’a’,’b’,’c’); /* 将A上的N个圆盘借助C将移动到B上 */
printf( "\t Total: %d\n", i );
}
movedisc ( n, fromneedle, toneedle, usingneedle )
unsigned n;
char fromneedle, toneedle, usingneedle;
{ if ( n == 1 )
printf("%2d-(%2d): %c ==> %c\n",++i, n,fromneedle,toneedle);
else {
movedisc ( n-1, fromneedle, usingneedle, toneedle );
printf("%2d-(%2d): %c ==> %c\n",++i, n,fromneedle,toneedle);
movedisc ( n-1, usingneedle, toneedle, fromneedle );
}
}