算法設(shè)計(jì)與分析期末論-文庫吧
2025-05-18 01:59 本頁面
【正文】 主函數(shù) void main() { int n=0。 int c[N][N]。 int x[N]={0}。 int p[N]={0}。 printf(\t\t\t\ n\n)。 printf(請輸入人數(shù) \n)。 scanf(%d,amp。n)。 下面用來輸入所需費(fèi)用 for(int i=1。i=n。i++) { for(int j=1。j=n。j++) scanf(%d,amp。c[i][j])。 } 調(diào)用 workdistribute(1,n,p,x,c)。函數(shù)進(jìn)行遞歸分配工作，遞歸結(jié)束后進(jìn)行輸出最小費(fèi)用和此分法，以矩陣的形式顯示 workdistribute(1,n,p,x,c)。 printf(%d\n,minexpense)。 此循環(huán)用來輸出最少費(fèi)用的分配方法 for(int k=1。k=n。k++) { for(int j=1。j=n。j++) { if(q[k]!=j) printf( )。 else printf(%d ,c[k][j])。 } printf(\n)。 } } //workdistribute(i,n,p,x,c)函數(shù)設(shè)計(jì)，傳遞進(jìn)行分 配的是第幾件工作 i，已分配過的人 X[],分配的路徑 p[]，以及費(fèi)用數(shù)組 c[][]，用 X[]來保存已非配工作所需費(fèi)用 void workdistribute(int i,int n,int *p,int x[],int c[][N]) { for(int j=1。j=n。j++) { if(x[j]==0) 4 { x[j]=1。 x[0]+=c[i][j]。 p[i]=j。 if(in)//當(dāng)未分配完時(shí)繼續(xù)調(diào)用 { workdistribute(i+1,n,p,x,c)。 } else//最后一事件分配完后，判斷此次分配是不是最小費(fèi)用 { if(minexpensex[0]||minexpense==1) //如果是最小分配或第一次分配，則保存此次分配數(shù)據(jù) { minexpense=x[0]。 for(int k=1。k=n。k++) q[k]=p[k]。 } } x[j]=0。 x[0]=c[i][j]。//返回上一層之前，先減去此事件分配的費(fèi)用 } } } 最后通過簡例說明程序?qū)崿F(xiàn)過程 輸入事件數(shù)為 3 輸入費(fèi)用矩陣 C 3 2 1 3 4 5 2 1 2 1 第一層第一次分配 workdistribute(1,n,p,x[],c[][N])。分配過程 c[1][1],c[2][2],c[3][3] 此時(shí)最小費(fèi)用是 8 賦值給minexpense，并把 1,2,3 保存在 q 數(shù)組 ,最后一層遞歸返回上一次，第二中分配方式 c[1][1],c[2][3],c[3][2]此時(shí)費(fèi)用時(shí) 6， minexpense 為 6， 1,3,2 保存在 q 中， 第一層第一次分配完畢，然后循環(huán) workdistribute(2,n,p,x[],c[][N])。第三種分配 ,c[1][2],c[2][1],c[3][3]，minexpesne=6,q[]:為 1,3,2，第四次分配 c[1][2],c[2][3],c[3][1]， minexpense=4， q[]： 2,3,1 第一層第二次分配完畢，然后循環(huán) workdistribute(3,n,p,x[],c[][N])。第五種分配c[1][3],c[2][1],c[3][2],minexpense=4， q[]： 2,3,1，第六種分配 c[1][3],c[2][2],c[3][1],minexpense=4， q[]： 2,3,1 返回主程序，輸出 minexpense， q[]， 2,3,1。 輸出
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1