1、內(nèi)江師范學院數(shù)據(jù)結構與算法設計課程設計實 驗 報 告 冊編制 算法設計課題組 審定 曾意專業(yè)： 信息與計算科學 班級： 2012 級 6 班學號： 20120241242 姓名： 楊浩天 數(shù)學與信息科學學院2014年9月說 明1. 學生在做實驗之前必須要準備實驗，主要包括預習與本次實驗相關的理論知識，熟練與本次實驗相關的軟件操作，收集整理相關的實驗參考資料，要求學生在做實驗時能帶上充足的參考資料；若準備不充分，則學生不得參加本次實驗，不得書寫實驗報告；2. 要求學生要認真做實驗，主要是指不得遲到、早退和曠課，在做實驗過程中要嚴格遵守實驗室規(guī)章制度，認真完成實驗內(nèi)容，極積主動地向?qū)嶒灲處熖釂柕龋?/p>

2、若學生無故曠課，則本次實驗等級計為D；3. 學生要認真工整地書寫實驗報告，實驗報告的內(nèi)容要緊扣實驗的要求和目的，不得抄襲他人的實驗報告；4. 實驗成績評定分為A+、A、A-、B+、B、C、D各等級。根據(jù)實驗準備、實驗態(tài)度、實驗報告的書寫、實驗報告的內(nèi)容進行綜合評定，具體對應等級如下：完全符合、非常符合、很符合、比較符合、基本符合、不符合、完全不符合。實驗名稱： 算法設計基礎實驗（實驗一） 指導教師： 牟廉明，劉芳 實驗時數(shù)： 4 實驗設備：安裝了VC+計算機實驗日期： 年 月 日 實驗地點： 第五教學樓北802實驗目的：掌握算法設計的基本原理，熟悉算法設計的基本步驟及其軟件實現(xiàn)。實驗準備：1.

3、 在開始本實驗之前，請復習相關實驗內(nèi)容；2. 需要一臺準備安裝Windows XP Professional操作系統(tǒng)和裝有VC+6.0的計算機。實驗內(nèi)容：求n至少為多大時，n個1組成的整數(shù)能被2013整除。實驗過程：1.1算法思想2013=61*33,6個1能夠整除33，尋找滿足n個1能夠整除61的n即可。1.2 算法步驟1.定義變量y儲存余數(shù)，i儲存1的個數(shù)，m為被除數(shù)，初始化為111111；2.如果被除數(shù)能夠除盡61，輸出i; 如果被除數(shù)不能夠除盡61，while繼續(xù)循環(huán),m=y*1000000+111111,i+;3.重復2，直到找到滿足條件的m為止，輸出i;1.3算法實現(xiàn)（C+程序代碼

4、）#include<iostream>using namespace std;int main() int y,m,i; i=6; m=111111; while(y!=0) m=y*1000000+111111; y=m%61; i=i+6; cout<<i<<endl; return 0;1.4 算法分析時間復雜度為O(n);實驗總結（由學生填寫）：通過該實驗發(fā)現(xiàn)，任何問題不要盲目的使用蠻力法，一定要化蠻力為巧力，這樣既可以減少程序的時間復雜度，也能得到較精確的結果。并且在以后的解決問題的過程中，一定要多分析，多思考。 實驗等級評定： 實驗名稱： 蠻力法

5、實驗分式化簡（實驗二） 指導教師：牟廉明，劉芳實驗時數(shù)： 4 實驗設備：安裝了VC+的計算機實驗日期： 年 月 日 實驗地點： 第五教學樓北802 實驗目的：掌握蠻力法的基本思想和方法，熟悉搜索法的軟件實現(xiàn)。實驗準備：1在開始本實驗之前，請回顧教材的相關內(nèi)容；2需要一臺準備安裝Windows XP Professional操作系統(tǒng)和裝有數(shù)學軟件的計算機。實驗內(nèi)容：設計算法，將一個給定的真分數(shù)化簡為最簡分數(shù)形式，例如，將6/8化簡為3/4。實驗過程：1.1算法思想首先對于普通整數(shù)；可以先利用歐幾里得算法求出最大公約數(shù)，然后再講分子分母用最大公約數(shù)作除，即可求出最簡真分數(shù)。1.2 算法步驟輸入：約

6、分前的兩個整數(shù)分子和分母輸出：約分后的分子分母1.r=m%n;2.循環(huán)直到r=0;3.m=n;n=r;r=m%n;4.a/n;b/n;5.輸出b/a;1.3算法實現(xiàn)（C+程序代碼）#include<iostream>using namespace std;int main() long int a, b, r;cout<<"請輸入真分數(shù)的分母和分子："cin>>a>>b;long int m=a;long int n=b;r = a % b;while (r!=0) a = b;b= r;r = a%b;a=m/b;b=n/b

7、;cout<<"原分數(shù)的最簡分數(shù)為:"<<b<<"/"<<a<<endl;return 0;1.4 算法分析時間復雜度為o(n).實驗總結（由學生填寫）： 此次實驗較為簡單，也較為基礎。但需注意的是，即使是很簡單的問題，也需要注意細節(jié)，尤其是在定義長整型的時候，不要單獨的只定義為整型。 實驗等級評定： 實驗名稱： 分治法實驗循環(huán)移位（實驗三） 指導教師：牟廉明，劉芳實驗時數(shù)： 4 實驗設備：安裝了VC+的計算機 實驗日期： 年 月 日 實驗地點：第五教學樓北802 實驗目的：通過本次實驗，讓學生

8、掌握分治法的基本思想和技巧，并學會如何用C+軟件來實現(xiàn)實驗準備：1在開始本實驗之前，請回顧教科書的相關內(nèi)容；2需要一臺準備安裝Windows XP Professional操作系統(tǒng)和裝有C+軟件的計算機。實驗內(nèi)容：設計分治算法，實現(xiàn)將數(shù)組An中所有元素循環(huán)左移k個位置，要求時間復雜度為O（n），空間復雜度為O（1）。例如，對abcdefgh循環(huán)左移3位得到defghabc。實驗過程：1.1算法思想對于第6題，用分治法進行求解的話，若是采用循環(huán)賦值的方式，如果字符的個數(shù)和左移的位數(shù)成倍數(shù)關系，那么算法就比較容易實現(xiàn)，但是如果不成比例關系，算法寫起來就比較麻煩，所以，用了另一種方式，進行三次對稱交

9、換就可以完成算法。1.2 算法步驟1.輸入：一個數(shù)組和左移位數(shù)2.編寫兩個函數(shù)，一個是對稱交換函數(shù)1，另一個是調(diào)用函數(shù)2，用函數(shù)2三次調(diào)用函數(shù)1，完成整個對稱交換過程。3.調(diào)用函數(shù)24.輸出：左移后的數(shù)組1.3算法實現(xiàn)（C+程序代碼）#include<iostream>using namespace std;void fun(char *a,int m,int k) int temp;int i,j;for(i=m,j=k;i<=k;i+,j-) if(i<=(m+k)/2)temp=ai;ai=aj;aj=temp;void xun(char a,int k,int

10、n)/（函數(shù)2）第二個調(diào)用函數(shù)，調(diào)用函數(shù)1fun(a,0,k-1);/第一次調(diào)用函數(shù)1，將(abc)對稱交換得到(cba),最后a為(cbadefgh)fun(a,k,n-1);/第二次調(diào)用函數(shù)1，將(defgh)對稱交換得到(hgfed),最后a為(cbahgfed)fun(a,0,n-1);/第三次調(diào)用函數(shù)1，將(cbadefgh)對稱交換得到(defghabc),即最后a為(defghabc)int main()char a1000; cout<<"請輸入一個數(shù)組:"<<endl;gets(a);/用cin>>a;也可以喲，不過配套

11、的比較好看！int k;cout<<"請輸入左移位數(shù):"<<endl;cin>>k; int n=strlen(a);xun(a,k,n);puts(a);/用cout<<a<<endl;也可以喲，不過配套的比較好看！return 0;1.4 算法分析存在如下遞推式，T(n)=2T(n/2)+n, 時間復雜性為O(nlog2n) 實驗總結（由學生填寫）： 分治法的主要思想是分而治之，在遇到一個規(guī)模比較大問題時，我們不應該直接入手，通過簡單的循環(huán)語句解決，而應該對其分段對局部進行考慮，通過對局部得到整體的結果。但在此

12、次實驗中，學會了對分治法的簡單應該，但要對其加深鞏固，還應該對此類問題的相關習題多多去練習，多多去領悟。 實驗等級評定： 實驗名稱： 回溯法0/1背包問題（實驗四） 指導教師：牟廉明，劉芳實驗時數(shù)： 4 實驗設備：安裝了VC+的計算機 實驗日期： 年 月 日 實驗地點：第五教學樓北802 實驗目的：熟悉回溯法的基本思想和實現(xiàn)方法，掌握如何用C+實現(xiàn)相關算法。實驗準備：1. 在開始本實驗之前，請回顧教科書的相關內(nèi)容；2. 需要一臺準備安裝Windows XP Professional操作系統(tǒng)和裝有C+的計算機。實驗內(nèi)容：給定背包容量W=20，以及6個物品，重量分別為（5，3，2，10，4，2），

13、價值分別為（11，8，15，18，12，6）。請用回溯法求解上述0/1背包問題。實驗過程：1.1算法思想首先把物品單價價值排序，并確定上界函數(shù)，在搜索二叉樹中利用上界函數(shù)對其進行剪枝，最終確定最優(yōu)解。1.2 算法步驟1.定義變量2.編寫函數(shù) knapsack() ，用于將物品按單位價值排序編寫函數(shù) bound(int i)，用于計算上界函數(shù)編寫函數(shù) backtrack(int i) ，回溯函數(shù)，用于搜索二叉樹。3.輸出解決方案1.3算法實現(xiàn)（C+程序代碼）#include<iostream>/這個是只找到了一個可行解就返回了值(其實還可能有其他的解)using namespace

14、std;#include<time.h>/計算程序運行時間的頭函數(shù)int n;/物品數(shù)量double c;/背包容量double v100;/各個物品的價值double w100;/各個物品的重量double cw = 0.0;/當前背包重量double cp = 0.0;/當前背包中物品價值double bestp = 0.0;/當前最優(yōu)價值double perp100;/單位物品價值排序后int order100;/物品編號int put100;/設置是否裝入/按單位價值排序void knapsack() int i,j; int temporder = 0; double t

15、emp = 0.0; for(i=1;i<=n;i+) perpi=vi/wi; for(i=1;i<=n-1;i+)/冒泡排序思想：比較n-1次，第一次從第一個數(shù)到最后一個數(shù)，第二次從第二個數(shù)到最后一個數(shù). for(j=i+1;j<=n;j+)/按照單位重量價值進行冒泡排序，同時要將重量，價值，序號進行相同排序 if(perpi<perpj)/冒泡排序perp,order,sortv,sortw temp = perpi; perpi=perpi; perpj=temp; temporder=orderi; orderi=orderj; orderj=temporde

16、r; temp = vi; vi=vj; vj=temp; temp=wi; wi=wj; wj=temp; /計算上界函數(shù)double bound(int i) double leftw= c-cw;/leftw = 背包容量 - 當前背包容量 double b = cp; /b = 當前背包中物品價值 while(i<=n&&wi<=leftw) leftw-=wi;/將第i件物品裝入背包 b+=vi; i+; if(i<=n) b+=vi/wi*leftw;/如果要切分的情況下 return b;/回溯函數(shù)void backtrack(int i) do

17、uble bound(int i); if(i>n) bestp = cp; return; if(cw+wi<=c) cw+=wi; cp+=vi; puti=1; backtrack(i+1); cw-=wi; cp-=vi; if(bound(i+1)>bestp)/符合條件搜索右子數(shù) backtrack(i+1);int main()clock_t nTimeStart;/開始時間clock_t nTimeStop;/結束時間nTimeStart=clock(); int i; /printf("請輸入物品的數(shù)量和容量："); /scanf(&qu

18、ot;%d %lf",&n,&c);cout<<"請輸入物品的數(shù)量和容量："cin>>n>>c; / printf("請輸入物品的重量和價值：");cout<<"請輸入物品的重量和價值："<<endl; for(i=1;i<=n;i+) /printf("第%d個物品的重量：",i); / scanf("%lf",&wi);cout<<"第"<<i<<"個物品的重量和價值：" cin>>wi>>vi;/ printf("價值是："); /scanf("%lf",&vi); orderi=i; knapsack(); backtrack(1