算法實(shí)驗(yàn)(矩陣連乘)

攀枝花學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程：計(jì)算機(jī)算法實(shí)驗(yàn)實(shí)驗(yàn)項(xiàng)目：矩陣連乘實(shí)驗(yàn)日期：2013.4.9系：數(shù)學(xué)與計(jì)算機(jī)學(xué)院班級(jí)：軟件工程姓名：馮斌學(xué)號(hào)：201010804004指導(dǎo)教師：銀星成績(jī)：【實(shí)驗(yàn)?zāi)康模骸坷脛?dòng)態(tài)規(guī)劃掌握矩陣連乘算法，計(jì)算矩陣連乘最優(yōu)次序。掌握用備忘錄方法計(jì)算矩陣連乘最優(yōu)次序。掌握vc++6.0環(huán)境下程序的編寫(xiě)和調(diào)試?！緦?shí)驗(yàn)設(shè)備器材：】pc機(jī)一套vc++6.0相應(yīng)編譯軟件【實(shí)驗(yàn)原理：】 【實(shí)驗(yàn)內(nèi)容：】編寫(xiě)相應(yīng)算法源程序在vc++6.0環(huán)境下調(diào)試通過(guò)運(yùn)行程序計(jì)算最優(yōu)次序。

程序代碼如下：#include<iostream>usingnamespacestd;#defineN100intn,q;intm[N][N],s[N][N],p[N+1];voidmatrixChain(){//動(dòng)態(tài)規(guī)劃計(jì)算最優(yōu)值算法 for(inti=1;i<=n;i++) { m[i][i]=0; } for(intr=2;r<=n;r++) {//對(duì)角線循環(huán) for(inti=1;i<=n-r+1;i++) {//行循環(huán)intj=r+i-1;//列的控制,找m[i][j]的最小值，先初始化一下，令k=im[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;//k從i+1到j(luò)-1循環(huán)找m[i][j]的最小值for(intk=i+1;k<j;k++) {inttemp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(temp<m[i][j]) {m[i][j]=temp;//s[][]用來(lái)記錄在子序列i-j段中，在k位置處斷開(kāi)能得到最優(yōu)解 s[i][j]=k; }} } }}intRecur(inti,intj)//直接遞歸計(jì)算最優(yōu)值{ if(i==j){ return0; }intu=Recur(i,i)+Recur(i+1,j)+p[i-1]*p[i]*p[j];//遞歸s[i][j]=i;for(intk=i+1;k<j;k++){intt=Recur(i,k)+Recur(k+1,j)+p[i-1]*p[k]*p[j];//從k處斷開(kāi)，分別求得每次的數(shù)乘次數(shù)if(t<u)//返回t,k中較小的值，并記錄斷點(diǎn)處k { u=t; s[i][j]=k; }}returnu;}intLook(inti,intj)//備忘錄計(jì)算最優(yōu)值{ if(m[i][j]>0) { returnm[i][j]; } if(i==j) return0; intu=Look(i,i)+Look(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i; for(intk=i+1;k<j;k++) { intt=Look(i,k)+Look(k+1,j)+p[i-1]*p[k]*p[j];//遞歸 if(t<u) { u=t;//從k處斷開(kāi)，分別求得每次的數(shù)乘次數(shù) s[i][j]=k;//返回t,k中較小的值，并記錄斷點(diǎn)處k } } m[i][j]=u; returnu;}voidTraceback(inti,intj){//輸出矩陣結(jié)合方式，加括號(hào)輸出if(i==j)//只有一個(gè)矩陣，直接輸出{cout<<"A"<<i;}elseif(i+1==j)//兩個(gè)矩陣，加括號(hào)輸出{cout<<"(A"<<i<<"A"<<j<<")";}else{cout<<"(";Traceback(i,s[i][j]);//遞歸，從最得到最優(yōu)解的地方s[i][j]處斷開(kāi)Traceback(s[i][j]+1,j);cout<<")";}}voidmain(){ cout<<"輸入矩陣個(gè)數(shù)：n="; cin>>n; cout<<"輸入第一個(gè)矩陣行數(shù)和第一個(gè)到第n個(gè)矩陣的列數(shù)："; for(inti=0;i<=n;i++) { cin>>p[i]; } cout<<endl; cout<<"請(qǐng)選擇解決矩陣連乘問(wèn)題的方法："<<endl; cout<<"1.動(dòng)態(tài)規(guī)劃算法"<<endl; cout<<"2.直接遞歸算法"<<endl; cout<<"3.備忘錄算法"<<endl; cout<<"0.退出..."<<endl; cout<<endl; cout<<"請(qǐng)選擇算法："; cin>>q; cout<<endl; while(q!=0){ switch(q){ case1: matrixChain(); cout<<"動(dòng)態(tài)規(guī)劃算法解決矩陣連乘問(wèn)題："<<endl; cout<<"最優(yōu)計(jì)算次序?yàn)椋?; Traceback(1,n); cout<<endl; cout<<"矩陣連乘的最優(yōu)數(shù)乘次數(shù)為："<<m[1][n]<<endl;//最終解值為m[1][n] break; case2: Recur(0,n); cout<<"直接遞歸算法解決矩陣連乘問(wèn)題："<<endl; cout<<"最優(yōu)計(jì)算次序?yàn)椋?; Traceback(1,n); cout<<endl; cout<<"矩陣連乘的最優(yōu)數(shù)乘次數(shù)為："<<m[1][n]<<endl;//最終解值為m[1][n] break; case3: Look(1,n); cout<<"備忘錄算法解決矩陣連乘問(wèn)題："<<endl; cout<<"最優(yōu)計(jì)算次序?yàn)椋?; Traceback(1,n); cout<<endl; cout<<"矩陣連乘的最優(yōu)數(shù)乘次數(shù)為："<<m[1][n]<<endl;//最終解值為m[1][n] break; case0: q=0; break; } cout<<endl; cout<<"請(qǐng)選擇解決矩陣連乘問(wèn)題的方法："<<endl; cout<<"1.動(dòng)態(tài)規(guī)劃算法"<<endl; cout<<"2.直接遞歸算法"<<endl; cout<<"3.備忘錄算法"<<endl; cout<<"0.退出..."<<endl; cout<<"請(qǐng)選擇算法："; cin>>q;