精华内容
下载资源
问答
  • 格式保持加密——FF1算法

    万次阅读 2018-01-06 15:26:10
    使用AES算法实现以下格式保持加密。 0、字符表:大写英文、小写英文字母、0-9、“-”和“*” 1、功能:加密如下格式文本 abcd-efgh*23,输出保持此格式的密文(比如输出 edfa-daxm*89),并可以解密。 2、可直接...

    记大三一次计算机安全学作业

    使用AES算法实现以下格式保持加密。

    0、字符表:大写英文、小写英文字母、0-9、“-”和“*”

    1、功能:加密如下格式文本 abcd-efgh*23,输出保持此格式的密文(比如输出 edfa-daxm*89),并可以解密。

    2、可直接使用官方提供的AES代码。

    3、输入输出可以是文本文件,也可以命令行输入、屏幕输出。

    4、秘钥可以固定写在程序中,也可以是文本文件保存的秘钥。

    5、C/C++语言实现。

    6、需要提交实验报告,说明文本编码、解码的过程。

    作业分析

    • 字符表包括大小写英文字母,数字和两个特殊符号(‘*’和’-‘)
    • 作业要求加密之后英文字母对应英文字母(或者更细致地,大写对大写,小写对小写),数字对数字,且特殊符号不变
    • 在实现格式保持加密之前,要明白FF1(此处链接不是随便搞的,真的很清晰地介绍了FF1和FF3)是在一个字符集中加密,如果把字符表的内容编码成为一个字符集,那就做不到第二点的对应关系了。也就是说,单纯地运用FF1算法,可能会加密出英文字母对应数字或特殊符号(‘*’,’-‘)。
    • 为解决上述问题(冥思苦想)只能把字符集拆开,将输入的明文用上述特殊符号分割成为多组明文块,然后用不同的字符集分别进行加密。其中,我对于字符集的划分:英文字母、数字。
    • 最后一点就是用的AES加密算法了,我用的是openssl库实现的AES。

    BUG

    • 代码的BUG:因为从0(对应于两个字符集中的’A’和0)开始编码,而ASCII码表的0对用于\0,所以会将输入加密的字符串截断导致不能正确加密。所以输入的明文中不能包含A和0。
    • BUG的解决方法:不用ASCII码字符集,自己定义字符集

    具体编码

           A,B,C,,Y,Z,   a,  b,  c ,,  y, z>0,1,2,,24,25,26,27,28,,50,51
           0,1,2,,9>0,1,2,,9

    代码

    给两个相当给力的链接
    参考
    FF1样例

    展开全文
  • 基_2FF并行算法及实现

    2009-06-13 22:21:22
    基_2FF并行算法及实现 基_2FF并行算法及实现
  • fpe - 在Go中实现NIST批准的格式保存加密(FPE)FF1FF3算法
  • 最大流问题之FF算法与EK算法

    千次阅读 2019-01-30 19:32:26
    目录 问题描述: EK算法: 算法描述: 伪代码: ...1推2: ...FF算法缺陷分析: 问题描述: G=(V,E)是一个有向图,其中每条边(u,v)有一个非负的容量值c(u,v),而且如果E中包含一条边...

    目录

    问题描述:

    EK算法:

    算法描述:

    伪代码:

    例子:

    控制台对应输出为:

    关键定理证明:

    最大流最小割定理:

    1推2:

    2推3:

    3推1:

    时间复杂度分析

    分析

    关键边定义:

    时间复杂度计算:

    FF算法:

    FF算法介绍

    FF算法缺陷分析:


    问题描述:

    G=(V,E)是一个有向图,其中每条边(u,v)有一个非负的容量值c(u,v),而且如果E中包含一条边(u,v),那么图中就不存在它的反向边。在流网络中有两个特殊的结点,源结点s和汇点t,源结点s只会流出不会流进,汇点只会流进不会流出,我们要求的就是从源结点流到汇结点的路径的值之和的最大值

    EK算法:

    算法描述:

    每次从残留网络中找出一条从源结点到汇结点的最短路径,流选为路径中的残存容量,依据流更新残存网络(将每条边的残存容量改为当前容量减去流的大小,并添加对应的反向边,边的容量为流的大小)

    重复选最短路径,更新残存网络,直到没有最短路径为止

    此时的流累加和即为最大流

     

    由于每次要找的是最短路径,所以需要用BFS找路径

    伪代码

    例子:

    初始图:

    第一次路径1->2->4->6,流大小:12

    更新后图为:

    第二次路径为1->3->5->6,流大小:4

    更新后图为:

     

    第三次路径为1->3->5->4->6,流大小:7

    更新后图为:

    此时,再也找不到最短路径,算法结束,则最大流为:12+4+7=23

     

    控制台对应输出为:

     

    关键定理证明:

    最大流最小割定理:

    下面条件等价

    1、f是G的一个最大流

    2、残存网络不包括任何增广路径

    3、|f|=c(S,T),其中(S,T)是流网络的某个切割

    1推2:

    假定f是G的一个最大流,但残存网络中仍包含有一条增广路径,那么对流f增加流量后,所得的值是严格大于f的值的,这与f是G的一个最大流矛盾

    2推3:

    假设流网络G不包含任何增广路径,现在定义S为G中存在一条从s到v的路径的所有v的集合,定义T为V-S,则划分(S,T)是流网络G的一个切割。

    对S中的任意一个结点u,T中的任意一个结点v

    如果(u,v)属于E,则必有f(u,v)=c(u,v)

    如果(v,u)属于E,则必有f(v,u)=0

    如果(u,v)和(v,u)都不属于E,则f(u,v)= f(v,u)=0

    因此

    所以|f| = f(S,T)= c(S,T),得证

    3推1:

    对于所有切割(S,T),|f|≤c(S,T)

    因此,当|f| = c(S,T)时,f就是一个最大流

     

    时间复杂度分析

    分析

    对于一个流网络,我们要分析EK算法的复杂度,实际就是要分析调用bfs的次数,但是bfs的次数是很难分析的,所以需要做一点转换,将对bfs次数的分析转换为其它和它等价的实体量且稍微简单一点的分析

    在实际分析中,我们发现关键边的个数和bfs的次数是等价的,所以要分析bfs次数,不妨就分析关键边的个数

     

    关键边定义:

    边(u,v)的残存容量为最短路径的残存容量,则称为为关键边

    任一增广路径都至少存在一条关键边

     

    时间复杂度计算:

    边(u,v)成为关键边到下一次成为关键边,从原结点到u的距离至少增加2个单位

    ②由于从源结点s到结点u的中间结点不可能包括s、u或t,所以一直到u成为不可到达结点前,距离最长为v-2

    由①②可得边(u,v)成为关键边的次数最多为(V-2)/2,取V/2

     

    由于一共有E条边,所以EK算法中关键边总数为O(VE)

    总时间 = BFS时间 * BFS次数

    由于每次BFS时间为O(E),需要O(VE)次BFS,所以总时间为O(VE²)

     

     

    FF算法:

    FF算法介绍

    FF算法和EK算法很相似,唯一不同的地方就是FF算法每次找的不是最短增广路径,它找的路径是随机的

     

    FF算法缺陷分析:

    由于FF算法每次找的增广路径不是最短路径,所以FF算法存在这样一个缺陷:它会使一条边成为关建边的最大次数从原来的V/2上升到K/2(K为所有边中权值最大的边的权值)

    举下面一个例子

    图3、FF算法样例图

    按照EK算法,边(u,v)和(v,u)成为关键边的最大次数应该是4/2-1 = 1,所以所需要的bfs次数为1+1 = 2次

    图4、FF算法过程图

     

    图5、FF算法过程图

    在FF算法中,它将以图4和图5的方式反复流动500000次

    边(u,v)和(v,u)成为关键边的最大次数是1000000/2=500000,所以所需要的bfs次数为500000+500000=1000000次,由于调用bfs的效率过低,所以会导致FF算法比EK算法慢

    代码:×

     

    展开全文
  • 51c语言ff算法

    2018-04-15 15:45:24
    c语言fft算法,在51单片机上调试通过,适用于雷达测试
  • 个人最近的一些算法编程练习,包含了一些springboot其他工具学习文档
  • 弹性光网络中虚拟网络映射的常用算法,包括频谱分配 首次命中 KSP等算法
  • FF 算法与 EK 算法是求解最大流的一般增广路方法,其时间复杂度均为 O(n*m*m) Ford-Fulkerson 算法是求解最大流的最基础的算法,其核心思想是增广路定理:网络达到最大流当且仅当残留网络中没有增广路 程序的实现...

    【概述】

    FF 算法与 EK 算法是求解最大流的一般增广路方法,其时间复杂度均为 O(n*m*m)

    Ford-Fulkerson 算法是求解最大流的最基础的算法,其核心思想是增广路定理:网络达到最大流当且仅当残留网络中没有增广路

    程序的实现过程与增广路求最大流的过程基本一致,即每一次更新都进行一次找增广路然后更新路径上的流量的过程。

    在传统的 FF 算法中,利用 dfs 每次找增广路的过程十分繁琐,常常会走冤枉路,此时更新增广路的复杂度就会增加,EK 算法为了规避这个问题使用了 bfs 来寻找增广路,然后在寻找增广路的时候总是向离汇点越来越近的方向去寻找下一个结点。

    【基本思想】

    1)若存在增广路径,则找出一条增广路径(通过 BFS)

    2)沿着找出的增广路径进行更新流量

    3)当没有增广路时,网络达到最大流

    【沿增广路径增广方法】

    第一步:计算可增加流量

      设:某一增广路径结点为 a1,a2,...,an,可增加流的增加流量 dis=INF

        若 (u,v) 是正向边,则:dis=min(dis,c(ai,aj)-f(ai,aj)),其中:j=i+1,i=1,2,...,n-1

        若 (u,v) 是逆向边,则:dis=min(dis,f(ai,aj)),其中:j=i+1,i=1,2,...,n-1

    第二步:更新流量

      若 (u,v) 是正向边,则:f(u,v)=f(u,v)+dis

      若 (u,v) 是负向边,则:f(u,v)=f(u,v)-dis(伴随着这部分流量的减去,必有另一部分的管道流量会增加)

    【模版】

    1.FF 算法

    struct Edge {
        int to, next;
        int cap;
    } edge[N * N];
    int head[N], tot;
    bool vis[N], flag;
    LL res;
    void addEdge(int x, int y, int cap) {
        edge[tot].to = y;
        edge[tot].cap = cap;
        edge[tot].next = head[x];
        head[x] = tot++;
    
        edge[tot].to = x;
        edge[tot].cap = 0;
        edge[tot].next = head[y];
        head[y] = tot++;
    }
    int dfs(int x, int T, int flow) { // dfs求任意路径
        if (x == T) {
            res += flow;
            flag = true;
            return flow;
        }
    
        vis[x] = true;
        for (int i = head[i]; i != -1; i = edge[i].next) {
            int x1 = edge[i].to;
            if (vis[x1] || edge[i].cap == 0)
                continue;
            int newFlow = dfs(x1, T, min(flow, edge[i].cap));
            if (flag) {
                edge[i].cap -= newFlow;
                edge[i ^ 1].cap += newFlow;
                return newFlow;
            }
        }
        return 0;
    }
    void FF(int S, int T) { //有增广路就增广
        flag = 0;
        memset(vis, 0, sizeof(vis));
        dfs(S, T, INF);
    
        while (flag) {
            flag = 0;
            memset(vis, 0, sizeof(vis));
            dfs(S, T, INF);
        }
    }
    int main() {
        memset(head, -1, sizeof(head));
        tot = 0;
        res = 0;
    
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
            int x, y, cap;
            scanf("%d%d%d", &x, &y, &cap);
            addEdge(x, y, cap);
        }
        int S = 1, T = n;
        FF(S, T);
        printf("%d\n", res);
    
        return 0;
    }

    2.EK 算法

    int n, m;
    int cap[N][N];  //容量
    int flow[N][N]; //流量
    
    int EK(int s, int t) { //沿着增广路增广
        int res = 0;       //最大流
        int dis[N];        // a[i]表示从s到i的最小残量
        int p[N];          //增广路中的上一节点
        queue<int> Q;
        while (true) {
            memset(dis, 0, sizeof(dis));
            dis[s] = INF;
            Q.push(s);
            //计算可增加流量
            while (!Q.empty()) {
                int x = Q.front();
                Q.pop();
                for (int y = 1; y <= n; y++) {
                    if (!dis[y] && cap[x][y] > flow[x][y]) {
                        p[y] = x;
                        Q.push(y);
                        dis[y] = min(dis[x], cap[x][y] - flow[x][y]);
                    }
                }
            }
    
            if (dis[t] == 0) //当网络中没有增广路径
                break;
            //更新流量
            for (int x = t; x != s; x = p[x]) {
                flow[p[x]][x] += dis[t];
                flow[x][p[x]] -= dis[t];
            }
            res += dis[t];
        }
        return res; //返回最大流
    }
    
    int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        memset(cap, 0, sizeof(cap));
        memset(flow, 0, sizeof(flow));
        while (m--) {
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w); //两点的容量
            cap[x][y] = +w;              //可能有重边
        }
        printf("%d\n", EK(1, n));
        return 0;
    }
    展开全文
  • BF FF算法模拟操作系统的内存分配回收。用MFC编程 涉及多线程编程
  • 最大流问题以及FF算法

    千次阅读 2017-05-15 16:24:46
    FF算法 Ford-Fulkerson 算法是一种解决最大流的方法,其依赖于三种重要思想: 残留网络(Residual networks) 增广路径(Augmenting paths) 割(Cut) Edmonds-Karp算法 即最短路径增广算法 简称EK...

    最大流问题

    问题描述:

    给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).

    最大流问题拓扑图

    约束条件:

    设 G = (V, E) 是一个流网络,其容量函数为 c。设 s 为网络的源点,t 为汇点。G 的流的一个实值函数 f:V×V → R,且满足下列三个性质:

    容量限制(Capacity Constraint):对所有顶点对 u, v ∈ V,要求 f(u, v) ≤ c(u, v)。
    反对称性(Skew Symmetry):对所有顶点对 u, v ∈ V,要求 f(u, v) = - f(v, u)。
    流守恒性(Flow Conservation):对所有顶点对 u ∈ V - {s, t},要求 Σv∈Vf(u, v) = 0。
    f(u, v) 称为从顶点 u 到顶点 v 的流,流的值定义为:|f| =Σv∈Vf(s, v),即从源点 s 出发的总流。

    最大流问题(Maximum-flow problem)中,给出源点 s 和汇点 t 的流网络 G,希望找出从 s 到 t 的最大值流。

    满足流网络的性质的实际上定义了问题的限制:

    经过边的流不能超过边的容量;
    除了源点 s 和汇点 t,对于其它所有顶点,流入量与流出量要相等。

    示例结果:

    上图最大流为 23,流向如下图所示
    最大流量

    FF算法

    Ford-Fulkerson 算法是一种解决最大流的方法,其依赖于三种重要思想:
    残留网络(Residual networks)
    增广路径(Augmenting paths)
    割(Cut)

    Edmonds-Karp算法 即最短路径增广算法 简称EK算法

    EK算法基于一个基本的方法:Ford-Fulkerson方法 即增广路方法 简称FF方法

    增广路方法是很多网络流算法的基础 一般都在残留网络中实现

    其思路是每次找出一条从源到汇的能够增加流的路径 调整流值和残留网络 不断调整直到没有增广路为止

    FF方法的基础是增广路定理(Augmenting Path Theorem):网络达到最大流当且仅当残留网络中没有增广路

    EK算法就是不断的找最短路 找的方法就是每次找一条边数最少的增广 也就是最短路径增广.

    Reference:

    http://www.jianshu.com/p/1451e70909c8#
    http://www.cnblogs.com/gaochundong/p/ford_fulkerson_maximum_flow_algorithm.html
    http://www.cnblogs.com/Booble/archive/2011/03/04/1970453.html

    展开全文
  •  1.残存网络:即为一条管道被占用了一部分流量之后所剩下的流量。在网络流中,图被看为一个有向图,残存流量向量相加后永远不变。这一点有点像基尔霍夫定律。  2.在找到一个流之后,仍然存在的从源点到汇点的路径...
  • FF(首次适应)算法C,Java实现

    千次阅读 2017-11-07 14:27:32
    FF(首次适应)算法C,Java实现
  • FF BF WF 算法 (java)

    2019-12-24 16:53:26
    1. 首次适应 FF • 每次从 低地址 开始查找 2. 最佳适应 BF • 空闲分区 按 容量递增 链接 • 从小的分区开始查找 3. 最坏适应 WF • 空闲分区 按 容量递减 链接 • 从大的...
  • FF最大流问题算法

    千次阅读 2018-11-23 11:38:13
    一、最大流问题 最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论如何充分利用装置的能力,使得运输的流量最大,以取得最好的效果。 实际来源: ...性质1:容量限制(Capacity Constra...
  • 首次适应算法(FF)和循环首次适应算法(NF)原文:...FF算法按地址递增从头扫描空闲分区,如果找到空闲分区大小&gt;=作业大小则分配。如果扫描完空闲分区表都没有...
  • 最大流的FF算法似乎是最简单的,即使是之前没怎么接触最大流的我也照着标程两下就会了。 FF算法大约是这么一个过程:不断地寻找源点到汇点的增广路,找到一个是一个,找不到了,那就已经是最大流了。找增广...
  • 弹性光网络中的KSP-FF-RSA算法matlab代码,实测有效,考虑了K最短路径、首次命中以及调制格式选择,最终能输出网络阻塞率,并提供多个候选网络拓扑测试,备注超级详细。
  • 内存分配算法代码模拟。包含 首次适应算法(First Fit) 最佳适应算法(Best Fit)最差适应算法(Worst Fit)伙伴算法(buddy) https://blog.csdn.net/GreyBtfly/article/details/84646981
  • 分区分配算法:  首次适应算法(First Fit):从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给 作业,这种方法的目的在于减少查找时间。为适应这种算法,空闲分区表(空闲区链)中的空闲...
  • 首次适应算法(FF)及其应用

    千次阅读 2019-02-19 16:46:17
    我们用的比较多的就是FF,首次适应算法。空闲分区链以地址递增的次序链接 分配时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止;再按照要存东西的大小(我们称之为作业),从该分区中划出一块...
  • FF算法:最基础的最大流算法 EK算法:每次BFS寻找増广路 Dinic算法:EK算法的优化 Dinic+链式前向星 这里以POJ1273这道题为例,题目链接:http://poj.org/problem?id=1273 FF算法:最基础的最大流算法 通过DFS...
  • 内存分配算法FF、BF、MF)

    千次阅读 多人点赞 2019-05-09 17:58:48
    在实现动态分区分配时,将涉及到分区分配中所用到的数据结构、分区分配算法和分区的分配与回收操作三方面的问题。 我的理解是,动态分区分配是按照作业需要的主存空间大小来分配的,当要装入一个作业时,根据作业...
  • SHA1摘要算法(带示例)

    千次阅读 2019-01-22 17:01:09
    1. 算法简介 2. 符号 3. 加密算法流程 3.1 概述 3.2 填充. 3.3 加密处理 附录A 运算示例 1.算法简介 SHA英文全称Secure Hash Algorithm,即安全散列算法。散列算法又称杂凑算法或哈希算法,能将一定长度的...
  • 简化版的SHA1算法C语言版

    千次阅读 2016-05-16 16:41:38
    最近用到了一些常规散列算法,学习一下SHA算法,网上SHA1介绍很多,也有实例,但代码风格似乎符合我的审美。 经过学习验证,编写了一个简化版的SHA1算法,为什么叫简化版呢? 因为这个算法只能处理56字节以内的数据...
  • package neicunfenpei; import java.util.Scanner; public class Main { public static void main(String[] args) { Memory my = new Memory(); Scanner sc = new Scanner(System.in);... System.out.println("1
  • SHA256算法原理详解

    万次阅读 多人点赞 2018-07-03 23:07:30
    SHA-2,名称来自于安全散列算法2(英语:Secure Hash Algorithm 2)的缩写,一种密码散列函数算法标准,由美国国家安全局研发,属于SHA算法之一,是SHA-1的后继者。 SHA-2下又可再分为六个不同的算法标准 包括了:...
  •   在之前的工作中,用到了CRC16、MD5 和 SHA1 算法,主要用来校验下发的文件。网上关于这些算法的文章铺天盖地,以下内容仅仅是自己在学习时候的一个记录,一些套话来自于互联网。下面先来看看 SHA1。    以下...
  • 内存分配---FF、BF、WF三种算法

    千次阅读 2018-05-20 23:43:00
    所用的数据结构、分区分配算法和分区的分配与内存回收的过程。 分区分配中的数据结构:(1)描述空闲块的数据结构。(2)内存块的描述。 #define PROCESS_NAME_LEN 32 //进程名长度 #define MIN_SLICE 10 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 73,880
精华内容 29,552
关键字:

ff1算法