• /  13
  • 下載費用: 15積分  

算法設計與分析(作業三)

'算法設計與分析(作業三)'
? .. .. ..算法設計與分析實驗報告學 院 信息科學與技術學院 專業班級 軟件工程3班 學 號 20122668 姓 名 王建君 指導教師 尹治本 2014年10月 實驗四 矩陣相乘次序一、 問題提出用動態規劃算法解矩陣連乘問題。給定n個矩陣{A1,A2,…,An},其中Ai與Ai+1是可乘的,i=1,2,…,n-1。要算出這n個矩陣的連乘積A1A2…An。由于矩陣乘法滿足結合律,故計算矩陣的連乘積可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定,也就是說該連乘積已完全加括號,則可以依此次序反復調用2個矩陣相乘的標準算法計算出矩陣連乘積。完全加括號的矩陣連乘積可遞歸地定義為: (1) 單個矩陣是完全加括號的; (2) 矩陣連乘積A是完全加括號的,則A可表示為2個完全加括號的矩陣連乘積B和C的乘積并加括號,即A=(BC)。 例如,矩陣連乘積A1A2A3A4有5種不同的完全加括號的方式:(A1(A2(A3A4))),(A1((A2A3)A4)),((A1A2)(A3A4)),((A1(A2A3))A4),(((A1A2)A3)A4)。每一種完全加括號的方式對應于一個矩陣連乘積的計算次序,這決定著作乘積所需要的計算量。若A是一個p×q矩陣,B是一個q×r矩陣,則計算其乘積C=AB的標準算法中,需要進行pqr次數乘。 (3) 為了說明在計算矩陣連乘積時,加括號方式對整個計算量的影響,先考察3個矩陣{A1,A2,A3}連乘的情況。設這三個矩陣的維數分別為10×100,100×5,5×50。加括號的方式只有兩種:((A1A2)A3),(A1(A2A3)),第一種方式需要的數乘次數為10×100×5+10×5×50=7500,第二種方式需要的數乘次數為100×5×50+10×100×50=75000。第二種加括號方式的計算量時第一種方式計算量的10倍。由此可見,在計算矩陣連乘積時,加括號方式,即計算次序對計算量有很大的影響。于是,自然提出矩陣連乘積的最優計算次序問題,即對于給定的相繼n個矩陣{A1,A2,…,An}(其中矩陣Ai的維數為pi-1×pi,i=1,2,…,n),如何確定計算矩陣連乘積A1A2…An的計算次序(完全加括號方式),使得依此次序計算矩陣連乘積需要的數乘次數最少。二、 求解思路本實驗采用動態規劃算法解矩陣連乘積的最優計算次序問題。本實驗的算法思路是: 1)計算最優值算法MatrixChain():建立兩張表(即程序中的**m和**s,利用二維指針存放),一張表存儲矩陣相乘的最小運算量,主對角線上的值為0,依次求2個矩陣、3個矩陣…、直到n個矩陣相乘的最小運算量,其中每次矩陣相乘的最小運算量都在上一次矩陣相乘的最小運算量的基礎上求得,最后一次求得的值即為n個矩陣相乘的最小運算量;另一張表存儲最優斷開位置。 2)輸出矩陣結合方式算法Traceback():矩陣結合即是給矩陣加括號,打印出矩陣結合方式,由遞歸過程Traceback()完成。分三種情況: (1)只有一個矩陣,則只需打印出A1; (2)有兩個矩陣,則需打印出(A1-省略部分-[MAX]) { if(i==1) { if(j%t[1]==0) b[i][j]=j/t[1]; else b[i][j]=INFINITY; return b[i][j]; } else{ int x; if(b[i-1][j]==-1) x=DynamicMemory(t,i-1,j,b); else x=b[i-1][j]; if(jy+1)?(y+1):x; return b[i][j]; } } } void main() { system("title 軟件3班 王建君 20122668 動態規劃實現找零問題"); int t[10],n,M;//n--鈔票面額的個數 M--要找的錢數 t[0]=0; printf("請輸入鈔票面額的種數:\n"); scanf("%d",&n); printf("請依次輸入%d種鈔票的面額:\n",n); for(int i=1;i<=n;i++) scanf("%d",&t[i]); printf("請輸入要找零的錢的總數:\n"); scanf("%d",&M); int b[MAX][MAX]; int p[MAX]={0}; for(i=0;i<MAX;i++) for(int j=0;j0) if(r=1;k--) { if(p[k]!=0) printf("面額為%d的鈔票數:%d\n",t[k],p[k]); } }} 五、 結果分析 專業word可編輯 .
關 鍵 詞:
分析 算法 設計 作業
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:算法設計與分析(作業三)
鏈接地址: http://www.476824.live/p-47706534.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 下期双色球开出号码 山东快乐扑克开奖结果查询 北京28最准的技巧 理财都有哪几种方式 辽宁快乐12走势手机版 韩国快乐8app 黑龙江正好网11选五 淘宝天天红包赛能拿多少红包 贵州快3号码统计图 福建11选5任玩法