알고리즘 기초 홍릉과학 출판사 3장 솔루션

소개글

알고리즘 기초 홍릉과학출판사 3장 2,4,5,6,13,15,17,20,22,26,28,36 솔루션입니다.

목차

없음

본문내용

6.최단경로출력 알고리즘을 사용하여 연습문제 5의 그래프에서 정점 V7에서 V3로 가는 최단경로를 구하시오. 여기서 그 연습문제에서 구한 행렬 P를 사용하시오. 그리고 수행되는 절차를 단계별로 보이시오
q=7 r=3
P[7][3] =! 0
P[7][5] =! 0
P[7][4] = 0 V4
P[5][3] = 0 V5
V4 와 V5가 V7에서 V3으로가는 최단경로 상의 중간마디 들이다.
13. 다음 행렬들의 곱인 A1*A2*A3*A4*A5를 계산하는 최적 순서와 그 비용을 구하시오
A2의 크기는 (4*5)
A3의 크기는 (5*20)
A4의 크기는 (20*2)
A5의 크기는 (2*50)

<중 략>

20. 임의 양의 정수 d에 대해서 각 행렬의 크기가 1x1 또는 1xd 또는 dx1 또는 dxd인 n개 행렬 A1xA2...xAn을 곱하는 최적 순서를 찾는 알고리즘을 작성하시오. 작성한 알고리즘을 분석하고, 그 결과를 차수표기법을 사용하여 표시하시오.

void order(int i, int j)
{
int k;
if(i ==j)
cout <<"A"<<i;
else
{
k = P[i][j];
cout << "(";
order(i,k);
order(k+1,j);
cout << ")";
}
}

참고 자료

없음