검색어 입력폼

알고리즘 연습문제

저작시기 2004.09 |등록일 2006.12.29 워드파일MS 워드 (doc) | 6페이지 | 가격 2,000원

소개글

연습문제 2장 부분입니다.

2.13 n개의 아이템으로 구성된 리스트를 크기가 거의 n/3인 3개의 부분리스트로 분할하고, 각 부분 리스트를 재귀적으로 정렬한 후, 그 3개의 정렬된 부분리스트를 합병하는 정렬 알고리즘을 작성하라. 작성한 알고리즘을 분석하고, 결과를 차수 표기법으로 표시하라.

2.17 하노이 탑 문제를 푸는 분할정복 알고리즘을 작성하라.
(a) 작성한 알고리즘이 S(n) = 2n – 1 임을 보여라. (S(n) 은 옮기는 횟수, n은 디스크의 개수이다)
(b) 어떤 다른 알고리즘도 최소한 (a)에서 주어진 횟수만큼은 옮겨야 한다는 사실을 증명하라.

컴파일 실행환경

워드파일입니다

본문내용

void mergeSort(int end, int S[]){
int i, j;
int left, mid, right;
int X[], Y[], Z[];

if (end > 1){
left = end/3; mid = (end - left)/2; right = end - left - mid;
X = malloc(left * sizeof(int));
Y = malloc(mid * sizeof(int));
Z = malloc(right * sizeof(int));
for(i = 0, l = 0; i < left; i++) { X[i] = S[j++]; }
for(i = 0; i < mid; i++) { Y[i] = S[j++]; }
for(i = 0; i < right; i++) { Z[i] = S[j++]; }
mergeSort(left, X); //왼쪽부분 재귀적 호출.
mergeSort(mid, Y); //가운데 부분 재귀적 호출.
mergeSort(right, Z); //오른쪽 부분 재귀적 호출.
merge(left, mid, right, X, Y, Z, S); //merge로 합치기..
}
}
void merge(int a, int b, int c, int X[], int Y[], int Z[], int S[]){
int i, j, k, l;
i = j = k = l = 0; //모든 인덱스가 0부터 시작.
while (i < a && j < b && k < c){
if(X[i] <= Y[j] && X[i] <= Z[k] ) { S[l++] = X[i++]; } //x가 작을 때
if(Y[j] <= X[i] && Y[j] <= Z[k] ) { S[l++] = Y[j++]; } //y가 작을 때
if(Z[k] <= X[i] && Z[k] <= Y[j] ) { S[l++] = Z[k++]; } //z가 작을 때
}
다운로드 맨위로