華東師范大學(xué)計算機(jī)科學(xué)技術(shù)系上機(jī)實(shí)踐報告

1、華東師范大學(xué)計算機(jī)科學(xué)技術(shù)系上機(jī)實(shí)踐報告課程名稱：算法設(shè)計與分析年級：上機(jī)實(shí)踐成績:指導(dǎo)教師：柳銀萍姓名：上機(jī)實(shí)踐名稱：動態(tài)規(guī)劃學(xué)號：上機(jī)實(shí)踐日期:上機(jī)實(shí)踐編號：N0.4組號：上機(jī)實(shí)踐時間:、目的二、內(nèi)容與設(shè)計思想1.2.對于以下n個矩陣：M 1： po pi, M2： pi p2, M3： p2 p3, M4： p3 p4, M5：p4 p5，(a) 找出這n個矩陣相乘需要的最小數(shù)量乘法的次數(shù)。(b) 請給出一個括號化表達(dá)式，使在這種次序下達(dá)到乘法的次數(shù)最少。要求：輸入：輸入一個正整數(shù)n,表示要處理的矩陣個數(shù)。在接下來的 1行中，輸入n+1個數(shù), 依次為這n個矩陣的維數(shù)。輸出：計算出的最少的

2、乘法次數(shù)及相應(yīng)的加括號方式。1.1其思路是：1.2具體算法是:2.設(shè)A和B是2個字符串。要用最少的字符操作將字符串A轉(zhuǎn)換為字符串B。這里所說的字符操作包括：(1) 刪除一個字符；(2) 插入一個字符；(3) 將一個字符改為另一個字符。將字符串A變換為字符串B所用的最少字符操作數(shù)稱為字符串 A到B的編輯距離，記為 d(A,B)。試設(shè)計一個有效算法，對任給的2個字符串A和B,計算出它們的編輯距離d(A,B)。 要求：輸入：第1行是字符串A,第2行是字符串B。輸出：字符串A和B的編輯距離d(A,B)2.1其思路是：2.2具體算法是:3* 定義于字母表刀a,b,c)上的乘法表如表1所示表1刀乘法表a b cab b abc b aca c c依此乘法表，對任一定義于刀上的字符串，適當(dāng)加括號表達(dá)式后得到一個表達(dá)式。例如，對于字 符串x=bbbba,它的一個加括號表達(dá)式為i(b(bb)(ba)。依乘法表，該表達(dá)式的值為a。試設(shè)計 一個動態(tài)規(guī)劃算法，對任一定義于刀上的字符串 X=XiX2Xn,計算有多少種不同的加括號方式 使由x導(dǎo)出的加括號表達(dá)式的值為 a。要求：輸入：輸入一個以a,b,c組成的任意一個字符串。輸出：計算出的加括號方式數(shù)。3.1其思路是:3.2具體算法是:使用環(huán)境四、調(diào)試過程五、總結(jié)六、附錄1動態(tài)規(guī)劃1的程序:(此處放程序)運(yùn)行結(jié)果:2.動態(tài)規(guī)劃2的程序：（此處放程序