算法設(shè)計(jì)與分析c-語言描述(陳慧南版)課后答案(編輯修改稿)
2025-09-01 11:04 本頁面
【文章內(nèi)容簡介】 {coutOut Of Bounds。 return false。} int *p=new temp[k]。 int mid,left=0,right=n1,t=0,j=0,r=0。 for(int i=0。im。i++) { while(k0) { do { mid=(left+right)/2。 if(a[mid]b[i]) left=mid。 else if(a[mid]b[i]) right=mid。 else {t=mid。 break。} }while(leftright1) if(a[left]b[i]) t=left。 else t=left1。 if(kt) { if(t0) { for(j=0。jt。j++) { temp[j]=a[r]。 r++。 } left=t。 k=t。 } else { temp[j]=b[i]。 left=0。 k。 } } else { for(j=0。jk。j++) { temp[j]=a[r]。 r++。 } left=t。 k=t。 return temp[k1]。 } } }}第六章：，所以，最優(yōu)解為，最大收益為。8.第六章69.普里姆算法。 因?yàn)閳DG是一個(gè)無向連通圖。 所以n1=m=n (n1)/2。 O(n)=m=O(n2)。克魯斯卡爾對(duì)邊數(shù)較少的帶權(quán)圖有較高的效率，而，此圖邊數(shù)較多，接近完全圖，故選用普里姆算法。610. T仍是新圖的最小代價(jià)生成樹。 證明：假設(shè)T不是新圖的最小代價(jià)生成樹，T’是新圖的最小代價(jià)生成樹，那么cost(T’)cost(T)。有cost(T’)c(n1)cost(t)c(n1)，即在原圖中存在一顆生成樹，其代價(jià)小于T的代價(jià)，這與題設(shè)中T是原圖的最小代價(jià)生成樹矛盾。所以假設(shè)不成立。證畢。 第七章1. Bcost(1,0)=0。 Bcost(2,1)=c(1,1)+Bcost()=5 Bcost(2,2)=c(1,2)+Bcost(1,0)=2 Bcost(3,3)=min{c(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)}=min{6+2,3+5}=8 Bcost(3,4)=c(2,4)+Bcost(2
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1