N个矩阵相乘[管理资料]

N个矩阵相乘[管理资料]N个矩阵相乘[管理资料] N个矩阵相乘指手画脚 question step 1 Hi all, 之前的号wxjeacen被封了之后一直也就没露面，公司的事情也比较多。这里的牛人越来越少了。之前的 StarWin83,貌似也很久都不露面了。免掉不必要的矫情。指手画脚，看看你的code 水平。有兴趣的也可以贴个代码，希望不要把这个帖子又一度论文水贴。 Question Describe : 第一个问题，也是比较基本的算法问题。看看你的基本工，跟我彪过code 的vx_works,Sta...

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，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

N个矩阵相乘[管理资料]

你可能还喜欢