设计一个动态规划算法确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。程序运行结束时,将矩阵连乘的加括号方式以及所计算的乘法次数输出的代码
时间: 2024-02-26 11:57:12 浏览: 26
好的,以下是Python实现代码:
```python
def matrix_chain_order(p):
n = len(p) - 1
m = [[float('inf')] * n for _ in range(n)]
s = [[0] * n for _ in range(n)]
for i in range(n):
m[i][i] = 0
for l in range(2, n + 1):
for i in range(n - l + 1):
j = i + l - 1
for k in range(i, j):
q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
if q < m[i][j]:
m[i][j] = q
s[i][j] = k
return m, s
def print_optimal_parens(s, i, j):
if i == j:
print(f"A_{i}", end="")
else:
print("(", end="")
print_optimal_parens(s, i, s[i][j])
print_optimal_parens(s, s[i][j] + 1, j)
print(")", end="")
def main():
p = [30, 35, 15, 5, 10, 20, 25]
m, s = matrix_chain_order(p)
print("Minimum number of multiplications:", m[0][len(p) - 2])
print("Optimal parenthesization: ", end="")
print_optimal_parens(s, 0, len(p) - 2)
if __name__ == "__main__":
main()
```
这里假设我们有 $6$ 个矩阵,维度分别为 $30 \times 35, 35 \times 15, 15 \times 5, 5 \times 10, 10 \times 20, 20 \times 25$,并将它们存储在数组 $p$ 中。可以根据需要修改这个数组。
在主函数中,首先调用 `matrix_chain_order` 函数计算最少的数乘次数和最优的计算次序,然后调用 `print_optimal_parens` 函数输出加括号方式。
其中 `matrix_chain_order` 函数实现了上面介绍的动态规划算法,返回两个二维数组 $m$ 和 $s$。`print_optimal_parens` 函数根据 $s$ 数组的值递归输出加括号方式。
希望这段代码能够帮助到你!
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)