数据结构-矩阵连乘算法

男娘i 2023-10-11 20:43 12阅读 0赞

数据结构,c语言  
用先序序列和中序序列构建二叉树，采用二叉链表存储。编写递归算法，交换二叉树的左右子树，  
输出新二叉树按先序遍历得到的结果。  
提交格式：实现void solve(int n, int \*preOrder, int \*inOrder, int \*outOrder)函数。  
函数参数为序列长度n、先序序列preOrder、中序序列inOrder和输出序列outOrder。1<=n<=1000000，树的深度<=2000。  
请不要printf输出任何内容。  
输入样例1：  
n=5,preOrder=\{1,2,3,4,5\},inOrder=\{3,2,4,1,5\}  
输出样例1：  
outOrder=\{1,5,2,4,3\}

解答：

这道题可以使用动态规划来解决。  
首先，我们可以使用一个二维数组  d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\] 表示在计算矩阵  A i ⋯ A j A\_i \\cdots A\_j Ai⋯Aj 连乘积的最小乘次数。这个数组的每一个元素都可以由更小范围内的矩阵连乘转移而来。具体地，我们可以枚举  k k k，使得  i ≤ k < j i \\leq k < j i≤k<j，然后计算出  d p \[ i \] \[ j \] = min ⁡ ( d p \[ i \] \[ j \] , d p \[ i \] \[ k \] + d p \[ k + 1 \] \[ j \] + p \[ i − 1 \] p \[ k \] p \[ j \] ) dp\[i\]\[j\] = \\min(dp\[i\]\[j\], dp\[i\]\[k\] + dp\[k+1\]\[j\] + p\[i-1\]p\[k\]p\[j\]) dp\[i\]\[j\]=min(dp\[i\]\[j\],dp\[i\]\[k\]\+dp\[k\+1\]\[j\]\+p\[i−1\]p\[k\]p\[j\])。  
除了计算最小乘次数之外，我们还需要记录下来矩阵连乘的次序。我们可以使用一个二维数组  s \[ i \] \[ j \] s\[i\]\[j\] s\[i\]\[j\] 表示在计算矩阵  A i ⋯ A j A\_i \\cdots A\_j Ai⋯Aj 连乘积时， d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\] 这个值是由哪个矩阵转移而来的。这样，我们就可以通过  s s s 数组得到矩阵连乘的次序。  
最后，我们可以通过递归的方式来输出矩阵连乘的次序。具体来说，我们可以写一个函数，输入为  i i i 和  j j j，然后判断  i = j i=j i=j 的情况，输出  i i i。否则，我们输出  − 1 -1 −1，然后调用递归函数来处理  i i i 到  s \[ i \] \[ j \] s\[i\]\[j\] s\[i\]\[j\] 之间的矩阵，然后再输出  s \[ i \] \[ j \] + 1 s\[i\]\[j\]+1 s\[i\]\[j\]\+1