الگوریتم ضرب زنجیری ماتریس ها

الگوریتم ضرب زنجیری ماتریس ها 

برای دیدن این الگوریتم روی ادامه ی مطلب کلیک کنید.

Msmas.blogfa.com

#include

#include

#include

int p[10][10];

int minmult(int n,int *,int p[][10]);

void order(int,int);

void main(void) {

            int i,j,n,*d,result;

            clrscr();

            printf("Welcome, Please enter the number of Matrix (Max 10):");

            scanf("%d",&n);

            printf("Ok, You enter %d, that meaning you have %d Matrix for multiplication.\n",n,n);

            printf("Now, please enter the number of rows and columns for each matrix.\n\n");

            d=(int *)malloc(sizeof(int) * (n+1));

            for(i=0;i

                        printf("The number of rows for Matrix%d:",i+1); scanf("%d",&d[i]);

                        printf("The number of columns for Matrix%d:",i+1); scanf("%d",&d[i+1]);

                        printf("\n");

            }

            result=minmult(n,d,p);

            printf("The best order for multiplication is: ");

            order(1,n);

            printf("\nThe number of multiplication is: M[1][n]=%d",result);

            getch();

}//end of main

int minmult(int n,int *d,int p[][10]){

            int i,j,k,diagonal,temp;

            int M[10][10];

            for(i=0;i<10;i++) for(j=0;j<10;j++) M[i][j]=0;

            for(diagonal=1;diagonal<=n-1;diagonal++)

                        for(i=1;i<=n-diagonal;i++){

                                    j=i+diagonal;

                                    temp=k=i; M[i][j]=M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j];

                                    for(k=i+1;k

                                                if((M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j])

                                                            M[i][j]=M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j];

                                                            temp=k;

                                                }

                                    p[i][j]=temp;

                        }

            return M[1][n];

}//end of minmult

void order(int i,int j){

            int k;

            if(i==j)

                        printf("A%d",i);

            else{

                        k=p[i][j];

                        printf("(");

                        order(i,k);

                        order(k+1,j);

                        printf(")");

            }

}//end of order

/*int r,t;

printf("n=%d\n",n);

for(r=0;r<=n;r++) printf("d[%d]=%d ",r,d[r]); printf("\n");

printf("p\n"); for(r=1;r<10;r++){ for(t=1;t<10;t++) printf("%d ",p[r][t]); printf("\n"); }

printf("M\n"); for(r=1;r<10;r++){ for(t=1;t<10;t++) printf("%d    ",M[r][t]); printf("\n"); }*/