算法

AES算法本质上是一种对称分组密码体制,采用代替/置换网络,每轮由三层组成:线性混合层确保多轮之上的高度扩散,非线性层由16个S盒并置起到混淆的作用,密钥加密层将子密钥异或到中间状态。AES是一个迭代分组密码,其分组长度和密钥长度都是可变的,只是为了满足AES的要求才限定处理的分组大小为128位,而密钥长度为128位、192位或256位,相应的迭代轮数N,为10轮、12轮、14轮。AES汇聚了安全 […]

DES(Data Encryption Standard)算法于1977年得到美国政府的正式许可,是一种用56位密钥来加密64位数据的方法。 DES是一种分组密码,明文、密文和密钥的分组长度都是64位,并且都是面向二进制的密码算法。DES处理的明文分组长度为64位,密文分组长度也是64位,使用的密钥长度为56位(实现上函数要求一个64位的密钥作为输入,但其中用到的只有56位,另外8位可以用作奇偶校 […]

题目: 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 基本思路: 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是: f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[ […]

刚刚闲的无聊,不知怎么突然就点到了以前参加ACM时刷题的网站http://poj.org/,恰好发现以前的账号密码保存在浏览器就直接点进去了。如下: 这些题,大部分是在暑假集训的时候刷的,那时候每天早上7、8的样子一起去机房,然后中午吃个饭到下午5点多回宿舍,那个时候真的好热,因为白天集训的地方有空调,所以大部分时间都是留在机房的。每天的学习任务就是学习各种算法,然后刷题,有时周末的时候会组织一些 […]

一、插入排序 算法思想:  利用顺序查找实现“在 R[1..i-1]中查找 R[i]的插入位置”的插入排序。 算法描述: 一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下: 1.从第一个元素开始,该元素可以认为已经被排序 2.取出下一个元素,在已经排序的元素序列中从后向前扫描 3.如果该元素(已排序)大于新元素,将该元素移到下一位置 4.重复步骤3,直到找到已排序的元素小于或 […]

哈希表的概念:   哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。 哈希函数的构造方法: 常见的构造哈希函数的方法有:直接定址法、数字分析法、平均取中法、折叠法、除留余数法、随机数法。 1.直接定址法 取关键字 […]

最短路径:从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径。 1.单源点到其余各顶点的最短路径 给定带权有向图G和源点v,求从v到G中其余各顶点的最短路径。 迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短路径的算法。 Dijkstra算法: 基本思想:这个算法的过程有比prim算法的过程稍微多一点点步骤,但是思想确实巧妙的,也是贪心原理,它的目的 […]

一、拓扑排序 什么是拓扑排序?简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。 回顾离散数学中关于偏序和全序的定义: 若集合X上的关系R是自反的,反对称的和传递的,则称R是集合X上的偏序关系。 设R是集合X上的偏序,如果对每个x,y∈X必有xRy或yRx,则称R是集合X上的全序关系。 直观地看,偏序指集合中仅有部分成员之间可比较,而全序指集合中全体成员之间均可比较下 […]

一、最小生成树的概念 生成树:所有顶点均由边连接在一起,但不存在回路的图叫该图的生成树。 一个图可以有许多棵不同的生成树。 所有生成树具有以下共同特点: 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图   最小生成树:生成树的每条边上的权值之和最小。 构成最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简称为MST的性质:假设N=(V,{E})是一个连通图, […]

广度优先搜索(Breadth-First-Search)和深度优先搜索(Deep-First-Search)是搜索策略中最经常用到的两种方法,特别常用于图的搜索.其中有很多的算法都用到了这两种思想,比如:Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。 一、DFS算法 DFS的思想: 顾名思义,深度优先搜索所遵循的策略就是尽可能“深”的在图中进行搜索,对于 […]