算法實(shí)驗(yàn)報(bào)告

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