N个矩阵相乘.doc

N个矩阵相乘

指手画脚 question step 1

Hi all,

之前的号wxjeacen被封了之后一直也就没露面，公司的事情也比较多。

这里的牛人越来越少了。之前的 StarWin83,貌似也很久都不露面了。

免掉不必要的矫情。

指手画脚，看看你的code 水平。

有兴趣的也可以贴个代码， 希望不要把这个帖子又一度论文水贴。

Question Describe :

第一个问题，也是比较基本的算法问题。

看看你的基本工，跟我彪过code 的vx_works,StarWin83的基本功都是一流的。

N个矩阵相乘，不同的结合方式会有不同的计算复杂度，所谓的计算复杂度也就是计算量。

A1*A2*A3可以加括号，A1*(A2*A3)或者，(A1*A2)*A3结果都一样，但是计算两未必相同。

input sample:

7

30 35 15 5 10 20 25

(Note:7表示一个输入矩阵的个数。A[i-1],A[i]表示矩阵的两维.比如，30 也就是A[0], 35也就是A[1],这两个就表示第一个矩阵是30*35 , A[1], A[2] 表示第2个矩阵是35*15,这N-1个矩阵是相容的。）

output sample:

((A1 (A2 A3 ))((A4 A5 )A6 ))

(Note:这个组合方式出来的结果，所要的计算两是最简的）程序代码：

#include <malloc.h>

#include <stdio.h>

int Right(int & nSum, int & nPos, int arr[], int arrDepth[], int nDepth, int & nNode);

/////////////////////////////////////////////////////////////////////////////

// 函数说明 : 遍历左子树

// 输入参数 : int & nSum 计算量

// 输入参数 : int & nPos 遍历矩阵的位置

// 输入参数 : int arr[] 相容矩阵

// 输入参数 : int arrDepth[] 各个矩阵元素的所在二叉树深度

// 输入参数 : int nDepth 当前深度

// 输入参数 : int & nNode 节点数

// 返 回 值 : int 矩阵行数

// 作者信息 : 指手画脚 2010-1-11 12:32:47

/////////////////////////////////////////////////////////////////////////////

int Left(int & nSum, int & nPos, int arr[], int arrDepth[], int nDepth, int & nNode)

{

nNode++; // 记录节点数

int nLeft = 0; // 第一个矩阵的行

int nRight = 0; // 第二个矩阵的列

nDepth++; // 记录深度

// 判断当前深度是否超过给定深度

if (nDepth > arrDepth[nPos])

return -1;

// 判读是否达到指定深度

if (nDepth == arrDepth[nPos])

return arr[nPos++];

else

nLeft = Left(nSum, nPos, arr, arrDepth, nDepth, nNode);

// 判断是否出现错误遍历

if (-1 == nLeft)

return -1;

// 向右子树遍历

nRight = Right(nSum, nPos, arr, arrDepth, nDepth, nNode);

// 判断是否出现错误遍历

if (-1 == nRight)

return -1;

// 计算计算量

nSum += nLeft*nRight;

return nLeft;

/////////////////////////////////////////////////////////////////////////////

// 函数说明 : 遍历右子树

// 输入参数 : int & nSum 计算量

// 输入参数 : int & nPos 遍历矩阵的位置

// 输入参数 : int arr[] 相容矩阵

// 输入参数 : int arrDepth[] 各个矩阵元素的所在二叉树深度

// 输入参数 : int nDepth 当前深度

// 输入参数 : int & nNode 节点数

// 返 回 值 : int 矩阵列数

// 作者信息 : 指手画脚 2010-1-11 12:33:48

/////////////////////////////////////////////////////////////////////////////

int Right(int & nSum, int & nPos, int arr[], int arrDepth[], int nDepth, int & nNode)

{

nNode++; // 记录节点数

int nLeft = 0; // 第一个矩阵的行

int nRight = 0; // 第二个矩阵的列

nDepth++; // 记录深度

// 判断当前深度是否超过给定深度

if (nDepth > arrDepth[nPos])

return -1;

if (nDepth == arrDepth[nPos])

return arr[++nPos];

else

nLeft = Left(nSum, nPos, arr, arrDepth, nDepth, nNode);

// 判断是否出现错误遍历

if (-1 == nLeft)

return -1;

// 继续向右子树遍历

nRight = Right(nSum, nPos, arr, arrDepth, nDepth, nNode);

// 判断是否出现错误遍历

if (-1 == nRight)

return -1;

// 计算计算量

nSum += nLeft*nRight;

return nRight;

}

/////////////////////////////////////////////////////////////////////////////

// 函数说明 : 计算矩阵在当前满二叉树下的计算量

// 输入参数 : int arr[] 相容矩阵

// 输入参数 : int nLen 数组长度

// 输入参数 : int arrDepth[] 满二叉树深度数组

// 返 回 值 : int 如果计算成功返回计算量，否则返回-1

// 作者信息 : 指手画脚 2010-1-11 12:43:32

/////////////////////////////////////////////////////////////////////////////

int CountSum(int arr[], int nLen, int arrDepth[])

{

// 计算计算量

int nSum = 0;

int nPos = 0;

int nDepth = 0;

int nNode = 0;

if (-1 == Left(nSum, nPos, arr, arrDepth, nDepth, nNode))

return -1;

// 判断节点数是否为合法满二叉树

if (2*nLen-3 != nNode)

return -1;

// 计算成功，返回计算量

return nSum;

}

/////////////////////////////////////////////////////////////////////////////

// 函数说明 : 递归生成所有可能的满二叉树

// 输入参数 : int n 深度数组标记

// 输入参数 : int arrDepth[] 满二叉树的深度数组

// 输入参数 : int arr[] 相容矩阵

// 输入参数 : int nLen 矩阵数组长度

// 输入参数 : int & nMin 计算量最小值

// 输入参数 : int arrMinDepth[] 计算量最小值时的深度数组

// 作者信息 : 指手画脚 2010-1-11 12:50:02

/////////////////////////////////////////////////////////////////////////////

void EnumTree(int n, int arrDepth[], int arr[], int nLen, int & nMin, int arrMinDepth[])

{

// 判断是否已经生成完成一组深度数组

if (-1 == n)

{// 完成一组深度数组

// 计算计算量

int nSum = CountSum(arr, nLen, arrDepth);

// 判断是否为最小计算量

if (-1 != nSum && (nSum < nMin || 0 == nMin))

{

for (int i=0; i<nLen-1; i++)

arrMinDepth[i] = arrDepth[i];

nMin = nSum;

}

return;

}

// 从小到大设置当前深度

for (int i=2; i<nLen; i++)

{

arrDepth[n] = i;

EnumTree(n-1, arrDepth, arr, nLen, nMin, arrMinDepth);

}

}

void Expreesion_Right(char sz[], int nMaxLen, int & nSzPos, int & nPos, int arrDepth[], int nDepth); /////////////////////////////////////////////////////////////////////////////

// 函数说明 : 遍历左子树求求表达式

// 输入参数 : char sz[] 表达式保存字符串

// 输入参数 : int nMaxLen 字符串最大长度

// 输入参数 : int & nSzPos 当前字符串位置

// 输入参数 : int & nPos 遍历深度的位置

// 输入参数 : int arrDepth[] 深度数组

// 输入参数 : int nDepth 当前深度

// 作者信息 : 指手画脚 2010-1-11 13:37:53

/////////////////////////////////////////////////////////////////////////////

void Expreesion_Left(char sz[], int nMaxLen, int & nSzPos, int & nPos, int arrDepth[], int nDepth) {

if (nMaxLen < nSzPos)

return;

nDepth++;

if (nDepth == arrDepth[nPos])

{

nPos++;

sz[nSzPos++] = 'A';

sz[nSzPos++] = nPos+'0';

return;

}

sz[nSzPos++] = '(';

Expreesion_Left(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);

Expreesion_Right(sz, nMaxLen, nSzPos, nPos, arrDepth, nDepth);

sz[nSzPos++] = ')';

}

/////////////////////////////////////////////////////////////////////////////