dynamicprogrammingtest.c

它建立在最优原则的基础上,采用动态规划方法,可以优雅而高效地解决许多用贪心技术或分治技术无法解决的问题。因此,动态规划技术越来越成为解决许多重要的应用问题的关键技术。矩阵连乘。

/**
* File    : DynamicProgrammingTest.c
 * Author  : Wind
 * Email   : [e-mail]
 * Date    : 2005-9-29
 * Purpose : Unit testing
 * */
#include <stdio.h>

#include "../head/Global.h"
#include "../head/Matrix.h"
#include "../head/DynamicProgramming.h"

#define MATRIX_LENGTH 6

void testInitMatrix(){
    MessageLine("Testing Matrix.c-initMatrix(Matrix * m);");
    Matrix m;
    int i=0;
    int j=0;
    int k=0;
    
    initialMatrix(&m,10,10);
    for(i=0;i<(&m)->row;i++){
        for (j = 0; j < (&m)->col; ++j) {
            *M(&m,i,j)=k++;
		}
    }
    printMatrix(&m);
    matrixTranspose(&m);
    
    MessageLine("matrix after transpose:");
    printMatrix(&m);
    destroyMatrix(&m);
}

void testMatrixMultiply(){
    MessageLine("Testing Matrix.c-matrixMultiply(Matrix * a,Matrix * b,Matrix * c);");
    Matrix a , b , c ;
    initialMatrix(&a,2,2);
    initialMatrix(&b,2,2);
    *M( &a,0,0)=1;
    *M( &a,0,1)=2;
    *M( &a,1,0)=3;
    *M( &a,1,1)=4;

    *M( &b,0,0)=5;
    *M( &b,0,1)=6;
    *M( &b,1,0)=7;
    *M( &b,1,1)=8;
    
    if(matrixMultiply(&a,&b,&c)){
        printMatrix(&c);
    }
    
    destroyMatrix(&a);
    destroyMatrix(&b);
    destroyMatrix(&c);
}

void testMatrixChainOrder(){
    MessageLine("Testing DynamicProgramming.c--int matrixChainOrder(Matrix matrixs [],int positions [],int matrixNum,int m,int n );");
    Matrix ms[MATRIX_LENGTH];
    int tokenLength=MATRIX_LENGTH*MATRIX_LENGTH;
    int token[tokenLength];
    int mini[tokenLength];
    int i=0;
    for (i = 0; i < tokenLength; ++i) {
        token[i]=-1;
    }
    for (i = 0; i < tokenLength; ++i) {
        mini[i]=-1;
    }
    
    initialMatrix(&ms[0],30,35);
    initialMatrix(&ms[1],35,15);
    initialMatrix(&ms[2],15,5);
    initialMatrix(&ms[3],5,10);
    initialMatrix(&ms[4],10,20);
    initialMatrix(&ms[5],20,25);
   
    
    matrixChainOrder(ms,mini,token,MATRIX_LENGTH,0,MATRIX_LENGTH-1);
    
    MessageLine("__________Token_____________");
    for (i = 0; i < tokenLength; ++i) {
		printf("%6d |",token[i]);
        if((i+1)%MATRIX_LENGTH==0){
            printf("\n");
        }
	}
    MessageLine("__________Mini_____________");
    for (i = 0; i < tokenLength; ++i) {
		printf("%6d |",mini[i]);
        if((i+1)%MATRIX_LENGTH==0){
            printf("\n");
        }
	}
    
    printf("\n");
    
    for ( i = 0; i < MATRIX_LENGTH; ++i) {
		destroyMatrix(&ms[i]);
	}
}

void testMatrixChainMultiply(){
    MessageLine("Testing DynamicProgramming.c--char * matrixChainMultiply(int tokenTable [],int tableLength,int tbColLength,int p1, int p2,char * order);");
    Matrix ms[MATRIX_LENGTH];
    int tokenLength=MATRIX_LENGTH*MATRIX_LENGTH;
    int token[tokenLength];
    int mini[tokenLength];
    int i=0;
    for (i = 0; i < tokenLength; ++i) {
        token[i]=-1;
    }
    for (i = 0; i < tokenLength; ++i) {
        mini[i]=-1;
    }
    
    initialMatrix(&ms[0],30,35);
    initialMatrix(&ms[1],35,15);
    initialMatrix(&ms[2],15,5);
    initialMatrix(&ms[3],5,10);
    initialMatrix(&ms[4],10,20);
    initialMatrix(&ms[5],20,25);
   
    
    matrixChainOrder(ms,mini,token,MATRIX_LENGTH,0,MATRIX_LENGTH-1);
    
    char order[]="";
    matrixChainMultiply(token,tokenLength,MATRIX_LENGTH,0,MATRIX_LENGTH-1,order);
    
    MessageLine(order);
    
    for ( i = 0; i < MATRIX_LENGTH; ++i) {
        destroyMatrix(&ms[i]);
    }  
}