太原理工大學(xué)算法實(shí)驗(yàn)報(bào)告

./本科實(shí)驗(yàn)報(bào)告課程名稱：算法設(shè)計(jì)與分析實(shí)驗(yàn)項(xiàng)目：算法設(shè)計(jì)與分析實(shí)驗(yàn)實(shí)驗(yàn)地點(diǎn)：致遠(yuǎn)樓403專業(yè)班級(jí)：學(xué)號(hào)：學(xué)生：指導(dǎo)教師：2017年3月實(shí)驗(yàn)一分治法合并排序一、實(shí)驗(yàn)?zāi)康?.掌握合并排序的基本思想2.掌握合并排序的實(shí)現(xiàn)方法3.學(xué)會(huì)分析算法的時(shí)間復(fù)雜度4.學(xué)會(huì)用分治法解決實(shí)際問題二、實(shí)驗(yàn)容隨機(jī)產(chǎn)生一個(gè)整型數(shù)組,然后用合并排序?qū)⒃摂?shù)組做升序排列,要求輸出排序前和排序后的數(shù)組。三、實(shí)驗(yàn)環(huán)境程序設(shè)計(jì)語(yǔ)言：c++編程工具：microsoftvisualstudio2013四、程序代碼#include"stdafx.h"#include<iostream>#include<cassert>#include"SortTestHelper.h"usingnamespacestd;template<typenameT>voidmergeSort<Tarr[],intn>{_mergeSort<arr,0,n-1>;}template<typenameT>void__mergeSort<Tarr[],intl,intr>{if<l>=r> return; intmid=<l+r>/2; __mergeSort<arr,l,mid>; __mergeSort<arr,mid+1,r>; if<arr[mid]>arr[mid+1]> __merge<arr,l,mid,r>;}template<typenameT>void__merge<Tarr[],intl,intmid,intr>{ T*aux=newT[r-l+1]; for<inti=l;i<=r;i++> aux[i-l]=arr[i]; inti=l,j=mid+1; for<intk=l;k<=r;k++> {if<i>mid> { arr[k]=aux[j-l]; j++; } elseif<j>r> { arr[k]=aux[i-l]; i++; } elseif<aux[i-l]<aux[j-l]> { arr[k]=aux[i-l]; i++; } else{ arr[k]=aux[j-l]; j++; } } delete[]aux;}int_tmain<intargc,_TCHAR*argv[]>{ intn=10; int*arr=SortTestHelper::generateRandomArray<n,0,n>; cout<<"未排序的數(shù)組為："; for<intj=0;j<10;j++> cout<<arr[j]<<""; cout<<endl; mergeSort<arr,10>; cout<<"經(jīng)過排序的數(shù)組為："; for<inti=0;i<9;i++> cout<<arr[i]<<""; cout<<endl;}#include"stdafx.h"#include<iostream>#include<ctime>#include<cassert>usingnamespacestd;namespaceSortTestHelper{int*generateRandomArray<intn,intrandL,intrandR>{ assert<randL<=randR>; int*arr=newint[n]; for<inti=0;i<n;i++> arr[i]=rand<>%<randR-randL+1>+randL; returnarr;}}五、實(shí)驗(yàn)結(jié)果截圖六、實(shí)驗(yàn)總結(jié)一定要先找到遞歸函數(shù)式后,設(shè)計(jì)遞歸程序?qū)嶒?yàn)二貪心法多機(jī)調(diào)度實(shí)驗(yàn)?zāi)康?.掌握貪心算法的基本思想2.掌握貪心算法的典型問題求解3.進(jìn)一步多機(jī)調(diào)度的基本思想和算法設(shè)計(jì)方法4.學(xué)會(huì)用貪心法分析和解決實(shí)際問題實(shí)驗(yàn)容設(shè)計(jì)貪心算法實(shí)現(xiàn)作業(yè)調(diào)度,要求按作業(yè)調(diào)度順序輸出作業(yè)序列。如已知n=8,效益p=<35,

30,

25,

20,

15,

10,

5,

1>,時(shí)間期限

d=<4,

2,

4,

5,

6,

4,

5,

7>,求該條件下的最大效益。實(shí)驗(yàn)環(huán)境程序設(shè)計(jì)語(yǔ)言：c++編程工具：microsoftvisualstudio2013方法描述和程序代碼#include"stdafx.h"#include"iostream"usingnamespacestd;int_tmain<intargc,_TCHAR*argv[]>{doublework[99],time[99],t,w;doubletemp[99],usetemp[99],a,s=0;intA[99];cout<<"作業(yè)數(shù)為<x<99>:"<<endl;cin>>w; cout<<"作業(yè)收益為:"<<endl;for<inti=0;i<w;i++>{cin>>work[i];} cout<<"作業(yè)收益："<<endl;for<inti=0;i<w;i++>{cout<<""<<work[i]<<"";} cout<<endl; cout<<"每個(gè)作業(yè)的時(shí)限為:"<<endl;for<inti=0;i<w;i++>{cin>>time[i];} cout<<"作業(yè)時(shí)限："<<endl;for<inti=0;i<w;i++>{cout<<""<<time[i]<<"";} cout<<endl; cout<<"總作業(yè)時(shí)限為:"<<endl; cin>>t;//初始化錄入數(shù)據(jù)for<inti=0;i<w;i++>{temp[i]=work[i]/time[i];usetemp[i]=temp[i];}//平均時(shí)間盈利cout<<"作業(yè)平均時(shí)間盈利排序?yàn)椋?<<endl;for<intm=0;m<w;m++>{ a=temp[0],A[m]=0;for<inti=0;i<w;i++>if<a<temp[i]>{ A[m]=i;a=temp[i];} temp[A[m]]=0;cout<<""<<A[m]<<""; }//作業(yè)平均時(shí)間盈利排序cout<<endl; cout<<"可進(jìn)行的作業(yè)有："<<endl;for<inti=0;i<w;i++>{doublex=s+time[A[i]];if<x<t>{ s=s+time[A[i]];cout<<""<<A[i]<<"";}} }五、實(shí)驗(yàn)結(jié)果截圖六、實(shí)驗(yàn)總結(jié)貪心算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇。實(shí)驗(yàn)三動(dòng)態(tài)規(guī)劃法求多段圖問題實(shí)驗(yàn)?zāi)康?.掌握動(dòng)態(tài)規(guī)劃算法的基本思想2.掌握多段圖的動(dòng)態(tài)規(guī)劃算法3.選擇鄰接表或鄰接矩陣方式來存儲(chǔ)圖4.分析算法求解的復(fù)雜度。實(shí)驗(yàn)容設(shè)G=<V,E>是一個(gè)帶權(quán)有向圖,其頂點(diǎn)的集合V被劃分成k>2個(gè)不相交的子集Vi,1<i<=k,其中V1和Vk分別只有一個(gè)頂點(diǎn)s〔源和一個(gè)頂點(diǎn)t〔匯。圖中所有邊的始點(diǎn)和終點(diǎn)都在相鄰的兩個(gè)子集Vi和Vi+1中。求一條s到t的最短路線。參考講義p136圖5-24中的多段圖,試選擇使用向前遞推算法或向后遞推算法求解多段圖問題。實(shí)驗(yàn)環(huán)境程序設(shè)計(jì)語(yǔ)言：c++編程工具：microsoftvisualstudio2013算法描述和程序代碼#include"stdafx.h"#include<iostream>usingnamespacestd;#defineINFTY1000structT{ intadjVex; intw; structT*nextArc;};classGraph{private: T**a; int*p; intn;public: Graph<intn>{this->n=n;p=newint[n];a=newT*[n];for<inti=0;i<n;i++>a[i]=newT;} voidGetT<int**m>; intfp<intk>; voidprint<intk>;};voidGraph::print<intk>{ intc=fp<k>; cout<<"最短路徑權(quán)值："<<c<<endl; cout<<"最短路徑："<<endl; for<inti=0;i<k-1;i++> cout<<p[i]<<"-->"<<p[i+1]<<endl;}intGraph::fp<intk>{ intc,*cost=newint[n];intq,*d=newint[n]; cost[n-1]=0; d[n-1]=-1; for<intj=n-2;j>=0;j-->{ intmin=INFTY; for<T*r=a[j]->nextArc;r;r=r->nextArc>{ intv=r->adjVex; if<r->w+cost[v]<min>{ min=r->w+cost[v]; q=v; } } cost[j]=min; d[j]=q; } p[0]=0;p[k-1]=n-1;c=cost[0]; for<intj=1;j<=k-2;j++> p[j]=d[p[j-1]]; delete[]cost; delete[]d; returnc;}voidGraph::GetT<int**m>{ T*x,*p,*q; for<inti=0;i<n;i++>{ p=q=a[i]; for<intj=0;j<n;j++>{ if<m[i][j]!=0>{ x=newT; x->adjVex=j; x->w=m[i][j]; p->nextArc=x; p=p->nextArc; } } p->nextArc=NULL; }}int_tmain<intargc,_TCHAR*argv[]>{ int**m; Graphq<12>; m=newint*[12]; for<inti=0;i<12;i++> m[i]=newint[12]; cout<<"圖的各點(diǎn)見的權(quán)值為："<<endl; for<inti=0;i<12;i++> for<intj=0;j<12;j++> cin>>m[i][j]; q.GetT<m>; intk; cout<<"到第幾個(gè)結(jié)點(diǎn)的最短路徑:"; cin>>k; q.print<k>; for<inti=0;i<12;i++> delete[]m[i]; deletem; return0;}實(shí)驗(yàn)結(jié)果截圖實(shí)驗(yàn)總結(jié)動(dòng)態(tài)規(guī)劃法應(yīng)用于子問題重疊的情況,與分治法類似。實(shí)驗(yàn)四回溯法求n皇后問題實(shí)驗(yàn)?zāi)康恼莆栈厮菟惴ǖ幕舅枷胪ㄟ^n皇后問題求解熟悉回溯法使用蒙特卡洛方法分析算法的復(fù)雜度實(shí)驗(yàn)容要求在一個(gè)8*8的棋盤上放置8個(gè)皇后,使得它們彼此不受"攻擊"。兩個(gè)皇后位于棋盤上的同一行、同一列或同一對(duì)角線上,則稱它們?cè)诨ハ喙簟，F(xiàn)在要找出使得棋盤上8個(gè)皇后互不攻擊的布局。實(shí)驗(yàn)環(huán)境程序設(shè)計(jì)語(yǔ)言：c++編程工具：microsoftvisualstudio2013算法描述和程序代碼#include"stdafx.h"#include<stdlib.h>#defineN4intcolumn[N+1];intrup[2*N+1];intlup[2*N+1];intqueen[N+1]={0};intnum;//解答編號(hào)確定voidbacktrack<int>;int_tmain<intargc,_TCHAR*argv[]>{inti;num=0;for<i=1;i<=N;i++>column[i]=1;for<i=1;i<=2*N;i++>rup[i]=lup[i]=1;backtrack<1>;return0;}//遞回求解voidshowAnswer<>{intx,y;printf<"\n解答%d\n",++num>;for<y=1;y<=N;y++>{for<x=1;x<=N;x++>{if<queen[y]==x>{printf<"Q">;}else{printf<".">;}}printf<"\n">;}}//GUI顯示voidbacktrack<inti>{intj;if<i>N>{showAnswer<>;}else{for<j=1;j<=N;j++>{