N个矩阵相乘[管理资料]
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
#include
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
本文档为【N个矩阵相乘[管理资料]】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。