[알고리즘] Minimum Matrix Multiplication,Binary Search Tree

목차

(1) Minimum Matrix Multiplication
(3) Binary Search Tree

본문내용

(1) Minimum Matrix Multiplication
- Implement algorithm 3.6 & 3.7, and show the final matrix M,P and the sequence of the multiplications based the sequence of the multiplications.
1-1)Source Code
#include
#define N 5 //행렬의 개수
int minmult(int n, const int d[], int P[][N+1]); //최소곱셈
void print_P(int P[N+1][N+1]); //출력
void order(int i, int j,int P[N+1][N+1]); //최적의 순서 출력
int main(void)
{
int d[N+1] = {10,4,5,20,2,50};//Ak의 열
int P[N+1][N+1] = {0}; //최적의 순서를 가진 2차원 배열
printf("M의 값 : %d ",minmult(N,d,P)); //최소곱셈 함수를 실행함과 동시에 M의 값을 return

<중 략>

배열 R은 최적 트리를 구축할 수 있는 2차원 배열로 선언되었다. 배열 R의 행의 인덱스의 범위는 1부터 n+1까지이고(즉 0을 제외하고 n+1의 배열을 쓰기 위해서 N+2를 선언하였다.), 열의 인덱스 범위는 0부터 n까지이기에 각각 N+1을 더하도록 하였다. 배열 A는 최적트리의 평균 검색시간을 저장하기 위해 선언되었으며 변수 minave는 최적 이진검색 트리에 대한 평균 검색시간을 출력하기 위해 선언되었다. 배열 p는 문제에서 주어진 값을 저장하기 위해 선언되었다. 다음에 실행되는 함수 optsearchtree는 첫 번째 인자로 N의 개수, 2번째 인자로 문제에서 주어진 값을 입력하는 배열p, 세 번째 인자로는 평균검색을 출력하기 위한 minavg의 변수, 네 번째와 다섯 번째는 각각 R과 A의 배열이다. 이 함수는 최적 이진검색 트리함수로써 최소 값을 주는 R의 값과 A의 값을 출력한다.

참고 자료

없음