《華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系上機(jī)實(shí)踐報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系上機(jī)實(shí)踐報(bào)告（3頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系上機(jī)實(shí)踐報(bào)告
課程名稱：
算法設(shè)計(jì)與分析
年級(jí)：
上機(jī)實(shí)踐成績(jī):
指導(dǎo)教師：
柳銀萍
姓名：
上機(jī)實(shí)踐名稱：
動(dòng)態(tài)規(guī)劃
學(xué)號(hào)：
上機(jī)實(shí)踐日期:
上機(jī)實(shí)踐編號(hào)：
N0.4
組號(hào)：
上機(jī)實(shí)踐時(shí)間:
、目的
二、內(nèi)容與設(shè)計(jì)思想
1.2.對(duì)于以下n個(gè)矩陣：
M 1： po pi, M2： pi p2, M3： p2 p3, M4： p3 p4, M5：p4 p5，…
(a) 找出這n個(gè)矩陣相乘需要的最小數(shù)量乘法的次數(shù)。
(b) 請(qǐng)給出一個(gè)括號(hào)化表達(dá)式，使在這種次序下達(dá)到乘法的次數(shù)最少。
要求：
輸入：輸入一個(gè)正整數(shù)n,表
2、示要處理的矩陣個(gè)數(shù)。在接下來的 1行中，輸入n+1個(gè)數(shù), 依次為這n個(gè)矩陣的維數(shù)。
輸出：計(jì)算出的最少的乘法次數(shù)及相應(yīng)的加括號(hào)方式。
1.1其思路是：
1.2具體算法是:
2.設(shè)A和B是2個(gè)字符串。要用最少的字符操作將字符串 A轉(zhuǎn)換為字符串B。這里所說的
字符操作包括：
(1) 刪除一個(gè)字符；
(2) 插入一個(gè)字符；
(3) 將一個(gè)字符改為另一個(gè)字符。
將字符串A變換為字符串B所用的最少字符操作數(shù)稱為字符串 A到B的編輯距離，記為 d(A,B)。試設(shè)計(jì)一個(gè)有效算法，對(duì)任給的2個(gè)字符串A和B,計(jì)算出它們的編輯距離d(A,B)。 要求：
輸入：第1行是字符串A,第2行是字符串B
3、。
輸出：字符串A和B的編輯距離d(A,B)
2.1其思路是：
2.2具體算法是:
3* ?定義于字母表刀｛a,b,c)上的乘法表如表1所示
表1刀乘法表
a b c
a
b b a
b
c b a
c
a c c
依此乘法表，對(duì)任一定義于刀上的字符串，適當(dāng)加括號(hào)表達(dá)式后得到一個(gè)表達(dá)式。例如，對(duì)于字 符串x=bbbba,它的一個(gè)加括號(hào)表達(dá)式為i(b(bb))(ba)。依乘法表，該表達(dá)式的值為a。試設(shè)計(jì) 一個(gè)動(dòng)態(tài)規(guī)劃算法，對(duì)任一定義于刀上的字符串 X=XiX2…Xn,計(jì)算有多少種不同的加括號(hào)方式 使由x導(dǎo)出的加括號(hào)表達(dá)式的值為 a。
要求：
輸入：輸入一個(gè)以a,b,c組成的任意一個(gè)字符串。
輸出：計(jì)算出的加括號(hào)方式數(shù)。
3.1其思路是:
3.2具體算法是:
使用環(huán)境
四、調(diào)試過程
五、總結(jié)
六、附錄
1■動(dòng)態(tài)規(guī)劃1的程序:
(此處放程序)
運(yùn)行結(jié)果:
2.動(dòng)態(tài)規(guī)劃2的程序：
（此處放程序）
運(yùn)行結(jié)果：
3* .動(dòng)態(tài)規(guī)劃3的程序：
（此處放程序）
運(yùn)行結(jié)果：
要求至少給出1組測(cè)試數(shù)據(jù)運(yùn)行結(jié)果
華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系上機(jī)實(shí)踐報(bào)告
