matrix_multiplication.cpp

关于turborc,C语言运行程序,可以正常正常运行.希望有所帮助.

#include<string.h>
#include<stdio.h>
#define MAX 21
int p[MAX],ptr;
int m[MAX][MAX];
int s[MAX][MAX];

void prnt(int i, int j)
{
	if (i == j) {
		printf("A%d",i);
		return;
	}
	else if (i < j) {
		printf("(");
		prnt(i,s[i][j]);
		printf(" x ");
		prnt(s[i][j]+1,j);
		printf(")");
	}
	return;
}

int main()
{
	int N,temp_N,T;
	int hang,lie;
	int i,j,k,r,t;
	T = 0;
	while (scanf("\n%d",&N) !=EOF) {
		if (N == 0)
			break;
		T ++;
		temp_N = N;  ptr = 0;
		while (temp_N--) {
			scanf("\n%d %d",&hang,&lie);
			if (N-1 == temp_N) {
				p[ptr++] = hang;p[ptr++] = lie;
			}
			else p[ptr++] = lie;
		}
		for (i = 1;i <= N;i ++)
			m[i][i] = 0;

		for (r = 2;r <= N; r++) {
			for (i = 1;i <= N - r+1;i ++) {
				j = i + r - 1;
				m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
				s[i][j] = i;
				for (k = i + 1; k < j; k++) {
					t = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
					if (t < m[i][j]) {
						m[i][j] = t;
						s[i][j] = k;
					}
				}
			}
		}
		printf("Case %d: ",T);
		prnt(1,N);
		printf("\n");
	}
	return 0;
}