k最近邻算法实验报告

第一篇：k最近邻算法实验报告

题

目学生姓名学生学号专业班级指导教师

k-最近邻算法实现

2015-1-2

实验二 k-最近邻算法实现

一、实验目的

1.加强对k-最近邻算法的理解；

2.锻炼分析问题、解决问题并动手实践的能力。

二、实验要求

使用一种你熟悉的程序设计语言，如C++或Java，给定最近邻数k和描述每个元组的属性数n，实现k-最近邻分类算法，至少在两种不同的数据集上比较算法的性能。

三、实验环境

Win7 旗舰版 + Visual Studio 2010 语言：C++

四、算法描述

KNN(k Nearest Neighbors)算法又叫k最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类，KNN就是计算每个样本数据到待分类数据的距离。如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待

分样本集来说，KNN方法较其他方法更为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

1、算法思路

K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的（未标记的）样本需要分类时才建立分类。K-最临近分类基于类比学习，其训练样本由N维数值属性描述，每个样本代表N维空间的一个点。这样，所有训练样本都存放在N维模式空间中。给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的K个训练样本。这K个训练样本是未知样本的K个“近邻”。“临近性”又称为相异度（Dissimilarity），由欧几里德距离定义，其中两个点 X（x1,x2,„,xn）和Y（y1,y2,„,yn）的欧几里德距离是：

D(x,y)(x1y1)2(x2y2)2(xnyn)2

未知样本被分配到K个最临近者中最公共的类。在最简单的情况下，也就是当K=1时，未知样本被指定到模式空间中与之最临近的训练样本的类。

2、算法步骤

step.1---初始化距离为最大值；

step.2---计算未知样本和每个训练样本的距离dist； step.3---得到目前K个最临近样本中的最大距离maxdist；

step.4---如果dist小于maxdist，则将该训练样本作为K-最近邻样本； step.5---重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完； step.6---统计K-最近邻样本中每个类标号出现的次数； step.7---选择出现频率最大的类标号作为未知样本的类标号。

3、算法伪代码

搜索k个近邻的算法：kNN(A[n],k)输入：A[n]为N个训练样本在空间中的坐标（通过文件输入），k为近邻数 输出：x所属的类别

取A[1]~A[k]作为x的初始近邻，计算与测试样本x间的欧式距离d（x,A[i]）,i=1,2,.....,k；按d（x，A[i]）升序排序，计算最远样本与x间的距离D<-----max{d(x,a[j])| j=1,2,.....,k};

for(i=k+1;i<=n;i++)

计算a[i]与x间的距离d(x,A[i]);

if(d(x,A[i]))

then 用A[i]代替最远样本

按照d(x,A[i])升序排序，计算最远样本与x间的距离D<---max{d(x,A[j])| j=1,...,i };计算前k个样本A[i]),i=1,2,...,k所属类别的概率，具有最大概率的类别即为样本x的类。

五、数据结构

代码结构如图所示，方法描述如下： KNN：KNN类构造函数，用于读取数据集；

get_all_distance:KNN类公有函数，计算要分类的点到所有点的距离； get_distance:KNN类私有函数，计算两点间的距离；

get_max_freq_label:KNN类公有函数，在k个数据里，获取最近k个数据的分类最多的标签，将测试数据归位该类。

类图如上图所示，KNN类的成员变量描述如下： dataSet：tData型二维数组，用于训练的数据集；

k：int型，从k个最近的元素中，找类标号对应的数目的最大值，归类； labels：tLable型一维数组，类标签；

map_index_dist：map型，记录测试点到各点的距离； map_label_freq：map型，记录k个邻居类，各类的个数。

六、程序截图

七、实验总结

八、附件

1.程序源码

kNN1.cpp #include #include

using namespace std;

typedef char tLabel;typedef double tData;typedef pair PAIR;const int colLen = 2;const int rowLen = 10;ifstream fin;

class KNN { private:

tData dataSet[rowLen][colLen];

tLabel labels[rowLen];

int k;

map map_index_dis;

map map_label_freq;

double get_distance(tData *d1,tData *d2);public:

KNN(int k);

void get_all_distance(tData * testData);

void get_max_freq_label();

struct CmpByValue

{

bool operator()(const PAIR& lhs,const PAIR& rhs)

{

return lhs.second < rhs.second;

}

};};

KNN::KNN(int k){ this->k = k;

fin.open(“data.txt”);

if(!fin){

cout<<“can not open the file data.txt”<

exit(1);}

/* input the dataSet */

for(int i=0;i

for(int j=0;j

{

fin>>dataSet[i][j];

}

fin>>labels[i];} } /* * calculate the distance between test data and dataSet[i] */ double KNN:: get_distance(tData *d1,tData *d2){ double sum = 0;for(int i=0;i

sum += pow((d1[i]-d2[i]), 2);}

// cout<<“the sum is = ”<

*/ void KNN:: get_all_distance(tData * testData){ double distance;int i;for(i=0;i

distance = get_distance(dataSet[i],testData);

// =>

map_index_dis[i] = distance;}

//traverse the map to print the index and distance map::const_iterator it = map_index_dis.begin();while(it!=map_index_dis.end()){

cout<<“index = ”<first<<“ distance = ”<second<

it++;} } /* * check which label the test data belongs to to classify the test data

*/ void KNN:: get_max_freq_label(){ //transform the map_index_dis to vec_index_dis vector

vec_index_dis(map_index_dis.begin(),map_index_dis.end());//sort the vec_index_dis by distance from low to high to get the nearest data sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue());

for(int i=0;i

cout<<“the index = ”<

//calculate the count of each label

map_label_freq[ labels[ vec_index_dis[i].first ] ]++;}

map::const_iterator map_it = map_label_freq.begin();

tLabel label;int max_freq = 0;//find the most frequent label while(map_it!= map_label_freq.end()){

if(map_it->second > max_freq)

{

max_freq = map_it->second;

label = map_it->first;

}

map_it++;} cout<<“The test data belongs to the ”<

int main(){ tData testData[colLen];int k;cout<<“please input the k value : ”<>k;KNN knn(k);cout<<“please input the test data :”<

cin>>testData[i];knn.get_all_distance(testData);knn.get_max_freq_label();

system(“pause”);

return 0;}

2.数据集 data.txt

第二篇：算法实验报告

《算法设计与分析》

实验报告

班级

姓名

学号

****年**月**日

目录

实验一

二分查找程序实现…………………………………………………………………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，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索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，算法终止；如果searchKeyb[n/2]，则只要在数组b的右半部继续搜索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算法实验报告

信息安全实验报告

题 目 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 #include #include #define False 0 #define True 1 int Max[100][100]={0};//各进程所需各类资源的最大需求 int Avaliable[100]={0};//系统可用资源 char name[100]={0};//资源的名称

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<>i;//输入须申请的资源号

cout<>Request[j];//输入需要申请的资源 } for(j=0;jNeed[i][j])//判断申请是否大于需求，若大于则出错

{ cout<Avaliable[j])//判断申请是否大于当前资源，若大于则

{ //出错

cout<

int main()//主函数 {

int t=1,i,j,number,choice,m,n,flag;char ming;cout<<“*****************银行家算法的设计与实现*****************”<>n;N=n;for(i=0;i>ming;name[i]=ming;cout<<“资源的数量:”;cin>>number;Avaliable[i]=number;} cout<>m;M=m;cout<>Max[i][j];do{ flag=0;cout<>Allocation[i][j];if(Allocation[i][j]>Max[i][j])flag=1;Need[i][j]=Max[i][j]-Allocation[i][j];} if(flag)cout<

showdata();//显示各种资源

safe();//用银行家算法判定系统是否安全

while(1){

if(t==1){ cout<

t=0;} else break;cout<

}

return 1;}

五、程序执行结果： cin>>t;cout<

六、实验总结

多个进程同时运行时，系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列，使得系统能快速且安全地运行进程，不至发生死锁。银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。

09信管（2）班

何美西 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、流程图： 系统主要过程流程图

银行家算法流程图

安全性算法流程图

四、实验代码：

//#define M 5 //#define N 3 #include //本实验中使用到的库函数 #include #include int max[5][1];//开始定义银行家算法中需要用到的数据 int allocation[5][1];int need[5][1];int available[1];int request[5][1];char *finish[5];int safe[5];int n,i,m;int k=0;int j=0;int work[1];int works[5][1];

void line()//美化程序，使程序运行时更加明朗美观 { printf(“-----------------n”);} void start()//表示银行家算法开始 { line();printf(“ 银行家算法开始n”);printf(“--死锁避免方法 line();} void end()//表示银行家算法结束 { line();printf(” 银行家算法结束，谢谢使用n“);line();} void input()//输入银行家算法起始各项数据 {

for(n=0;n<5;n++)

{

printf(”请输入进程P%d的相关信息：n“,n);

printf(”Max:“);

for(m=0;m<1;m++)

scanf(”%d“,&max[n][m]);

printf(”Allocation:“);

for(m=0;m<1;m++)

scanf(”%d“,&allocation[n][m]);

n”);

}

for(m=0;m<1;m++)

need[n][m]=max[n][m]-allocation[n][m];printf(“请输入系统可利用资源数Available:”);for(m=0;m<1;m++)

} void output()//输出系统现有资源情况 { line();printf(“资源情况 Max Allocation Need Availablen”);printf(“进程 A A A A n”);line();for(n=0;n<5;n++){ printf(“P%d%3d%3d%3d”,n,max[n][0],allocation[n][0],need[n][0]);

} line();}

void change()//当Request[i,j]<=Available[j]时，系统把资源分配给进程P[i]，Available[j]和Need[i,j]发生改变

{ for(m=0;m<1;m++){ if(n==0)else

printf(“n”);

printf(“%3d%3dn”,available[0]);scanf(“%d”,&available[m]);

} } available[m]-=request[i][m];allocation[i][m]+=request[i][m];need[i][m]-=request[i][m];void outputsafe()//输出安全序列的资源分配表 { printf(“该安全序列的资源分配图如下：n”);line();printf(“资源情况 Work Need Allocation Work+Allocation Finishn”);printf(“进程 A A A A n”);line();for(n=0;n<5;n++)

printf(“P%d%9d%3d%3d%5d%12sn”,safe[n],works[safe[n]][0],need[safe[n]][0],allocation[safe[n]][0],works[safe[n]][0]+allocation[safe[n]][0],finish[n]);line();} int check()//安全性算法 { printf(“开始执行安全性算法……n”);for(m=0;m<1;m++)//数组work和finish初始化

work[m]=available[m];for(n=0;n<5;n++){

} finish[n]=“false”;safe[n]=0;k=0;for(m=0;m<5;m++)for(n=0;n<5;n++)

if(strcmp(finish[n],“false”)==0 && need[n][0]<=work[0])//查找可以分配资源但尚未分配到资源的进程

{

safe[k]=n;//以数组safe[k]记下各个进程得到

分配的资源的顺序

works[safe[k]][0]=work[0];

放出分配给它的资源

work[0]+=allocation[n][0];//进程执行后释

finish[n]=“ture”;//finish[n]变为1以示该进

程完成本次分

}

k++;for(m=0;m<5;m++)//判断是否所有进程分配资源完成{

0

素都为ture } else

if(m==4)//此处m=4表示所有数组finish的所有元if(strcmp(finish[m],“false”)==0){

printf(“找不到安全序列，系统处于不安全状态。n”);return 0;//找不到安全序列，结束check函数，返回 {

printf(“找到安全序列P%d->P%d->P%d->P%d->P%d，系统是安全的n”,safe[0],safe[1],safe[2],safe[3],safe[4]);

} return 1;} void main()//主程序开始 { start();for(;j==0;)//确认输入数据的正确性，若输入错误，重新输入

{

入：“);

} printf(”数据确认无误，算法继续。n“);if(check()==0)//若check函数返回值为0，表示输入的初始数据找不到安全序列，无法进行下一步，程序结束

{

} for(;j==1;)//当有多个进程请求资源时，循环开始

{

printf(”请输入请求资源的进程i(0、1、2、3、4)：“);//输入发出请求向量的进程及请求向量 end();exit(0);input();printf(”以下为进程资源情况，请确认其是否正确：n“);output();printf(”数据是否无误：n正确：输入1n错误：输入0n请输

}

j=1;

outputsafe();//输出安全序列的资源分配表

scanf(“%d”,&j);

scanf(“%d”,&i);printf(“请输入进程P%d的请求向量Request%d：”,i,i);for(n=0;n<1;n++)

scanf(“%d”,&request[i][n]);

for(;request[i][0]>need[i][0];)//若请求向量大于需求资源，则认为是输入错误，要求重新输入

{

printf(“数据输入有误，请重试！n请输入进程P%d的请求向量Request%d：”,i,i);

提供分配

n“,i);

} if(request[i][0]<=available[0])//判断系统是否有足够资源

for(n=0;n<1;n++)

scanf(”%d“,&request[i][n]);{

} else

printf(”系统没有足够的资源，进程P%d需要等待。printf(“系统正在为进程P%d分配资源……n”,i);change();//分配资源 j=0;if(j==0)//j=0表示系统有足够资源分配的情况 {

printf(“当前系统资源情况如下：n”);//输出分配资源后的系统资源分配情况

分配无效

output();

if(check()==0)//若找不到安全系列，则之前的资源 {

printf(“本次资源分配作废，恢复原来的资源分配

状态。n”);

资源状态

输入：“);

for(m=0;m<1;m++)//恢复分配资源前的系统

}

}

{

}

output();//输出系统资源状态

available[m]+=request[i][m];allocation[i][m]-=request[i][m];need[i][m]+=request[i][m];printf(”是否还有进程请求资源？n是：输入1n否：输入0n请

scanf(“%d”,&j);//若还有进程请求资源，j=1，之前的for循环条件满足

} end();}

五、程序执行结果：

六、实验总结

多个进程同时运行时，系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列，使得系统能快速且安全地运行进程，不至发生死锁。银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。