第一篇：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個“近鄰”?！芭R近性”又稱為相異度（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();}

五、程序執行結果：

六、實驗總結

多個進程同時運行時，系統根據各類系統資源的最大需求和各類系統的剩余資源為進程安排安全序列，使得系統能快速且安全地運行進程，不至發生死鎖。銀行家算法是避免死鎖的主要方法，其思路在很多方面都非常值得我們來學習借鑒。