最新算法設(shè)計(jì)與分析作業(yè)三(專業(yè)版)
【正文】 k=k1。 printf(請輸入要找零的錢的總數(shù):\n)。 } else { int y。 實(shí)驗(yàn)五、找零問題 問題提出 設(shè)有n種不同面值的硬幣，各硬幣的面值存于數(shù)組t[1:n]中。)39。i。i++) m[i][i]=0。設(shè)這三個(gè)矩陣的維數(shù)分別為10100，1005，550。這種計(jì)算次序可以用加括號(hào)的方式來確定。 三、算法復(fù)雜度 該算法時(shí)間復(fù)雜度最高為。kj。 traceback(s[i][j]+1,j)。 //測試數(shù)據(jù)可以設(shè)為8個(gè)矩陣分別為 //A1[10*15],A2[15*20],A3[20*5],A4[5*25],A5[25*20],A6[20*5],A7[5*23],A8[23,8] //則p[08]={10,15,20,5,25,20,5,23,8} cout輸出結(jié)果如下：endl。 else b[i][j]=INFINITY。 scanf(%d,amp。j++) b[i][j]=1。k) { if(p[k]!=0) printf(面額為%d的鈔票數(shù)：%d\n,t[k],p[k])。i++) for(int j=0。//n鈔票面額的個(gè)數(shù) M要找的錢數(shù) t[0]=0。特別的，如果i=1，令b[1,j]=+∞；如果jvi0，b[i,jvi]=+∞ 算法復(fù)雜度n鈔票面額的個(gè)數(shù) M要找的錢數(shù)，子問題不重復(fù)計(jì)算，時(shí)間復(fù)雜度降低，時(shí)間復(fù)雜度O(nM)。i=n。 if(s[i][j]+1j) cout39。 s[i][j]=i。 2)輸出矩陣結(jié)合方式算法Traceback()：矩陣結(jié)合即是給矩陣加括號(hào)，打印出矩陣結(jié)合方式，由遞歸過程Traceback()完成。要算出這n個(gè)矩陣的連乘積A1A2…An。第二種加括號(hào)方式的計(jì)算量時(shí)第一種方式計(jì)算量的10倍。r=n。 } if(is[i][j]) cout39。 } int main() { system(title 軟件3班 王建君 20122668 動(dòng)態(tài)規(guī)劃求矩陣連乘次序)。當(dāng)只用硬幣面值t[1],t[2],…,t[i]時(shí)，可找出錢數(shù)M的最少硬幣個(gè)數(shù)記為b[i][j]。 else
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號(hào)-1