第一篇：《计算机算法》实验报告
1.实验名称
本次实验的名称。
2.问题描述
对本次实验要解决的问题的描述。
例子：处理汉诺塔问题时，描述什么是汉诺塔问题。
3.解决思路
采用什么方法；为什么可以采用这个方法； 例子：处理棋盘覆盖问题时，采用什么方法：采用递归分治的方法处理；
为什么可以采用递归分治方法的原因（P21页图2-6下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种L型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分（参见图2-6的b），则三个小棋盘都各有1个特殊方格所覆盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。
4.算法设计与分析
给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析算法的时间复杂度（空间复杂度）。注意，一定要有文字说明。例子：快速排序 伪算法描述
QuickSort(int a[], int p, int r){ 如果待排序数组a[]中只有一个元素则直接返回； 如果待排序数组a[]中不止一个元素，则进行如下处理 {
对数组a[p:r]进行Partition划分，使得a[p:r]以a[p]为标准，划分为三个部分，即：
左半部分a[p:q-1]；划分基准a[q]=a[p]；右半部分a[q+1:r]；
对左半部分快速排序QuickSort(a, p, q-1);
对右半部分快速排序QuickSort(a, q+1, r)； } }
例子：0-1背包问题
递归关系或者递归方程。
给出P72页“2.递归关系”中的递归表达式，并给出文字说明。注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。
5.程序实现
依据第4部分，给出C语言（其他语言亦可）的程序实现，并进行算法时间（空间）复杂度分析。
程序实现部分要包括：程序代码、程序注释、程序运行结果（或者截图）。
例子：快速排序的partition函数 int Partition(Type a[], int p, int r){
int i=p, j= r+1;
int x = a[p];//x=a[p]是对数组a进行划分的标准；
/* 以下循环将数组a[p:r]以a[p]为标准进行划分，在划分完毕之后，* a[p]调整到数组a[p:r]的中间位置q，有a[q]=a[p]；q左边所有的* 元素均小于a[p]，即a[p:q-1]中的任意元素都小于a[p]；q右边
* 所有的元素均大于a[p]，即a[q+1:r]中的元素都大于a[p]。
* /
while(true){ /* i用来从数组a[p:r]的左边向右边扫描，如果a[++i]中的元素总是 * 小于基准元素的，则是符合划分标准的，因此，不用额外处理，* 循环一直继续,直到第一个不满足划分标准的a[++i]（即a[++i]>=i）* 出现，或者整个数组a[p:r]扫描完毕（即i while(a[++i] „„ 6.总结 不用每个实验写一个总结，可以在一次课作业的最后写一个总结。当然，如果需要，在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。 1.实验名称 本次实验的名称。 2.问题描述 对本次实验要解决的问题的描述。 例子：处理汉诺塔问题时，描述什么是汉诺塔问题。 3.解决思路 采用什么方法；为什么可以采用这个方法； 例子：处理棋盘覆盖问题时，采用什么方法：采用递归分治的方法处理； 为什么可以采用递归分治方法的原因（P21 页图 2-6 下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种 L 型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分（参见图 2-6 的 b），则三个小棋盘都各有 1 个特殊方格所覆盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。 4.算法设计与分析 给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析算法的时间复杂度（空间复杂度）。注意，一定要有文字说明。 例子：快速排序 伪算法描述 QuickSort(int a[], int p, int r){ 如果待排序数组 a[]中只有一个元素则直接返回； 如果待排序数组 a[]中不止一个元素，则进行如下处理 { 对数组 a[p:r]进行 Partition 划分，使得 a[p:r]以 a[p]为标准，划分为三个部分，即： 左半部分 a[p:q-1]；划分基准 a[q]=a[p]；右半部分 a[q+1:r]； 对左半部分快速排序 QuickSort(a, p, q-1); 对右半部分快速排序 QuickSort(a, q+1, r)； } } 例子：0-1 背包问题 递归关系或者递归方程。 给出 P72 页“2.递归关系”中的递归表达式，并给出文字说明。 注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。 5.程序实现 依据第 4 部分，给出 C 语言（其他语言亦可）的程序实现，并进行算法时间（空间）复杂度分析。 程序实现部分要包括：程序代码、程序注释、程序运行结果（或者截图）。 例子：快速排序的 partition 函数 int Partition(Type a[], int p, int r){ int i=p, j= r+1; int x = a[p]; //x=a[p]是对数组 a 进行划分的标准； /* 以下循环将数组 a[p:r]以 a[p]为标准进行划分，在划分完毕之后，* a[p]调整到数组 a[p:r]的中间位置 q，有 a[q]=a[p]；q 左边所有的* 元素均小于 a[p]，即 a[p:q-1]中的任意元素都小于 a[p]；q 右边 * 所有的元素均大于 a[p]，即 a[q+1:r]中的元素都大于 a[p]。 * / while(true){ /* i 用来从数组 a[p:r]的左边向右边扫描，如果 a[++i]中的元素总是 * 小于基准元素的，则是符合划分标准的，因此，不用额外处理，* 循环一直继续,直到第一个不满足划分标准的 a[++i]（即 a[++i]>=i） * 出现，或者整个数组 a[p:r]扫描完毕（即 i */ while(a[++i] …… 6.总结 不用每个实验写一个总结，可以在一次课作业的最后写一个总结。当然，如果需要，在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。 《算法设计与分析》 实验报告 班级 姓名 学号 ****年**月**日 目录 实验一 二分查找程序实现…………………………………………………………………03页 实验二 棋盘覆盖问题（分治法）.…………………………………………………………08页 实验三 0-1背包问题的动态规划算法设计……………………………………………….11页 实验四 背包问题的贪心算法………………………………………………………………14页 实验五 最小重量机器设计问题（回溯法）………………………………………………17页 实验六 最小重量机器设计问题（分支限界法）…………………………………………20页 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验一：二分查找程序实现 一、实验时间：2013年10月8日，星期二，第一、二节地点：J13#328 二、实验目的及要求 目的： 建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。要求： 1、用c/c++语言实现二分搜索算法。 2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。 三、实验环境 平台：Win7 32位操作系统 开发工具：Codeblocks10.05 四、实验内容 对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素x。 五、算法描述及实验步骤 算法描述： 折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x 1、首先设定问题规模n； 2、随即产生递增数列； 3、在n个有序数中随机取一个作为待查找量，搜索之； 4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次； 5、改变问题规模n重复上述步骤2~4，n取100、200……1000； 6、依实验数据作图，并与理论图作比较； 7、二分搜索算法平均查找次数： 问题规模为n时，平均查找次数为： A(n)=Int(logn)+ 1/2 // Int()函数为向下取整 即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。 实验步骤： 1.初始化生成递增随机数列： for(int j=100;j <=1000;j+=100){ array[0]=10+rand()%15; for(int i=1;i array[i]=array[i-1]+1+rand()%3+rand()%10; } } 2.定义二分查找算法： int BinarySearch(const int b[], int searchKey, int low, int high);其中，返回值为int类型，数组b[]为待查递增序列，searchKey为所查数据，low为数组b[]左下标，hight为数组b[]右下标。该算法实现过程为： 将数组b[]的n个元素分成个数大致相同的两半，取b[n/2]与searchKey作比较。如果searchKey=b[n/2]，则找到searchKey，算法终止；如果searchKey 3.实现主函数并完成所有代码。4.算法复杂性分析： 容易看出，没执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O（logn）次。循环体内运算需要O（1）时间，因此整个算法在最坏情况下的计算时间复杂性为O（logn）。 六、调试过程及实验结果 输出结果为： Every array repeat search times: 10 Number of Elements 理论平均查找次数 实际平均查找次数 6.5 6.1 200 7.5 7.3 300 8.5 7.4 400 8.5 7.4 500 8.5 7.5 600 9.5 8.2 700 9.5 8.8 800 9.5 8.7 900 9.5 8.8 1000 9.5 9.4 七、总结 二分查找在搜索有序表时，效率比较高。通过这次实验我对二分查找算法的认识又有了新的提高。本想写个图形界面，但由于种种原因，没有实现，下次做加密算法时，要写一个图形化界面。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验二：分治法解决棋盘问题 一、实验时间：2013年10月22日，星期二，第一、二节地点：J13#328 二、实验目的及要求 1、用c/c++语言实现分治法解决棋盘问题算法。 2、实现棋盘化以及棋盘覆盖 三、实验环境 Windows 2007 操作系统 以及code blocks软件 四、实验内容 在一个2^k*2^k的方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一个特殊方格。用分治法将整个棋盘除特殊方格以外的方格覆盖。 五、算法描述及实验步骤 将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是： 左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格 右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格 左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格 右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。 六、调试过程及实验结果 七、总结 由于覆盖一个2k*2k棋盘所需的L型骨牌个数为（4k-1）/3，故此算法是一个在渐近意义下最优的算法。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验三：0-1背包问题的动态规划算法设计 一、实验目的及要求 1.了解并掌握动态规划算法的设计思想。 2.利用动态规划算法的设计思想实现0-1背包问题的算法设计。 二、实验环境 使用C++语言； 在windows环境下使用CodeBlocks调试并运行。 三、实验内容 1.了解并掌握动态规划的设计思想。 2.利用动态规划算法的思想解决0-1背包问题。 四、算法描述及实验步骤 每种物品一件，可以选择放1或不放0。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} “将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 五、调试过程及实验结果 六、总结 0-1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0-1背包问题求解。通过这次实验我对动态规划算法的认识又有了新的提高。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验四：背包问题的贪心算法 一、实验目的： 运用贪心算法思想，设计解决上述问题的算法，找出最大背包价值的装法。 二、实验要求 1.用c++语言实现背包问题的贪心算法。 2.掌握贪心思想的应用。 三、实验原理 在贪心算法中采用逐步构造最优解的办法，在每个阶段，都做出一个看上去最优的决策（在一定的标准下），决策一旦做出就不可更改。 四、实验过程(步骤)1.定义背包结构体： struct stone { int name;int weight;//物品的剩余重量 int weight_t;//物品的重量 float benefit;//物品的价值 //float b;};2.定义函数void sort(stone *data,int num)//计算物品的单位重量的价值，并进行排序 3.定义主函数并完成贪心选择。4.分析算法复杂性分析： 该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（n*logn）。 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，可以选择物品i 可以选择物品 的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构，最优子结构性质，极为相似，但 最优子结构 背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 五、运行结果 六、实验分析与讨论 贪心法的基本思路： ——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题： 1.不能保证求得的最后解是最佳的； 2.不能用来求最大或最小解问题； 3.只能求满足某些约束条件的可行解的范围。实现该算法的过程： 1.Begin 从问题的某一初始解出发； 2．while 能朝给定总目标前进一步 do 3.求出可行解的一个解元素； 4.由所有解元素组合成问题的一个可行解 七、实验心得 贪心算法通过一系列的选择来得知问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。通过背包问题的解决，进一步掌握了贪心算法的思想，并能在解问题时灵活运用。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验五：最小重量机器设计问题（回溯法） 一、实验目的 建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。 二、实验要求 1、用c++语言实现最小重量机器设计的回溯算法。 2、分析算法的计算复杂性 三、实验原理 首先，应该明确的确定问题的解空间。确定了解空间的组织结构后，发从开始节点（根节点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，向纵深方向搜索移至一个新的结点。这个新结点成为新的活结点，并成为新的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点成为死结点。此时，应往回移动（回溯）至最近的活结点，并使这个活结点成为当前的扩展结点。回溯以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。 四、实验过程(步骤)由于题目已经给出总价格的上限，因此算法通过使用回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最小。首先初始化当前价格cp=0,当前重量cw=0,此外，还要设置一个变量sum表示选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的sum小，如果小就赋给sum，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个排列树搜索完毕。这样，最终得到的sum即为最优解。 数据说明： N：零件数量 m：不同的零件商 W[][]:是从供应商j处购得的部件i的重量 c[][]：相应的价值 算法设计： a.部件有n个，供应商有m个，分别用w[i][j]和c[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。 b.用递归函数backtrack(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。 ① 若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。 ② 若cw>=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。 ③ 若i>n，则算法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行； ④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。 c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。 五、运行结果 六、实验心得 通过这次试验我明白了回溯法的思想，回溯法借助想象出来的树的结构，把问题简单化，使得解问题更方便。通过剪枝函数和约束函数对于求问题的解有很大的帮助，但要把一些限制条件把剪枝函数抽象化。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 实验六：最小重量机器设计问题（分支限界法） 一、实验时间：2013年11月12日，星期二，第一、二节地点：J13#328 二、实验目的及要求 1、了解分支限界法的基本思想。 2、运用分支限界法解决最小重量机器设计问题。 三、实验环境 平台：win7操作系统 开发工具：codeblocks10.05 四、实验内容 最小重量机器设计问题：设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计 五、算法描述及实验步骤 算法描述： 解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故cv=0，cw=0，position=0，peer=0，1≤i≤n。x[1:n]记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过c并加以扩展，队列为空时则结束循环。当peer=n时，此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若peer 实验步骤： 1.定义一个优先队列LinkQueue： void InitQueue(LinkQueue &Q);//创建一个队列-----首尾结点 void DestroyQueue(LinkQueue &Q);//销毁一个队列 void ClearQueue(LinkQueue &Q);//清空队列 int QueueEmpty(LinkQueue &Q);//判断队列是否为空，空则返回TURE，否则返回FLASE int QueueLength(LinkQueue &Q);//求队列的长度 void EnQueue(LinkQueue &Q,QElemType &e);//拆入e为新的队尾元素 void DeQueue(LinkQueue &Q,QElemType &e);//用e返回队列的对头元素 bool IsEmpty(LinkQueue &Q)//判断队列是否为空 2.定义类MinWeight，实现函数有： void Add(int wt,int ct,int i);//往队列插入节点 int FindBest();//实现最小重量机器的查找 void setMW();//函数初始化 void printMW();//打印输出结果 3 实现主函数并完成所有代码。 六、调试过程及实验结果 七、总结 利用分支限界法解决最小重量机器问题，就是构造一个优先队列，按照规定的优先级按最大效益优先的方式查找解空间树，找出满足要求的最优解。通过利用分支限界法解决最小重量机器问题，熟练了对分支限界法的使用。 指导教师对实验报告的评语 成绩： 指导教师签字： ****年**月**日 信息安全实验报告 题 目 RSA算法 姓 名 学 号 专业年级 计算机科学与技术2014级（1）班 指导教师 2016年 12 月 10日 一、实验目的 了解非对称加密机制 理解RSA算法的加解密原理 熟悉Java的学习以及运用Java实现RSA算法的加解密过程 二、实验背景 钥密码体制中，加密密钥(即公开密钥)PK是公开信息，而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在的这么多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。 三、实验原理 1.非对称密钥加解密概述 使用对称密钥加密体制进行保密通信时，任意不同的两个用户之间都应该使用互不相同的密钥。这样，如果一个网络中有n个用户，他们之间彼此都可能进行秘密通信，这时网络中将需要n(n-1)/2个密钥(其中，每个用户都需要保存n-1个密钥)，这样巨大的密钥量给密钥分配和管理带来了极大的困难。另外，随着计算机网络，特别是因特网的发展，网络上互不相识的用户可能需要进行保密的会话(例如，如果用户在进行电子商务活动时，需要保密的连接，这时的客户对象可能根本不是固定的对象)。最后，对称密钥加密机制难以解决签名验证问题。 非对称密钥加密也称为公开密钥加密，或者叫做公钥加密算法。使用公开密钥密码的每一个用户都分别拥有两个密钥：加密密钥和解密密钥，它们两者并不相同，并且由加密密钥得到解密密钥在计算机上是不可行的。每一个用户的加密密钥都是公开的。因此，加密密钥也称为公开密钥。所有用户的公开密钥都将记录在作用类似于电话号码薄的密钥本上，而它可以被所有用户访问，这样每一个用户都可以得到其他所有用户的公开密钥。同时，每一个用户的解密密钥将由用户保存并严格保密。因此，解密密钥也称为私有密钥。 非对称密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。公钥加密算法一般是将对密钥的求解转化为对数学上的困难问题的求解，例如RSA算法的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，已知两个大素数a和b，求出a*b是容易计算的，而已知a*b，想知道其是哪两个大素数的乘积目前还没有好的计算方法，另外也有一些非对称加密算法(如ELGamal算法)的安全性是基于求“离散对数”这个数学难题上的。 在公钥密码系统中每个实体都有自己的公钥和相应的私钥。公钥密码系统的加密变换和解密变换分别用E和D表示。任何实体B要向实体A发送信息m的步骤如下：实体B首先获得实体A的真实公钥的拷贝(eA)，实体B使用eA计算密文c=E(m)并发送给实体A，实体A使用自己的私钥dA，计算m=D(c)解密密文，恢复出明文m。这里公钥不需要保密，但要保证它的真实性，即eA确实是实体A掌握的私钥dA所对应的公钥。提供真实的公钥比安全地分配密钥实现起来要容易得多。这也是公钥密码系统的主要优点之一。 公钥密码系统的主要目的是提供保密性，它不能提供数据源认证(data origin authentication)和数据完整性(data integrity)。数据源认证是指：指定的数据是在以前的某个时间确实是由真正的源创建的。数据完整性是指：真正的源创建该数据后经过传输后存储没有发生改变。数据源认证和数据完整性要由其他技术来提供(如消息认证码技术、数字签名技术等)。 从本质上来看，公钥密码比对称密钥密码加密的速度要慢，粗略的说，公钥加密算法RSA硬件实现比分组加密算法DES硬件实现的速度慢1500倍，而软件实现的速度要慢100倍。 公钥解密也可以提供认证保证(如：在实体认证协议、带认证的密钥建立协议等)。公钥加密中必须有颁发让发送消息的人得到想要发送到的那个人的公钥的真实拷贝，否则就会受到伪装攻击。在实践中有很多方法分发真实的公钥，如：使用可信的公共文件，使用在线可信服务器，使用离线服务器和认证。 2.公钥加解密的优缺点： 1)大型网络中的每个用户需要的密钥数量少。 2)对管理公钥的可信第三方的信任程度要求不高而且是离线的。3)只有私钥是保密的，而公钥只要保证它的真实性。4)多数公钥加密比对称密钥加密的速度要慢几个数量级。5)公钥加密方案的密钥长度比对称加密的密钥要长。6)公钥加密方案没有被证明是安全的。 公钥密码的概念本身就被公认为是密码学上的一块里程碑。三十多年来的研究表明，公钥密码成功地解决了计算机网络安全中的密钥管理，身份认证和数字签名等问题，已经成为信息安全技术中的重大核心技术。 四、RSA算法 1.概述 RSA加密算法于1977年由美国麻省理工学院的Ronal Rivest，Adi Shamir和Len Adleman三位年轻教授提出，并以三人的姓氏Rivest，Shamir和Adleman命名为RSA算法。这三位科学家荣获2002图灵奖，以表彰他们在算法方面的突出贡献。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数的乘积却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。它无须收发双方同时参与加密过程，既可以用于保密也可以用于签名，因而非常适合于电子邮件系统的加密，互连网和信用卡安全系统。 算法概述：找两素数p和q，取n=p*q，取t=(p-1)*(q-1)，取任何一个数e，要求满足e 2.算法设计 1)publicstaticvoid GetPrime()说明：利用Java语言的中的java.math.BigInteger类的方法中随机产生大数。 2)public static boolean MillerRobin(BigInteger num)参数说明：num是由GetPrime方法产生的大数。 说明：这个方法判断GetPrime方法传过来的是否是一个素数，是就返回true,否就返回false。 3)public static BigInteger powmod(BigIntegera，BigIntegert，BigInteger num)说明：这个方法对传入的大数进行幂运算。 4)public static BigInteger invmod(BigInteger a，BigInteger b)说明：这个方法对大数进行取模运算。 5)public static String Encode(String inStr，BigInteger PrimeP，BigInteger PrimeQ，BigInteger n，int nLen，int m，JTextFieldd)方法名称：加密算法。参数说明： inStr是从界面输入的明文。 PrimeP和PrimeQ是由GetPrime方法产生的两个大素数。n是由PrimeP和PrimeQ得到的值。nLen为n的长度。d为公钥。 6)publicstatic String Decode(String inStr，BigInteger PrimeP，BigInteger PrimeQ，BigInteger n，int nLen，int m，JTextField e)方法名称：解密算法。参数说明： inStr是从界面输入的明文。 PrimeP和PrimeQ是由GetPrime方法产生的两个大素数。n是由PrimeP和PrimeQ得到的值。nLen为n的长度。e为私钥。 在对称加密中：n，d两个数构成公钥，可以告诉别人；n，e两个数构成私钥，e自己保留，不让任何人知道。给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。 RSA的安全性在于对于一个大数n，没有有效的方法能够将其分解从而在已知n，d的情况下无法获得e；同样在已知n，e的情况下无法求得d。 五、实验结果 实验结果如下图所示： 六、实验总结 本次实验对输入的任意一段明文字母，实现了输出对应密钥的密文字母。亲手实际编写RSA密码算法代码，更好的了解和掌握了RSA的相关内容。通过用Java对RSA密码体制进行编程，对RSA密码体制的加解密过程有了更深入的理解。通过这个实验更是让我获得了很多实际工作中所要具备的能力。 七、代码附录 略 计算机操作系统实验报告 何美西109253030212 一、实验名称：银行家算法 二、实验目的：银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 三、问题分析与设计： 1、算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。 2、银行家算法步骤：（1）如果Requesti＜or =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。 （2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。 （3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available=Available-Request[i];Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。 3、安全性算法步骤： （1）设置两个向量 ①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;②布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。 （2）从进程集合中找到一个能满足下述条件的进程： ①Finish[i]=false ②Need （3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work=Work+Allocation;Finish[i]=true;转向步骤（2）。（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。 4、流程图： 系统主要过程流程图 银行家算法流程图 安全性算法流程图 四、实验代码： #include int Allocation[100][100]={0};//系统已分配资源 int Need[100][100]={0};//还需要资源 int Request[100]={0};//请求资源向量 int temp[100]={0};//存放安全序列 int Work[100]={0};//存放系统可提供资源 int p[100]={0};int q[100][100]={0};int z[100][100]={0};int M=100;//作业的最大数为100 int N=100;//资源的最大数为100 int gg=1;void showdata()//显示资源矩阵 { int i,j;cout< int changdata(int i)//进行资源分配 { int j;for(j=0;j for(i=0;i cout< }//变分配数 Finish[i]=True;temp[k]=i;cout<<“ ”;cout<<“true”<<“ ”;cout< for(i=0;i Allocation[i][j]=Allocation[i][j]-Request[j];; Need[i][j]=Need[i][j]+Request[j]; } cout< return 0;} } cout< cout<<“安全序列为:”;for(i=0;i cout< { cout< { //出错 cout< int main()//主函数 { int t=1,i,j,number,choice,m,n,flag;char ming;cout<<“*****************银行家算法的设计与实现*****************”< showdata();//显示各种资源 safe();//用银行家算法判定系统是否安全 while(1){ if(t==1){ cout< t=0;} else break;cout< } return 1;} 五、程序执行结果： cin>>t;cout< 六、实验总结 多个进程同时运行时，系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列，使得系统能快速且安全地运行进程，不至发生死锁。银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。 09信管（2）班 何美西 109253030212第二篇：《计算机算法》实验报告范文(例文)
第三篇：算法实验报告
第四篇：RSA算法实验报告
第五篇：银行家算法实验报告
点击咨询 