返回顶部

收藏

矩阵乘法动态规划

更多
/*
* File:        multi.c
* Description:  矩阵乘法动态规划
* Created:      10:20 2001-12-3
* Author:      Justin Hou [mailto:justin_hou@hotmail.com]
*
*/

#include <stdio.h>
#define  N  7

int middle[N][N];

void Show(int, int);

void main()
{
        int i, j, l, k;
        unsigned long m[N+1][N+1], min;
        int r[N+1] = {10, 20, 50, 1, 100, 4, 20, 2};                            /* 矩阵维数 */

        /* 初始化 */
        for (i = 1; i <= N; i++) {
                m[i][i] = 0;
        }
        /* 每此增量加一 */
        for (l = 1; l < N; l++) {

                /* 对于差值为 l 的两个元素 */
                for (i = 1; i <= N - l; i++) {
                        j = i + l; 

                        /* 求其最小组合方式 */
                        min = m[i][i] + m[i+1][j] + r[i-1] * r[i] * r[j];
                        middle[i][j] = i;
                        for (k = i + 1; k < j; k++) {
                                if (min > m[i][k] + m[k+1][j] + r[i-1] * r[k] * r[j]) {
                                        min = m[i][k] + m[k+1][j] + r[i-1] * r[k] * r[j];
                                        middle[i][j] = k;
                                }
                        }
                        m[i][j] = min;
                }
        }
        printf("M = ");
        Show(1, N);
        printf("\\nMultiply Count: %d\\n", m[1][N]);
}

void Show(int i, int j)
{
        int k, m;

        if (i == j){
                printf("M%d", i);                              /* 如果下一个是矩阵,输出  */
        }
        else {
                m = middle[i][j];                              /* 分割成左右两组          */
                if (i != m) printf("(");                        /* 如果下一个显示的不是矩阵 */
                Show(i, m);                                    /* 显示左边的内容          */
                if (i != m) printf(")");                        /* 如果上一个显示的不是矩阵 */
                printf(" x ");                                  /* 打印乘法符号            */
                if (m+1 != j) printf("(");                      /* 如果下一个显示的不是矩阵 */
                Show(m + 1, j);                                /* 显示右边的内容          */
                if (m+1 != j) printf(")");                      /* 如果下一个显示的不是矩阵 */
        }

}
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2014-07-22 21:15:21斐波那契数列 by lucasli
  2. 2014-07-31 11:37:40二叉树 by 蟋蟀哥
  3. 2014-09-12 12:23:42求32768以内的质数 by walker30
  4. 2014-10-11 10:46:46c++实现欧拉回路问题 by 蟋蟀哥
  5. 2014-10-14 20:34:02二叉树的建立、存储与遍历 by 千万不要郁闷
  6. 2014-10-17 10:56:47求素数 by 童学芬
  7. 2014-10-20 10:44:19余弦曲线 by walker30
  8. 2014-10-26 11:58:41小字库DIY一 by sxgkwei
  9. 2014-12-03 10:48:48KMP算法实现字符串搜索 by 千万不要郁闷
  10. 2013-10-31 09:05:17C语言找出大于一个数的最小回文数 by walker30
  11. 2014-03-03 17:55:22每对结点之间最短路径的C++实现 by 千万不要郁闷
相关聚客文章
  1. dianlujitao 发表 2014-10-17 13:45:25 POJ 3122 Pie
  2. bystander 发表 2013-04-16 00:42:58 模板优先级队列及堆排序(C++实现)
  3. dianlujitao 发表 2014-10-17 13:52:22 POJ 2388 Who’s in the Middle
  4. surgesoft 发表 2014-10-28 08:01:58 LeetCode OJ: Restore IP Addresses
  5. espace 发表 2015-07-18 17:43:14 Two Sum
  6. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  7. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects
  8. bystander 发表 2013-05-15 10:37:24 倒水问题求解(C++)
  9. dianlujitao 发表 2014-10-17 14:11:26 POJ 1328 Radar Installation
  10. bystander 发表 2013-04-01 10:12:37 [藏]关于B树的一篇文章
  11. lvfuyu 发表 2015-04-12 08:53:30 [hihocoder]矩阵快速幂
  12. lvfuyu 发表 2015-04-18 09:13:32 [hihocoder]二分查找

发表评论