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