最新算法設(shè)計(jì)與分析作業(yè)三(已改無錯(cuò)字)
2022-07-23 03:13:14 本頁面
【正文】 4[25*20],A5[20*5],A6[5*23],A7[23,8] 則p[08]={10,15,20,5,25,20,5,23,8}，的最佳相乘次序?yàn)?A0(A1A2))(((A3A4)A5)(A6A7))。 實(shí)驗(yàn)五、找零問題 問題提出 設(shè)有n種不同面值的硬幣，各硬幣的面值存于數(shù)組t[1:n]中?，F(xiàn)要用這些面值的硬幣來找錢，可以實(shí)用的各種面值的硬幣個(gè)數(shù)不限。當(dāng)只用硬幣面值t[1],t[2],…,t[i]時(shí)，可找出錢數(shù)M的最少硬幣個(gè)數(shù)記為b[i][j]。若只用這些硬幣面值，找不出錢數(shù)M時(shí)，記b[i][j]=∞。 求解思路 令b[i,j]表示前i(1≤i≤m)種硬幣，總額為j(0≤j≤n)的最小硬幣數(shù)。目標(biāo)為求b[m,n]。由于對第i種硬幣，存在可選1個(gè)或者不選兩種可能，故容易建立遞推關(guān)系：b[i,j]＝min{ b[i1,j], 1+b[i,jvi]}, for 1≤i≤m, 0≤j≤n顯然，b[i,0]=0, 1≤i≤m如果無解，令b[i,j]=+∞。特別的，如果i=1，令b[1,j]=+∞；如果jvi0，b[i,jvi]=+∞ 算法復(fù)雜度n鈔票面額的個(gè)數(shù) M要找的錢數(shù)，子問題不重復(fù)計(jì)算，時(shí)間復(fù)雜度降低，時(shí)間復(fù)雜度O(nM)。 實(shí)驗(yàn)源代碼include include define INFINITY 32767 //無窮大define MAX 100/*b[i][j]==1 子問題未計(jì)算，遞歸計(jì)算 b[i][j]!=1 子問題已計(jì)算，直接取計(jì)算結(jié)果 另外,也可從b[i][j]算出各種面額的鈔票數(shù)*/int DynamicMemory(int t[], int i ,int j,int b[][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[i1][j]==1) x=DynamicMemory(t,i1,j,b)。 else x=b[i1][j]。 if(jt[i]) { b[i][j]=x。 return x。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號(hào)-1