OPTICS算法及其实现代码
1 什么是OPTICS算法
在前面介绍的DBSCAN算法中，有两个初始参数E（邻域半径）和minPts(E
邻域最小点数)需要用户手动设置输入，并且聚类的类簇结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果，其实这也是大多数其他需要初始化参数聚类算法的弊端。
为了克服DBSCAN算法这一缺点，提出了OPTICS算法（Ordering Points to identify the clustering structure）。OPTICS并不显示的产生结果类簇，而是为聚类分析生成一个增广的簇排序（比如，以可达距离为纵轴，样本点输出次序为横轴的坐标图），这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类，换句话说，从这个排序中可以得到基于任何参数E和minPts的DBSCAN算法的聚类结果。
2 OPTICS两个概念
核心距离：
对象p的核心距离是指是p成为核心对象的最小E’。如果p不是核心对象，那么p的核心距离没有任何意义。
可达距离：
对象q到对象p的可达距离是指p的核心距离和p与q之间欧几里得距离之间的较大值。如果p不是核心对象，p和q之间的可达距离没有意义。
例如：假设邻域半径E=2, minPts=3，存在点
A(2,3),B(2,4),C(1,4),D(1,3),E(2,2),F(3,2)
点A为核心对象，在A的E领域中有点{A,B,C,D,E,F}，其中A的核心距离为E’=1，因为在点A的E’邻域中有点{A,B,D,E}>3;
点F到核心对象点A的可达距离为，因为A到F的欧几里得距离，大于点
A的核心距离1.
3 算法描述
OPTICS算法额外存储了每个对象的核心距离和可达距离。基于OPTICS产生的排序信息来提取类簇。
算法描述如下：
算法：OPTICS
输入：样本集D, 邻域半径E, 给定点在E领域内成为核心对象的最小领域点数MinPts
输出：具有可达距离信息的样本点输出排序
方法：1 创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及其该核心对
象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次
序）；
2 如果所有样本集D中所有点都处理完毕，则算法结束。否则，选择一
个未处理（即
不在结果队列中）且为核心对象的样本点，找到其所有直接密度可达样本点，如
过该样本点不存在于结果队列中，则将其放入有序队列中，并按可达距离排序；
3 如果有序队列为空，则跳至步骤2，否则，从有序队列中取出第一个样本点（即可
达距离最小的样本点）进行拓展，并将取出的样本点保存至结果队列中，如果它不
存在结果队列当中的话。
3.1 判断该拓展点是否是核心对象，如果不是，回到步骤3，否则找到该拓展点所
有的直接密度可达点；
3.2 判断该直接密度可达样本点是否已经存在结果队列，是则不处理，否则下一
步；
3.2 如果有序队列中已经存在该直接密度可达点，如果此时新的可达距离小于旧
的可达距离，则用新可达距离取代旧可达距离，有序队列重新排序；
3.3 如果有序队列中不存在该直接密度可达样本点，则插入该点，并对有序队列
重新排序；
4 算法结束，输出结果队列中的有序样本点。
大家或许会很疑惑，这里不也有输入参数E和MinPts吗？其实这里的E和MinPts只是起到算法辅助作用，也就是说E和MinPts的细微变化并不会影响到样本点的相对输出顺序，这对我们分析聚类结果是没有任何影响。
我们采用与先前DBSCAN相同的样本点集合，
对于样本点
a={2,3};b={2,4};c={1,4};d={1,3};e={2,2};f={3,2};
g={8,7};h={8,6};i={7,7};j={7,6};k={8,5};
l={100,2};//孤立点
m={8,20};n={8,19};o={7,18};p={7,17};q={8,21};
并且使用相同的E=2 MinPts=4时，输出序列为
1->a:1.0
2->e:1.0
3->b:1.0
4->d:1.0
5->c:1.4142135623730951
6->f:1.4142135623730951
7->g:1.4142135623730951
8->j:1.4142135623730951
9->k:1.4142135623730951
10->i:1.4142135623730951
11->h:1.4142135623730951
------
12->n:2.0
13->q:2.0
14->o:2.0
15->m:2.0
如图，按照算法，分三个阶段输出了三波值
{a,e,b,d,c,f} ,{g,j,k,I,h},{n,q,o,m}
这和DBSCAN的类簇结果是一样的。不仅如此，我们通过分析有序图还能直接得到当参数E=1.5,minPts=4时DBSCAN的类簇结果，只要在坐标图中找到Y 值小于1.5的样本点即可，只有两类{a,e,b,d,c,f} ,{g,j,k,I,h},其他点被认为是孤立点，和DBSCAN聚类算法取E=1.5,minPts=4时的结果一致。
所以说，这个OPTICS聚类算法所得的簇排序信息等价于一个广泛的参数设置所获得的基于密度的聚类结果。
具体实现算法如下：
package com.optics;
public class DataPoint {
private String name; // 样本点名
private double dimensioin[]; // 样本点的维度
private double coreDistance; //核心距离，如果该点不是核心对象，则距离
private double reachableDistance; //可达距离
public DataPoint(){
}
public DataPoint(DataPoint e){
https://www.wendangku.net/doc/ef704938.html,=https://www.wendangku.net/doc/ef704938.html,;
this.dimensioin=e.dimensioin;
this.coreDistance=e.coreDistance;
this.reachableDistance=e.reachableDistance;
}
public DataPoint(double dimensioin[],String name){
https://www.wendangku.net/doc/ef704938.html,=name;
this.dimensioin=dimensioin;
this.coreDistance=-1;
this.reachableDistance=-1;
}
public String getName() {
return name;
}
public void setName(String name) {
https://www.wendangku.net/doc/ef704938.html, = name;
}
public double[] getDimensioin() {
return dimensioin;
}
public void setDimensioin(double[] dimensioin) {
this.dimensioin = dimensioin;
}
public double getCoreDistance() {
return coreDistance;
}
public void setCoreDistance(double coreDistance) {
this.coreDistance = coreDistance;
}
public double getReachableDistance() {
return reachableDistance;
}
public void setReachableDistance(double reachableDistance) { this.reachableDistance = reachableDistance;
}
}
package com.optics;
import java.util.ArrayList;
import java.util.Collections;
import https://www.wendangku.net/doc/ef704938.html,parator;
import java.util.List;
public class ClusterAnalysis {
class ComparatorDp implements Comparator
public int compare(DataPoint arg0, DataPoint arg1) {
double
temp=arg0.getReachableDistance()-arg1.getReachableDistance();
int a = 0;
if (temp < 0) {
a = -1;
} else {
a = 1;
}
return a;
}
}
public List
double radius, int ObjectNum) {
List
List
int total = 0;
while (total < dataPoints.size()) {
if (isContainedInList(dataPoints.get(total), dpList) == -1 ) {
List
dataPoints, radius, ObjectNum);
if(tmpDpList != null && tmpDpList.size() > 0){
DataPoint newDataPoint=new
DataPoint(dataPoints.get(total));
dpQue.add(newDataPoint);
}
}
while (!dpQue.isEmpty()) {
DataPoint tempDpfromQ = dpQue.remove(0);
DataPoint newDataPoint=new DataPoint(tempDpfromQ);
dpList.add(newDataPoint);
List
isKeyAndReturnObjects(tempDpfromQ,
dataPoints, radius, ObjectNum);
System.out.println(newDataPoint.getName()+":"+newDataPoint.getReachable Distance());
if (tempDpList != null && tempDpList.size() > 0) {
for (int i = 0; i < tempDpList.size(); i++) {
DataPoint tempDpfromList = tempDpList.get(i);
int indexInList = isContainedInList(tempDpfromList,
dpList);
int indexInQ = isContainedInList(tempDpfromList, dpQue);
if (indexInList == -1) {
if (indexInQ > -1) {
int index = -1;
for (DataPoint dataPoint : dpQue) {
index++;
if (index == indexInQ) {
if
(dataPoint.getReachableDistance() > tempDpfromList
.getReachableDistance ()) {
dataPoint
.setReachableDist ance(tempDpfromList
.getReach ableDistance());
}
}
}
} else {
dpQue.add(new
DataPoint(tempDpfromList));
}
}
}
// TODO：对Q进行重新排序
Collections.sort(dpQue, new ComparatorDp());
}
}
System.out.println("------");
total++;
}
return dpList;
}
public void displayDataPoints(List
for(DataPoint dp: dps){
System.out.println(dp.getName()+":"+dp.getReachableDistance());
}
}
private int isContainedInList(DataPoint dp, List
for (DataPoint dataPoint : dpList) {
index++;
if (dataPoint.getName().equals(dp.getName())) {
return index;
}
}
return -1;
}
private List
dataPoint,List
List
double coreDistance; //核心距离
for (int i = 0; i < dataPoints.size(); i++) {
DataPoint dp = dataPoints.get(i);
double distance = getDistance(dataPoint, dp);
if (distance <= radius) {
distances.add(distance);
arrivableObjects.add(dp);
}
}
if(arrivableObjects.size()>=ObjectNum){
List
Collections.sort(distances);
coreDistance=distances.get(ObjectNum-1);
for(int j=0;j if (coreDistance > newDistances.get(j)) { if(newDistances.get(j)==0){ dataPoint.setReachableDistance(coreDistance); } arrivableObjects.get(j).setReachableDistance(coreDistance); }else{ arrivableObjects.get(j).setReachableDistance(newDistances.get(j)); } } return arrivableObjects; } return null; } private double getDistance(DataPoint dp1,DataPoint dp2){ double distance=0.0; double[] dim1=dp1.getDimensioin(); double[] dim2=dp2.getDimensioin(); if(dim1.length==dim2.length){ for(int i=0;i double temp=Math.pow((dim1[i]-dim2[i]), 2); distance=distance+temp; } distance=Math.pow(distance, 0.5); return distance; } return distance; } public static void main(String[] args){ ArrayList double[] a={2,3}; double[] b={2,4}; double[] c={1,4}; double[] d={1,3}; double[] e={2,2}; double[] f={3,2}; double[] g={8,7}; double[] h={8,6}; double[] i={7,7}; double[] j={7,6}; double[] k={8,5}; double[] l={100,2};//孤立点 double[] m={8,20}; double[] n={8,19}; double[] o={7,18}; double[] p={7,17}; double[] q={8,21}; dpoints.add(new DataPoint(a,"a")); dpoints.add(new DataPoint(b,"b")); dpoints.add(new DataPoint(c,"c")); dpoints.add(new DataPoint(d,"d")); dpoints.add(new DataPoint(e,"e")); dpoints.add(new DataPoint(f,"f")); dpoints.add(new DataPoint(g,"g")); dpoints.add(new DataPoint(h,"h")); dpoints.add(new DataPoint(i,"i")); dpoints.add(new DataPoint(j,"j")); dpoints.add(new DataPoint(k,"k")); dpoints.add(new DataPoint(l,"l")); dpoints.add(new DataPoint(m,"m")); dpoints.add(new DataPoint(n,"n")); dpoints.add(new DataPoint(o,"o")); dpoints.add(new DataPoint(p,"p")); dpoints.add(new DataPoint(q,"q")); ClusterAnalysis ca=new ClusterAnalysis(); List ca.displayDataPoints(dps); } } md5加密算法c实现 七分注释收藏 经常到csdn来是查资料，每次都会有所收获。总是看别人的感觉很不好意思，于是决定自己也写一点东西贡献出来。于是就有了这篇md5七分注释。希望对用到的朋友有所帮助。 记得当初自己刚开始学习md5的时候，从网上搜了很多关于算法的原理和文字性的描述的东西，但是看了很久一直没有搞懂，搜c的源代码又很少。直到后来学习rsa算法的时候，从网上下了1991年的欧洲的什么组织写的关于rsa、des、md5算法的c源代码（各部分代码混在一块的，比如rsa用到的随机大素数就是用机器的随机时间的md5哈希值获得的）。我才彻底把md5弄明白了。这里的代码就是我从那里面分离出来的，代码的效率和可重用性都是很高的。整理了一下希望对需要的朋友能够有帮助。 md5的介绍的文章网上很多，关于md5的来历，用途什么的这里就不再介绍了。这里主要介绍代码。代码明白了就什么都明白了。 //////////////////////////////////////////////////////////////////// /* md5.h */ #ifndef _MD5_H_ #define _MD5_H_ #define R_memset(x, y, z) memset(x, y, z) #define R_memcpy(x, y, z) memcpy(x, y, z) #define R_memcmp(x, y, z) memcmp(x, y, z) typedef unsigned long UINT4; typedef unsigned char *POINTER; /* MD5 context. */ typedef struct { /* state (ABCD) */ /*四个32bits数，用于存放最终计算得到的消息摘要。当消息长度〉512bits时，也用于存放每个512bits的中间结果*/ UINT4 state[4]; /* number of bits, modulo 2^64 (lsb first) */ /*存储原始信息的bits数长度,不包括填充的bits，最长为2^64 bits，因为2^64是一个64位数的最大值*/ UINT4 count[2]; /* input buffer */ /*存放输入的信息的缓冲区，512bits*/ unsigned char buffer[64]; 排序算法汇总 第1节排序及其基本概念 一、基本概念 1．什么是排序 排序是数据处理中经常使用的一种重要运算。 设文件由n个记录{R1，R2，……，Rn}组成，n个记录对应的关键字集合为{K1，K2，……，Kn}。所谓排序就是将这n个记录按关键字大小递增或递减重新排列。b5E2RGbCAP 2．稳定性 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。 如果文件中关键字相同的记录经过某种排序方法进行排序之后，仍能保持它们在排序之前的相对次序，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。p1EanqFDPw 3．排序的方式 由于文件大小不同使排序过程中涉及的存储器不同，可将排序分成内部排序和外部排序两类。整个排序过程都在内存进行的排序，称为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。DXDiTa9E3d 内排序适用于记录个数不是很多的小文件，而外排序则适用于记录个数太多，不能一次性放人内存的大文件。 内排序是排序的基础，本讲主要介绍各种内部排序的方法。 按策略划分内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。 二、排序算法分析 1．排序算法的基本操作 几乎所有的排序都有两个基本的操作： <1）关键字大小的比较。 <2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。RTCrpUDGiT 为了简化描述，在下面的讲解中，我们只考虑记录的关键字，则其存储结构也简化为数组或链表。并约定排序结果为递增。5PCzVD7HxA 2．排序算法性能评价 排序的算法很多，不同的算法有不同的优缺点，没有哪种算法在任何情况下都是最好的。评价一种排序算法好坏的标准主要有两条：jLBHrnAILg <1）执行时间和所需的辅助空间，即时间复杂度和空间复杂度； <2）算法本身的复杂程度，比如算法是否易读、是否易于实现。 第2节插入排序 插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的记录集中，使记录依然有序，直到所有待排序记录全部插入完成。xHAQX74J0X 一、直接插入排序 1．直接插入排序的思想 一、冒泡排序 冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 代码实现如下： 二、插入排序 插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。 直接插入排序具体算法描述如下： 1. 从第一个元素开始，该元素可以认为已经被排序 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到下一位置中 6. 重复步骤2 伪码描述如下： 代码实现如下： 三、归并排序 归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为n的有序表，排序结束。 归并操作的工作原理如下： 1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 2、设定两个指针，最初位置分别为两个已经排序序列的起始位置 3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 4、重复步骤3直到某一指针达到序列尾 5、将另一序列剩下的所有元素直接复制到合并序列尾 代码实现如下： MD5算法及源代码 分类：计算机密码 //获得MD5的二个数组和一个buffer并初始化 MD5 *GetMD5(); //初始化MD5的二个数据和一个buffer void MD5Init (MD5 *context); //用于计算MD5值的函数 void MD5Update (MD5 *context, unsigned char *input, unsigned int inputLen); //输出结果 void MD5Final (MD5 *context, unsigned char digest[16]); //对input数据做一次完整的MD5运算 void MD5Out (MD5 *md5, unsigned char *input, unsigned int inputLen, unsigned char out[16]); //计算一个文件的MD5值 int 计算一个文件的MD5值(TCHAR* 文件路径, unsigned char md5值[16]) { MD5 context; int 缓冲区长度 = 1024, 读取到的字节数; unsigned char *缓冲区 = new unsigned char[缓冲区长度]; FILE *文件指针 = fopen(文件路径, "rb"); if(文件指针 == NULL) return 1; MD5Init(&context); while ( (读取到的字节数 = fread ( 缓冲区, 1, 缓冲区长度, 文件指针 )) ! =EOF) { MD5Update (&context, 缓冲区, 读取到的字节数); //判断是否为已经读到文件尾 if ( 读取到的字节数 < 缓冲区长度 ) break; } MD5Final (&context, md5值); free ( 缓冲区 ); return 0; } /** **MD5.h **/ typedef struct { unsigned long state[4]; /* state (ABCD) */ unsigned long count[2]; /* number of bits, modulo 2^64 */ 一、设计思想 插入排序：首先，我们定义我们需要排序的数组，得到数组的长度。如果数组只有一个数字，那么我们直接认为它已经是排好序的，就不需要再进行调整，直接就得到了我们的结果。否则，我们从数组中的第二个元素开始遍历。然后，启动主索引，我们用curr当做我们遍历的主索引，每次主索引的开始，我们都使得要插入的位置（insertIndex）等于-1，即我们认为主索引之前的元素没有比主索引指向的元素值大的元素，那么自然主索引位置的元素不需要挪动位置。然后，开始副索引，副索引遍历所有主索引之前的排好的元素，当发现主索引之前的某个元素比主索引指向的元素的值大时，我们就将要插入的位置（insertIndex）记为第一个比主索引指向元素的位置，跳出副索引；否则，等待副索引自然完成。副索引遍历结束后，我们判断当前要插入的位置（insertIndex）是否等于-1，如果等于-1，说明主索引之前元素的值没有一个比主索引指向的元素的值大，那么主索引位置的元素不要挪动位置，回到主索引，主索引向后走一位，进行下一次主索引的遍历；否则，说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大，那么，我们记录当前主索引指向的元素的值，然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位，这里注意，要从后向前一位一位挪，否则，会使得数组成为一串相同的数字。最后，将记录下的当前索引指向的元素的值放在要插入的位置（insertIndex）处，进行下一次主索引的遍历。继续上面的工作，最终我们就可以得到我们的排序结果。插入排序的特点在于，我们每次遍历，主索引之前的元素都是已经排好序的，我们找到比主索引指向元素的值大的第一个元素的位置，然后将主索引指向位置的元素插入到该位置，将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法，使得挪动的次数相对较多，如果对于排序数据量较大，挪动成本较高的情况时，这种排序算法显然成本较高，时间复杂度相对较差，是初等通用排序算法中的一种。 选择排序：选择排序相对插入排序，是插入排序的一个优化，优化的前提是我们认为数据是比较大的，挪动数据的代价比数据比较的代价大很多，所以我们选择排序是追求少挪动，以比较次数换取挪动次数。首先，我们定义我们需要排序的数组，得到数组的长度，定义一个结果数组，用来存放排好序的数组，定义一个最小值，定义一个最小值的位置。然后，进入我们的遍历，每次进入遍历的时候我们都使得当前的最小值为9999，即认为每次最小值都是最大的数，用来进行和其他元素比较得到最小值，每次认为最小值的位置都是0，用来重新记录最小值的位置。然后，进入第二层循环，进行数值的比较，如果数组中的某个元素的值比最小值小，那么将当前的最小值设为元素的值，然后记录下来元素的位置，这样，当跳出循环体的时候，我们会得到要排序数组中的最小值，然后将最小值位置的数值设置为9999，即我们得到了最小值之后，就让数组中的这个数成为最大值，然后将结果数组result[]第主索引值位置上的元素赋值为最小值，进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于，我们挪动元素的次数很少，只是每次对要排序的数组进行整体遍历，找到其中的最小的元素，然后将改元素的值放到一个新的结果数组中去，这样大大减少了挪动的次序，即我们要排序的数组有多少元素，我们就挪动多少次，而因为每次都要对数组的所有元素进行遍历，那么比较的次数就比较多，达到了n2次，所以，我们使用选择排序的前提是，认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序，他的比较次数大于插入排序的次数，而挪动次数就很少，元素有多少个，挪动次数就是多少个。 希尔排序：首先，我们定义一个要排序的数组，然后定义一个步长的数组，该步长数组是由一组特定的数字组成的，步长数组具体得到过程我们不去考虑，是由科学家经过很长时间计算得到的，已经根据时间复杂度的要求，得到了最适合希尔排序的一组步长值以及计算 function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta ,Rho,Q) %%===================================================== ==================== %% ACATSP.m %% Ant Colony Algorithm for Traveling Salesman Problem %% ChengAihua,PLA Information Engineering University,ZhengZhou,China %% Email:aihuacheng@https://www.wendangku.net/doc/ef704938.html, %% All rights reserved %%------------------------------------------------------------------------- %% 主要符号说明 %% C n个城市的坐标，n×4的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%===================================================== ==================== %%第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=max( ((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5,min(abs(C(i,3)-C(j,3)),144- abs(C(i,3)-C(j,3))) );%计算城市间距离 else D(i,j)=eps; end D(j,i)=D(i,j); end end Eta=1./D;%Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n);%Tau为信息素矩阵 Tabu=zeros(m,n);%存储并记录路径的生成 NC=1;%迭代计数器 R_best=zeros(NC_max,n);%各代最佳路线 实验三 MD5算法的设计与实现 一、实验目的： 设计并实现MD5算法，从而进一步加深对数据完整性保证和散列函数的理解。 二、实验要求： 1、产生任意电子文档（包括文本和二进制）的128位信息摘要。 2、根据信息摘要验证该电子文档是否被更改过。 三、实验内容: 1、MD5算法简介: Message Digest Algorithm MD5（中文名为消息摘要算法第五版）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。1991年，Rivest开发出技术上更为趋近成熟的md5算法。它在MD4的基础上增加了"安全-带子"（safety-belts）的概念。虽然MD5比MD4复杂度大一些，但却更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中，信息-摘要的大小和填充的必要条件与MD4完全相同。Den boer和Bosselaers曾发现MD5算法中的假冲突（pseudo-collisions），但除此之外就没有其他被发现的加密后结果了。对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。 2. MD5算法逻辑处理操作包括以下几步： 步骤一：附加填充比特。对报文填充使报文的长度（比特数）与448模512同余。即填充比特使长度为512的整数倍减去64。例如，如果报文是448比特长，那么将填充512比特形成960比特的报文。填充比特串的最高位为1，其余各位均为0。 步骤二：附加长度值。将用64比特表示的初始报文（填充前）的位长度附加在步骤一的结果后（低位字节优先）。如果初始长度大于264，仅使用该长度的低64比特。这样，该域所包含的长度值为初始报文长度模264的值。这两步的结果将产生一个长度为512整数倍比特的报文。经扩展的报文表示成512比特的分组序列列Y1、Y2、Y3……Y（n-1），因此扩展的报文长度等于L乘512比特。与之等价的是，该结果也等于字长为16比特或32比特的整数倍，如果让[]10?NML表示扩展报文包含的字数，其中N是16的倍数，则N等于L 乘512。下图为使用MD5产生报文摘要的过程： 冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 #include 软件开发报价的计算方法 1．软件开发价格估算方法软件开发价格与工作量、商务成本、国家税收和企业利润等项有关。为了便于计算，给出一个计算公式： 软件开发价格＝开发工作量× 开发费用／人·月 1.1 开发工作量软件开发工作量与估算工作量经验值、风险系数和复用系数等项有关：软件开发工作量＝估算工作量经验值× 风险系数× 复用系数 1.1.1 估算工作量经验值（以A 来表示）软什开发工作量的计算，曾有人提出以源代码行或功能点来计算，这些方法实施起来均有不少难度。目前国际上仍旧按以往经验的方式加以计算，国内各软件企业也是采用经验的方式加以估算工作量。 1.1.2 风险系数（以σ 来表示）估算工作量经验值亦会存在较大风险，造成软件危机的因素很多，这也是一个方面的因素。特别当软件企业对该信息工程项目的业务领域不熟悉或不太熟悉，而且用户又无法或不能完整明白地表达他们的真实的需求，从而造成软件企业需要不断地完善需求获取，修改设计等各项工作。因此： l ≤风险系数≤1.5 根据我们对软件企业的了解，超过估算工作量经验值的一半，已是不可接受，所以我们确定“ 1.5 ”为极限值。当然这既要看企业的能力，也要看用户能接受的程度。 1.1.3 复用系数（以τ 来表示）估算工作量经验值是软件企业承担一般项目来估算的，但如果软件企业已经采用“基于构件的开发方法” ，并己建立起能够复用的构件库（核心资产库），或者已有一些软件产品，仅作二次开发，从而使软件开发工作量减少。因此： 0.25 ≤复用系数≤1 根据国内外软件企业在实施基于构件开发方法（软件产品线）的经验数据，提高工作效率达到25%（最高值）。 1.2 开发费用／人·月软件企业的商务成本、国家税收、企业利润、管理成本和质量成本。均可摊分到各个软件开发人员头上。 开发费用／人·月＝（P＋Q＋R）× S× τ 1.2.1 P （人头费）人头费主要是员工的工资、奖金和国家规定的各项按人计算的费用。其总量在软件企业中的商务成本占70%－80%。 P ＝B × 1.476 国家规定的公积金7%，医疗保险金12%，养老金22%，失业金2%（即通常所说的四金），另外还有按工资总额计征的工伤保证金0.5%，生育保证金0.5%，残疾基金 1.6%，工会基金2%，累计为47.6%。 B 为平均工资，即企业支付给员工的工资、奖金、物质奖励等多项总和，除以企业员工数，分摊到每个月。 1.2.2 Q （办公费）办公费包括企业办公房屋租赁费和物业管理费、通信费、办公消耗品、水电空调费、设备折旧、差旅费，另外也包括企业对员工的在职培训所支付的费用，其总量在软件企业中的商务成本占20%－30%。 Q ＝B／3 此处办公费用按商务成本的25%计算。 1.2.3 R （国家税收和企业利润）由于国家实施发展软件产业的优惠政策，故不单独列出计算，但软件企业仍需承担缴纳国家税收的义务，可一并与企业利润一起考虑。另外，软件企业的员工不可能全年满负荷地工作，即使一年十二个月都安排工作，但也需抽出时间进行在职培训和提职的岗前培训。据我们的了解，软件企业的员工一 MD5加密算法原理 MD5的全称是Message-Digest Algorithm 5（信息-摘要算法），在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest开发出来，经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密匙前被"压缩"成一种保密的格式（就是把一个任意长度的字节串变换成一定长的大整数）。不管是MD2、MD4还是MD5，它们都需要获得一个随机长度的信息并产生一个128位的信息摘要。虽然这些算法的结构或多或少有些相似，但MD2的设计与MD4和MD5完全不同，那是因为MD2是为8位机器做过设计优化的，而MD4和MD5却是面向32位的电脑。这三个算法的描述和C语言源代码在Internet RFCs 1321中有详细的描述 （https://www.wendangku.net/doc/ef704938.html,/rfc/rfc1321.txt），这是一份最权威的文档，由Ronald L. Rivest 在1992年8月向IEFT提交。. . Van Oorschot和Wiener曾经考虑过一个在散列中暴力搜寻冲突的函数（Brute-Force Hash Function），而且他们猜测一个被设计专门用来搜索MD5冲突的机器（这台机器在1994年的制造成本大约是一百万美元）可以平均每24天就找到一个冲突。但单从1991年到2001年这10年间，竟没有出现替代MD5算法的MD6或被叫做其他什么名字的新算法这一点，我们就可以看出这个瑕疵并没有太多的影响MD5的安全性。上面所有这些都不足以成为MD5 的在实际应用中的问题。并且，由于MD5算法的使用不需要支付任何版权费用的，所以在一般的情况下（非绝密应用领域。但即便是应用在绝密领域内，MD5也不失为一种非常优秀的中间技术），MD5怎么都应该算得上是非常安全的了。 算法的应用 MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。比如，在UNIX下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如： MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461 这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。如果在以后传播这个文件的过程中，无论文件的内容发生了任何形式的改变（包括人为修改或者下载过程中线路不稳定引起的传输错误等），只要你对这个文件重新计算MD5时就会发现信息摘要不相同，由此可以确定你得到的只是一个不正确的文件。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的"抵赖"，这就是所谓的数字签名应用。 MD5还广泛用于加密和解密技术上。比如在UNIX系统中用户的密码就是以MD5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成MD5值，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。 排序算法题目及其代码 1、明明的随机数（Noip2006） 【问题描述】 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。 【输入文件】 输入文件random.in 有2行， 第1行为1个正整数，表示所生成的随机数的个数：N 第2行有N个用空格隔开的正整数，为所产生的随机数。 【输出文件】 输出文件random.out 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。 【输入样例】 10 20 40 32 67 40 20 89 300 400 15 【输出样例】 8 15 20 32 40 67 89 300 400 【参考程序】 var n,s:byte; i,min,max,x:word; b:array[1..1000]of boolean; begin assign(input,'random.in');reset(input); assign(output,'random.out');rewrite(output); readln(n); fillchar(b,sizeof(b),false); min:=1000;max:=0;s:=0; for i:=1 to n do begin read(x); b[x]:=true; if x 先新建一个主程序M文件ACATSP.m 代码如下: function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q) %%================================================== ======================= %% 主要符号说明 %% C n个城市的坐标，n×2的矩阵 %% NC_max 蚁群算法MATLAB程序最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 表示蚁群算法MATLAB程序信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%================================================== ======================= %% 蚁群算法MATLAB程序第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5; else D(i,j)=eps; % i = j 时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示 end D(j,i)=D(i,j); %对称矩阵 end end Eta=1./D; %Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n); %Tau为信息素矩阵 Tabu=zeros(m,n); %存储并记录路径的生成 3.4 大林（Dahlin）算法 前面介绍的最少拍无纹波系统的数字控制器的设计方法只适合 于某些随动系统，对系统输出的超调量有严格限制的控制系统它并不理想。在一些实际工程中，经常遇到纯滞后调节系统，它们的滞后时间比较长。对于这样的系统，往往允许系统存在适当的超调量，以尽可能地缩短调节时间。人们更感兴趣的是要求系统没有超调量或只有很小超调量，而调节时间则允许在较多的采样周期内结束。也就是说，超调是主要设计指标。对于这样的系统，用一般的随动系统设计方法是不行的，用PID算法效果也欠佳。 针对这一要求，IBM公司的大林(Dahlin)在1968年提出了一种针对工业生产过程中含有纯滞后对象的控制算法。其目标就是使整个闭环系统的传递函数相当于一个带有纯滞后的一阶惯性环节。该算法具有良好的控制效果。 3.4.1 大林算法中D(z)的基本形式 设被控对象为带有纯滞后的一阶惯性环节或二阶惯性环节，其传递函数分别为： （3-4-1） （3-4-2） 其中为被控对象的时间常数，为被控对象的纯延迟时间，为了简化，设其为采样周期的整数倍，即N为正整数。 由于大林算法的设计目标是使整个闭环系统的传递函数相当于 一个带有纯滞后的一阶惯性环节，即 ，其中 由于一般控制对象均与一个零阶保持器相串联，所以相应的整个闭环系统的脉冲传递函数是 （3-4-3）于是数字控制器的脉冲传递函数为 （3-4-4）D(z)可由计算机程序实现。由上式可知，它与被控对象有关。下面分别对一阶或二阶纯滞后环节进行讨论。 3.4.2 一阶惯性环节的大林算法的D(z)基本形式 当被控对象是带有纯滞后的一阶惯性环节时，由式（3-4-1）的传递函数可知，其脉冲传递函数为 将此式代入（3-4-4），可得 //以下为md5计算程序源代码，可以复制到自己的程序中使用，使用方法见最后的main函数 //经测试，绝对可以使用 ////////////////////////////////////////////////////// #include 排序算法的分析比较 学生姓名: 学号： 专业： 班级： 一、题目概述 排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果排序中依据的不同原则对内部排序方法进行分类，则大致可分为直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序、堆排序等六类排序算法。 本文是对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序、堆排序这几种内部排序算法进行比较，用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。最后用图表数据汇总，以便对这些内部排序算法进行性能分析。 二、数据定义 输入数据： 由于大多数排序算法的时间开销主要是关键字之间的比较和记录的移动，算法的执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。所以对于输入数据，我们采用由用户输入记录的个数（以关键字的数目分别为20，100，500为例），测试数据由随机数产生器生成。 输出数据： 产生的随机数分别用直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序这些排序方法进行排序，输出关键字的比较次数和移动次数。 各种排序的基本原理及时间复杂度分析 1、直接插入排序（InsertSort） 1.1、基本原理： 假设待排序的n个记录{R0，R1，…，Rn}顺序存放在数组中，直接插入法在插入记录Ri(i=1，2，…，n-1)时，记录被划分为两个区间[R0,Ri-1]和[Ri+1,Rn-1],其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码Ki与Ki-1Ki-2，…，K0依次比较，找出应该插入的位置，将记录Ri插，然后将剩下的i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i-1趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 1.2、时间复杂度分析： 直接插入排序算法必须进行n-1趟。最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是O(n)。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为O(n2)。 10大算法R实现 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继 承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过 程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它 是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面 常见排序算法的实现(一)→插入排序 插入排序是最简单最直观的排序算法了，它的依据是：遍历到第N个元素的时候前面的N-1个元素已经是排序好的了，那么就查找前面的N-1个元素把这第N 个元素放在合适的位置，如此下去直到遍历完序列的元素为止。 算法的复杂度也是简单的，排序第一个需要1的复杂度，排序第二个需要2的复杂度，因此整个的复杂度就是 1 + 2 + 3 + …… + N = O（N ^ 2）的复杂度。[详细内容] void insert_sort(int s[],int n) { int i,j,temp; for(i=1;i function [y,val]=QACStic load att48 att48; MAXIT=300; % 最大循环次数 NC=48; % 城市个数 tao=ones(48,48);% 初始时刻各边上的信息最为1 rho=0.2; % 挥发系数 alpha=1; beta=2; Q=100; mant=20; % 蚂蚁数量 iter=0; % 记录迭代次数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2); end end bestroute=zeros(1,48); % 用来记录最优路径 routelength=inf; % 用来记录当前找到的最优路径长度 % for i=1:mant % 确定各蚂蚁初始的位置 % end for ite=1:MAXIT for ka=1:mant %考查第K只蚂蚁 deltatao=zeros(48,48); % 第K只蚂蚁移动前各边上的信息增量为零 [routek,lengthk]=travel(distance,tao,alpha,beta); if lengthkMD5加密算法-c源代码
排序算法汇总(图解加程序代码)
排序算法
MD5算法及源代码
几种排序算法的分析与比较--C语言
蚁群算法TSP问题matlab源代码
MD5算法的设计与实现
c语言排序算法总结(主要是代码实现)
软件开发报价和报价材料模板的计算方法
MD5加密算法原理
排序算法题目及其代码
蚁群算法matlab程序代码
大林控制算法与其软件实现
md5计算程序源代码
数据结构排序算法的分析和比较(包涵源代码)
10大算法R实现
各个排序算法及其代码
蚁群算法MATLAB代码