矩陣連乘問題：下圖是動(dòng)態(tài)規(guī)劃算法計(jì)算6個(gè)矩陣A1A2A3A4A5A6連乘所生成的信息表
（a）表描述了計(jì)算順序
（b）表是m[i][j]的最優(yōu)值表
（c）表是輔助信息表（斷開位置）
分析表格，給出A2A3A4A5A6五個(gè)矩陣連乘所需要的最少數(shù)乘次數(shù)，并用加括號(hào)的方法表示出其乘法順序（）。
A.15125，（A2A3）（（A4A5）A6）
B.10500，（A2（A3A4））（A5A6）
C.15125，（A2（A3A4））（A5A6）
D.10500，（A2A3）（（A4A5）A6）
您可能感興趣的試卷
你可能感興趣的試題
動(dòng)態(tài)規(guī)劃解題的步驟分為四步：
（1）分析最優(yōu)解的結(jié)構(gòu)
（2）建立遞歸關(guān)系
（3）計(jì)算最優(yōu)值
（4）構(gòu)造最優(yōu)解
關(guān)于這四個(gè)步驟的內(nèi)容描述不正確的是哪個(gè)？（）
A.計(jì)算最優(yōu)值：以自頂往下的方法計(jì)算問題的最優(yōu)值，也就是先求解規(guī)模較大的問題的最優(yōu)值
B.構(gòu)造最優(yōu)解：根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造出問題的最優(yōu)解，通常是用遞歸算法完成最優(yōu)解的構(gòu)造
C.建立遞歸關(guān)系：建立關(guān)于問題最優(yōu)值的遞歸定義，即問題的最優(yōu)值通過子問題的最優(yōu)值合并得到
D.分析最優(yōu)解的結(jié)構(gòu)：一個(gè)一般化問題可以分解為幾個(gè)性質(zhì)相同的子問題，并且問題的最優(yōu)解可以通過子問題的最優(yōu)解合并得到，也就是要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)
A.O（n）
B.O（nlogn）
C.O（logn）
D.O（n2）
A.結(jié)構(gòu)清晰
B.容易用數(shù)學(xué)歸納法證明算法的正確性
C.遞歸算法耗費(fèi)的時(shí)間和占用的內(nèi)存空間要比解決同一問題的非遞歸算法要少
D.可讀性強(qiáng)
A.6
B.101
C.51
D.7
A.這是因?yàn)闅w并排序把問題劃分為子問題時(shí)的時(shí)間復(fù)雜性是O（1），而快速排序劃分為子問題是使用partition（）函數(shù)，其時(shí)間復(fù)雜性是O（n）
B.因?yàn)闅w并排序把問題劃分為兩個(gè)子問題時(shí)其規(guī)模大致相等，是原來規(guī)模的n/2，而快速排序劃分為子問題是使用partition（）函數(shù)，劃分為子問題時(shí)不能保證二個(gè)子問題的規(guī)模大致相同，在極端狀況下，每次都只劃分為1個(gè)子問題，其規(guī)模為原問題規(guī)模n-1，因此快速排序在極端狀況下的時(shí)間復(fù)雜性的遞歸定義為T（n）=T（n-1）+O（n）
C.因?yàn)榭焖倥判驅(qū)栴}劃分為子問題的個(gè)數(shù)比歸并排序要多
D.歸并排序的分和合的時(shí)間復(fù)雜性之和低于快速排序的分和合的時(shí)間復(fù)雜性之和
最新試題
使用窮舉法求解最長遞增子序列的時(shí)間復(fù)雜度為（）。
在隊(duì)列式分支限界法解決裝載問題時(shí)，為什么在其改進(jìn)算法中，每次進(jìn)入左分支都要檢查更新bestw，而不是等搜索到達(dá)葉子結(jié)點(diǎn)時(shí)才去更新bestw，其目的是什么？（）
在求解部分背包問題時(shí)采用的貪心策略是（）。
回溯法采用的搜索策略是（）。
回溯法的主要用途包括求問題的所有解、求問題的最優(yōu)解和求問題的任一解。
下列關(guān)于貪心算法與動(dòng)態(tài)規(guī)劃算法說法正確的是（）。
下面哪個(gè)問題不是NPC問題？（）
0-1背包問題與部分背包問題的區(qū)別在于（）。
用m種顏色給n個(gè)頂點(diǎn)著色、且使一條邊的兩個(gè)頂點(diǎn)顏色不同，則對(duì)應(yīng)的解空間樹是一棵（）。
分支限界法中，擴(kuò)展出的孩子結(jié)點(diǎn)在入隊(duì)時(shí)，存儲(chǔ)該孩子結(jié)點(diǎn)的父結(jié)點(diǎn)的地址和左孩子標(biāo)志。其目的是什么？（）