第一篇：貪心算法實驗報告
實驗報告題目 實驗四 貪心算法
開課實驗室：數學實驗室
指導老師：韓逢慶
時間：2011.12 學院：理學院
專業：信息與計算科學
班級：2009級2班 姓名：古 月
學號：09180230
一、實驗目的 1．加深學生對貪心算法設計方法的基本思想、基本步驟、基本方法的理解與掌握；
2．提高學生利用課堂所學知識解決實際問題的能力；
3．提高學生綜合應用所學知識解決實際問題的能力。
二、實驗內容
題目見P143:4-16,4-23.三、實驗要求
（1）用分治法求解最少加油次數和最少硬幣個數問題；
（2）再選擇自己熟悉的其它方法求解本問題；
（3）上機實現所設計的所有算法；
四、實驗過程設計（算法設計過程）（1）最少加油次數 實驗題目
一輛汽車加滿油以后可以行使n公里，旅途中有若干個加油站，設計一個有效算法，指出應在哪些加油站停靠加油，使沿路加油次數最少。并證明算法能產生一個最優解。過程設計
貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。比如說最少加油次數的問題。在這個算法中，我采用的貪心算法的策略。首先人機互動的設定加滿油以后最長能夠行使的距離，然后輸入了各個站點之間的距離，在程序的設計中，首先檢查了程序的可行性。要是遇到當某兩個站點之間的距離大于汽車一次加油以后所能夠行使的最大距離時，我們認為此問題是不可行的。這個在實際情況中也是很容易理解的。然后在滿足可行性條件下，依次采用貪心算法對問題得以實現。采用s這個來保存現在車里面留下的油，當此時留下的有能夠行駛完這一站點到下一站點之間的距離是，在這一站點的時候就不加油。但是若不能行使完這一段路程的時候，就加滿油。核心算法如下：
for(i=0,s=0;i { s=s+a[i]; if(s>n) { sum++; s=a[i]; } }（2）最少硬幣個數問題 實驗題目 考慮下面的用最少硬幣個數找出n分錢的問題： 當使用2角5分，1角，5分和1分四種硬幣面值時，設計一個找n分錢的貪心算法，并證明算法能產生最優解。過程設計 貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。比如說找最少硬幣個數的問題。在算法的實現過程中，當剩余的錢數大于2角5分時，我們在記錄找2角5分硬幣的個數的變量里面加一，同時把剩余所找的錢的總數目也減2角5分。不斷重復這個過程，直到剩余所需找的錢的數目小于2角5分時，在記錄找1角硬幣的個數的變量里面加一，同時把剩余所找的錢的總數目也減1角，不斷重復這個過程，直到剩余所需找的錢的數目小于1角。5分和1分的硬幣實現過程同上述過程一樣，一直執行到所剩的錢的數目為0，此時停止計算，得到最優解。 五、實驗結果分析（1）最少加油次數 當加油后行駛的最大距離小于相鄰站點的最小值時，此時，可行，求解結果如下： 當加油后行駛的最大距離大于相鄰站點的最小值時，此時，沒用可行性，為邊沿情況，求解結果如下： （分析時空復雜性，設計測試用例及測試結果）時間復雜性：該算法的時間復雜度為O(n)空間復雜性分析：該算法的空間復雜度為O(1)（2）最少硬幣問題 當輸入的找零錢數為正常的時候的運行情況如下： 當輸入的找零錢數為不正常的時候（為負）的運行情況如下： （分析時空復雜性，設計測試用例及測試結果）時間復雜性：該算法的時間復雜性為O(n)空間復雜性分析：該算法的空間復雜性為O(1) 六、實驗體會 貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。如單源最短路經問題，最小生成樹問題，相容活動安排問題等。這樣和采用動態規劃的算法相比，算法的思想更加的簡單，實現起來更加的容易。 但是也要明確貪心算法和動態規劃的主要區別。及0-1背包問題可以用動態規劃算法求解，但是貪心選擇算法卻不能用動態規劃算法求解。因為貪心算法無法最終將背包裝滿，部分閑置的背包空間使得每公斤背包空間的價值降低了。 七、附錄：（源代碼）（1）最少加油次數 具體算法的實現如下： #include cin>>a[i];} for(i=0;i<=n;i++){ cout<<“第”< if(a[j]>m) { sum=-1; break; } if(sum!=-1){ } for(i=0,s=0;i s=s+a[i]; if(s>n) { sum++; s=a[i]; } } } if(sum==-1)cout<<“沒有可行性”< #include cout<<“ 您輸入的數據有錯!”< a++; m=m-2.5;} while(m>=1){ b++; m=m-1;} while(m>=0.5){ c++; m=m-0.5;} while(m>=0.1){ d++; m=m-0.1;} f=a+b+c+d;cout<<“應找的最少的硬幣個數為：”< 《算法設計與分析》實驗報告 實驗3貪心算法 姓名 學號班級 實驗日期實驗地點 一、實驗目的 1、掌握貪心算法的設計思想。 2、理解最小生成樹的相關概念。 二、實驗環境 1、硬件環境 CPU：酷睿i5 內存：4GB 硬盤：1T 2、軟件環境 操作系統：Windows10 編程環境：jdk 編程語言：Java 三、實驗內容：在Prim算法與Kruskal算法中任選一種求解最小生成樹問題。 1、你選擇的是：Prim算法 2、數據結構 （1）圖的數據結構——圖結構是研究數據元素之間的多對多的關系。在這種結構中，任意兩個元素之間可能存在關系，即結點之間的關系可以是任意的，圖中任意元素之間都可能相關。 圖形結構——多個對多個，如 （2）樹的數據結構——樹結構是研究數據元素之間的一對多的關系。在這種結構中，每個元素對下(層)可以有0個或多個元素相聯系，對上(層)只有唯一的一個元素相關，數據元素之間有明顯的層次關系。樹形結構——一個對多個，如 3、算法偽代碼 Prim(G,E,W)輸入：連通圖G 輸出：G的最小生成樹T 1.S←{1};T=? 2.While V-S ≠? do 3.從V-S中選擇j使得j到S中頂點的邊e的權最小；T←T∪{e} 4.S←S∪{j} 3、算法分析 時間復雜度：O(n)空間復雜度：O(n^2) 4、關鍵代碼（含注釋） package Prim; import java.util.*;publicclass Main { staticintMAXCOST=Integer.MAX_VALUE; staticint Prim(intgraph[][], intn){ /* lowcost[i]記錄以i為終點的邊的最小權值，當lowcost[i]=0時表示終點i加入生成樹 */ intlowcost[]=newint[n+1]; /* mst[i]記錄對應lowcost[i]的起點，當mst[i]=0時表示起點i加入生成樹 */ intmst[]=newint[n+1]; intmin, minid, sum = 0; /* 默認選擇1號節點加入生成樹，從2號節點開始初始化 */ for(inti = 2;i<= n;i++){ /* 標記1號節點加入生成樹 */ mst[1] = 0; /* n個節點至少需要n-1條邊構成最小生成樹 */ for(inti = 2;i<= n;i++){ /* 找滿足條件的最小權值邊的節點minid */ for(intj = 2;j<= n;j++){ /* 輸出生成樹邊的信息:起點，終點，權值 */ System.out.printf(“%c1, minid + 'A''A' + 1;intj = chy-'A' + 1;graph[i][j] = cost;graph[j][i] = cost;for(intj = 1;j<= n;j++){ } graph[i][j] = MAXCOST;} } System.out.println(”Total:"+cost);} } 5、實驗結果（1）輸入 （2）輸出 最小生成樹的權值為： 生成過程： (a) (b) (d) (e) (c) 四、實驗總結（心得體會、需要注意的問題等） 這次實驗，使我受益匪淺。這次實驗我選擇了Prim算法來求出樹的最小生成樹，在編寫代碼的過程中，我對Prim算法有了更深的了解，也使我對算法設計與分析更有興趣，今后一定要更努力的學習這門課。 《算法設計與分析》 實驗報告 班級 姓名 學號 ****年**月**日 目錄 實驗一 二分查找程序實現…………………………………………………………………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第二篇：實驗3 貪心算法（定稿）
第三篇：算法實驗報告
第四篇：RSA算法實驗報告
第五篇：銀行家算法實驗報告
點擊咨詢 