컴퓨터 알고리즘 - c프로그램 알고리즘[코딩 및 출력결과]

본문내용

k의 값 배열\n\n");
for(i=1; i {
for(j=1; j {
printf("%d\t", Key[i][j]); // 최소값을 주는 k의 값을 출력
}
printf("\n");
}
printf("\n");
printf("n 개의 행렬을 곱하는 최적의 순서 : ");
// 최적의 순서를 구하는 함수를 호출 함수내에서 출력
order(1,Size);
printf("\n\n\n");
}
int minmult(int n, const int d[], int P[][Size+1]) // 최소곱셈 함수
{
int i, j, k, diagonal, min, tmp;
int M[Size+1][Size+1];
for(i=0; i<=n; i++)
for(j=0; j<=n; j++)
M[i][j] =0;
for(diagonal=1; diagonal<=n-1; diagonal++)
{
for(i=1; i<=n-diagonal; i++)
{
min = 99999999;// 초기 최대값을 임의로 설정
j = i + diagonal;
// i<= k <= j-1 를 만족하는 k를 for문을 이용하여
// 지정 하고 최소값을 구한다
for(k=i; k<= j-1; k++)
{
if(min > M[i][k] + M[k+1][j] + d[i-1] * d[k] * d[j])
{
min = M[i][k] + M[k+1][j] + d[i-1] * d[k] * d[j];
tmp = k;
}
}
M[i][j] = min; // 최소값과 그 최소값을 주는 k의 값을 각 배열에 저장
P[i][j] = tmp;
}
}
printf("\n\n기본 곱셈의 최소개수를 나타내는 행렬\n\n"); // 최소값을 출력부.
for(i=1; i {
for(j=1; j {
printf("%d\t", M[i][j]);
}
printf("\n");
}
printf("\n");
return M[1][n];// 구한값을 리턴한다.
}
void order(int i, int j) // 최적의 순서 출력 알고리즘
{
int k;
if(i == j)
printf("A%d", i); // 모든 행렬을 A라 지정하고 번호만을 부여한다.
else
{
k = Key[i][j];
printf("(");
order(i, k);// 재귀적호출
order(k+1, j);
printf(")");
}
}
void array_input(int n, int list[]) //배열내의 키값을 입력하기 위한 함수.
{
int i, j; //함수 선언.
srand(time(NULL)); //배열에 숫자 입력 부분
for(i=1; i<=n; i++)
list[i] = rand() % n; //랜덤하게 나온 숫자를 배열에 저장
for(i=1; i<=n; i++) //중복되는 숫자를 걸러내기 위한 알고리즘.
{
for(j=0; j < i; j++)
{
if(list[i]==list[j])
{
list[i] = list[i]+1;
i = i+1;
}
}
} //중복 숫자 걸러내기 끝.
}
알고리즘 3.6, 3.7 최소 곱셈,
최적의 순서 출력
(출력결과)
알고리즘 4.1 프림의 알고리즘
문제: 최소 비용 신장트리를 구하라
입력: 정수 n>=2와 정점의 개수가 n인 연결된, 가중치 포함 비방향그래프
출력: 그래프에 대한 최소비용 신장트리 안에 있는 이음선의 집합
#include
const int Size = 6;
int F[10], F2[10];// 정점의 인덱스를 저장할 배열
void prim(int n, const int W[][Size]);
void main()
{
int i, j;
int Key[Size][Size] = { // 교재의 그래프의 가중치를 2차원 배열 정의.
{8, 100, 6, 100, 6, 100,}, // 무한대는 100이라고 임의로 정의.
{7, 0, 6, 3, 4, 100},
{100, 1, 0, 3, 6, 100},
{5, 3, 5, 0, 4, 2},
{100, 100, 5, 4, 100, 5},
{100, 4, 100, 2, 5, 0}
};
prim(Size, Key); // 프림의 알고리즘 호출
printf("그래프의 가중치"); // 각 노드와 가중치의 값 출력
printf("\n");
for(i=1; i {
for(j=1; j {
printf("%d\t", Key[i][j]);
}
printf("\n");
}
printf("\n");
printf("그래프에 대한 최소비용 신장트리 안에 있는 이음선의 집합\n"); // 최소비용 신장트리 안에있는 정점을 출력한다.
for(i=2; i printf("(V%d~V%d)", F2[i], F[i]);
printf("\n");
}
void prim(int n, const int W[][Size])// 프림의 알고리즘
{
int i, j, vnear;
int min;
int *nearest, *distance; // 동적 배열할당
nearest = new int[n];
distance = new int[n];
for(i=1; i<=n; i++) // 첫 정점을 V1으로 초기화
{
nearest[i] = 1;
distance[i] = W[1][i];
}
for(j=1; j {
min = 99; // 무한대는 100이기 때문에 1작게 min 초기화
for(i=1; i {
if(distance[i] >=0 && distance[i] < min)
{
min = distance[i];
vnear = i;
}
}
}
F[j] = vnear; // 선택된 정점을 저장.
F2[j] = nearest[vnear];
distance[vnear] = -1; // 다음 정점을 선택.
for(i=2; i if(W[i][vnear] < distance[i])
{
distance[i] = W[i][vnear];
nearest[i] = vnear;
}
}
}
알고리즘 4.1 프림의 알고리즘
(출력 결과)

키워드

c프로그램 알고리즘,   코딩 및 출력결과,   알고리즘 1.1 순차검색