返回顶部

收藏

矩阵乘法动态规划

更多
/*
* 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. 2012-11-06 09:31:31孪生素数 by 牛哥
  2. 2013-03-29 15:39:35背包问题动态规划详解 by moxia
  3. 2013-05-18 15:26:29c++实现K-MEANS算法 by 李兰军
  4. 2014-02-07 11:26:13C++算法之寻路算法 by 千万不要郁闷
  5. 2014-05-04 10:48:55C++算法之内存数据 by lucasli
  6. 2014-05-20 13:07:50各种排序算法 by walker30
  7. 2014-05-21 17:32:00排序之直接插入排序 by Kevin.
  8. 2014-05-21 21:44:10算法实现—磁盘调度 by niutao.linux
  9. 2014-06-07 11:54:45迭代算法的应用 by sxgkwei
  10. 2014-06-29 11:32:00用递归和非递归方法遍历二叉树的前,中,后序 by qqmmcc
  11. 2014-07-14 12:28:27顺序表操作 by 小项
相关聚客文章
  1. dianlujitao 发表 2014-10-17 13:32:08 POJ 2339 Rock, Scissors, Paper
  2. bystander 发表 2013-04-11 10:50:25 模板栈以及中缀表达式求值(C++实现)
  3. dianlujitao 发表 2014-10-17 13:42:33 POJ 3844 Divisible Subsequences
  4. dianlujitao 发表 2014-10-17 13:45:25 POJ 3122 Pie
  5. bystander 发表 2013-04-16 00:42:58 模板优先级队列及堆排序(C++实现)
  6. dianlujitao 发表 2014-10-17 13:52:22 POJ 2388 Who’s in the Middle
  7. surgesoft 发表 2014-10-28 08:01:58 LeetCode OJ: Restore IP Addresses
  8. espace 发表 2015-07-18 17:43:14 Two Sum
  9. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  10. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects
  11. bystander 发表 2013-05-15 10:37:24 倒水问题求解(C++)
  12. dianlujitao 发表 2014-10-17 14:11:26 POJ 1328 Radar Installation

发表评论