算法實驗報告

《算法設計與分析》上機試驗匯報一、分治與遞歸1、問題描述 編寫程序，實現(xiàn)線性時間內(nèi)選擇n個元素中位數(shù)算法。并對于不一樣n，測試平均時間效率。2、問題分析 本問題屬于線性選擇問題一個特例，能夠使用分治法進行求解。其基本思想是模仿快速排序方法，對輸入數(shù)組進行劃分，求出中位數(shù)所在子數(shù)組，然后用遞歸方法進行求解，最終能夠求得問題解。3、算法設計將n個輸入元素依照隨機選擇基準劃分成2個子數(shù)組，a[p:r]被劃分成a[p:i]和a[i+1:r]兩組，使得a[p:i]中每個元素都小于a[i+1:r]中元素。接著算法計算子數(shù)組a[p:i]中元素個數(shù)j，假如k<=j，則a[p:r]中第k個小元素落在子數(shù)組a[p:i]中元素均小于要找第k小元素，所以要找a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。按照上述方法遞歸執(zhí)行，直到當前數(shù)組中只剩下一個元素，就能夠得到問題解。4、算法實現(xiàn) #include"iostream.h"#include"stdlib.h"#include"time.h"#include<sys/types.h>#include<sys/timeb.h>#include"windows.h"#include<stdio.h>intrandomizedSel(int*,int,int,int);voidmain(){ srand((unsignedint)time(NULL)); _timebtime0,time1; intn; cout<<"請輸入數(shù)組長度："; cin>>n; cout<<"請輸入數(shù)組每一個數(shù)："<<endl; int*a=newint[n]; for(inti=0;i<n;i++) cin>>a[i]; DWORDstime=GetTickCount(); _ftime(&time0); intresult=randomizedSel(a,0,n-1,(n+1)/2); DWORDEtime=GetTickCount(); _ftime(&time1); cout<<"結果為："<<result<<endl; cout<<litm*1000-litm*1000<<endl; cout<<Etime-stime<<endl;}voidswap(int*a,inti,intj){ inttemp=a[i]; a[i]=a[j]; a[j]=temp;}intpartition(int*a,intp,intr){ inti=p,j=r+1; intx=a[p]; while(1) { while(a[++i]<x&&i<r); while(a[--j]>x); if(i>=j)break; swap(a,i,j); } a[p]=a[j]; a[j]=x; returnj;}intrandomizedpar(int*a,intp,intr){ inti=rand()%(r-p+1)+p; swap(a,i,p); returnpartition(a,p,r);}intrandomizedSel(int*a,intp,intr,intk){ if(p==r) returna[p]; inti=randomizedpar(a,p,r); intj=i-p+1; if(k<=j)returnrandomizedSel(a,p,i,k); elsereturnrandomizedSel(a,i+1,r,k-j);}5、運行結果運行結果以下列圖所表示：經(jīng)過測試，當輸入數(shù)組長度不大時，執(zhí)行時間幾乎為零，當輸入數(shù)組很大時，執(zhí)行時間隨之增大，與數(shù)組長度成正相關。二、動態(tài)規(guī)劃1、問題描述 實現(xiàn)0/1背包問題求解算法。2、問題分析能夠?qū)⑸鲜鰡栴}轉(zhuǎn)化為以下數(shù)學表示式形式：求：，滿足以下條件：記m（i，j）表示背包容量為j，可選物品為i，i+1，.....，n時0-1背包問題最優(yōu)值，則能夠得到以下算式：則m（1，c）即為所求最優(yōu)值3、算法設計將問題分析中m（i，j）用二維數(shù)組m[][]存放，則能夠得到問題求解。4、算法實現(xiàn)#include<stdio.h>#include<stdlib.h>#include<iostream>usingnamespacestd;intmax(intx,inty);intmain(intargc,char*argv[]){//定義intn,c,w[105],v[105],m[105][105];inti,j,jmax;cout<<"請輸入物品數(shù)量與背包容量:"<<endl;cin>>n>>c;//最終一層計算cout<<"輸入各個物品重量：";for(i=1;i<=n;i++)cin>>w[i];cout<<"輸入各個物品價值：";for(i=1;i<=n;i++)cin>>v[i];jmax=w[n-1]<c?w[n-1]:c;for(j=0;j<=jmax;j++)m[n][j]=0;for(j=w[n];j<=c;j++)m[n][j]=v[n];//中間計算for(i=n-1;i>1;i--){ jmax=w[i-1]<c?w[i-1]:c;for(j=0;j<=jmax;j++)m[i][j]=m[i+1][j];for(j=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}//第一層計算m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);//輸出cout<<"最優(yōu)背包價值為:"<<m[1][c]<<endl;system("pause");return0;}intmax(intx,inty){intt;if(x>y)t=x;elset=y;returnt;}5、運行結果 執(zhí)行結果以下列圖所表示：三、貪心法1、問題描述 給定n位整數(shù)a，去掉其中任意k<=n個數(shù)字后，剩下數(shù)字按原次序排列組成一個新正整數(shù)。對于給定n位正整數(shù)a和正整數(shù)k，設計一個算法找出剩下數(shù)字組成新數(shù)最小刪數(shù)方案。2、問題分析本題能夠用貪心算法求解，因為左邊數(shù)比右邊數(shù)具備更大位值，所以應該從左邊開始遍歷，當碰到一個右邊數(shù)大于左邊數(shù)時，刪去右邊數(shù)，能夠得到刪除一個數(shù)時最大數(shù)。這么，經(jīng)過數(shù)次這么遍歷，就能夠問題解了。3、算法設計算法對數(shù)組進行掃描遍歷，當碰到第一個右邊數(shù)比左邊數(shù)大時候，就把右邊數(shù)據(jù)刪除，同時將后面每一位數(shù)據(jù)按位向前移動一位，這么就完成了一次遍歷。執(zhí)行上述步驟k次，將最終得到刪除后數(shù)組。4、算法實現(xiàn)#include"iostream.h"#include"string.h"voidgreedy(char*,int);voidmain(){charnumber[30];intk;cout<<"請輸入一個正整數(shù)：";cin>>number;cout<<"請輸入刪除位數(shù)：";cin>>k;greedy(number,k);cout<<"刪數(shù)后結果為："<<number<<endl;}voidgreedy(char*number,intk){ for(inti=1;i<=k;i++) { intj=0; while(number[j]) { j++; if(number[j-1]<=number[j])//若前一位小于后一位，則繼續(xù)執(zhí)行 continue; while(number[j])//若前一位大于后一位，則刪除前一位，后面數(shù)順次前移一位 { number[j-1]=number[j]; j++; } number[j-1]=number[j]; } }}5、運行結果執(zhí)行結果以下列圖所表示四、回溯/分支限界法1、問題描述 某售貨員要到若干城市去推銷商品，已知各城市之間旅程（或運費）。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，最終回到駐地路線，使總旅程（或總旅費）最小。2、問題分析本問題能夠使用回溯法進行求解，該問題解空間書是一顆排列樹，從樹根節(jié)點到任意葉子節(jié)點路徑定義了圖中一條周游路線。用深度優(yōu)先方式對排列數(shù)進行遍歷，添加剪枝函數(shù)降低遍歷中節(jié)點數(shù)。3、算法設計在遞歸算法匯中，當i=n時，當前擴展節(jié)點是排列數(shù)葉節(jié)點父節(jié)點。此時算法檢測圖G是否存在一條從頂點x[n-1]到頂點x[n]邊和一條從頂點x[n]到頂點1邊。假如這兩條邊都存在，則找到一條旅行售貨員回路。此時，算法還需判斷這條回路費用是否優(yōu)于當前已找到最有回路費用bestc，假如是，則必須更新當前最優(yōu)值bestc和當前最優(yōu)解bestx。當i<n時，當前擴展節(jié)點位于排列數(shù)第i-1層。圖G中存在從頂點x[i-1]到頂點x[i]邊時，x[1:i]組成圖G一條路徑，且當x[1:i]費用小于當前最優(yōu)值時，算法進入排列樹第i層，不然，將漸趨對應子樹。按照上述方法，遍歷整個排列數(shù)，就能夠得到問題最優(yōu)解了。4、算法實現(xiàn)#include"iostream.h"#defineUNTO-1floatbestc=-1;intn;voidbacktrack(int,float**,int*,int*,float);voidswap(int*,int,int);voidmain(){ cout<<"請輸入城市數(shù)目："; cin>>n; float**a=newfloat*[n]; for(inti=0;i<n;i++) a[i]=newfloat[n]; cout<<"請輸入城市之間距離（用-1表示不可達）："<<endl; for(i=0;i<n;i++) for(intj=0;j<n;j++) cin>>a[i][j]; int*x=newint[n]; for(i=0;i<n;i++) { x[i]=i; } int*bestx=newint[n]; floatcc=0; backtrack(1,a,x,bestx,cc); cout<<"最短路徑為："<<bestc<<endl; cout<<"最優(yōu)路徑為："; for(i=0;i<n;i++) cout<<bestx[i]+1<<''; cout<<"1"<<endl;}voidbacktrack(intt,float**a,int*x,int*bestx,floatcc){ if(t==n-1) { if(a[x[t-1]][x[t]]!=UNTO&&a[x[t]][1]!=UNTO &&(bestc==UNTO||cc+a[x[t-1]][x[t]]+a[x[t]][1]<bestc)) { for(inti=0;i<n;i++) bestx[i]=x[i]; bestc=cc+a[x[t-1]][x[t]]+a[x[t]][0]; } } else { for(inti=t;i<n;i++) if(a[x[t-1]][x[t]]!=UNTO&& (bestc==UNTO||cc+a[x[t-1]][x[t]]+a[x[t]][1]<bestc)) { swap(x,t,i); cc=cc+a[x[t-1]][x[t]]; backtrack(t+1,a,x,bestx,cc); cc=cc-a[x[t-1]][x[t]]; swap(x,t,i); }