[자료구조 프로그래밍 연습문제] 재귀함수, 선택정렬, 배열

1. recursion

 

교재 Figure 1.3의 C 코드에서 수업시간에 언급된 오류를 차고 정확한 코드로 수정하시오. 수정하지 않을 경우 실행 결과에 어떤 오류가 발생하는지 간단한 예를 들어 설명하시오.

 

float rsum(float list[], int n)
{
    if (n) return rsum(list, n-1) + list[n-1];
    return 0;
}

0 대신 list[0]의 값을 반환하면, list배열의 값들의 전체 합에 첫번째 요소 값이 한 번 더 더하여져서 값이 달라진다. 예를 들어, list == [1, 2, 3, 4, 5] 인 경우, rsum의 결과 값은 1 + 1 + 2 + 3 + 4+ 5, 16으로 첫번째 요소인 1만큼의 오차가 발생한다.

 

 

2. recursive implementation of selection sort

 

아래는 list[i], ..., list[n-1] 의 값 중 최소값이 list[min]에 있다고 할 경우 min을 반환하는 C 함수이다.

int find_min (int list[], int i, int n) { // assuming 0 <= i < n
	int j, min;
	min = i;
	for (j = i+1; j < n; j++)
		if (list[j] < list[min]) min = j;
	return min;
}

 

A. find_min(list, 0, 100)이 호출되었다고 하자. list[0], ..., list[99]의 값 중 최소값은 20인데 세 원소 list[7], list[25], list[70]에 저장되어 있다고 할 경우 (즉, list[7]=list[25]=list[70]=20), 반환되는 min 값은 얼마인가?

 

7이다. (if문의 조건이 list[j] (새로 검사하는 값) < list[min] (전 요소들 중 최소값)이기 때문이다.)

 

B. 교재 1장 Program 1.4: Selection sort의 C 함수 sort()를 find_min()을 이용하여 recursive version rsort()로 수정하시오. 소스코드와 rsort()가 정확히 정렬을 수행하는지 Program 1.4의 main()을 이용하여 테스트한 결과를 제출하시오.

void rsort (int list [], int n)
{
	int min, temp;
	for (int i = 0; i < n - 1; i ++) {
		min = find_min (list , i , n);
		SWAP(list[i], list [min], temp);
	}
}

 

C. find_min()의 recursive version rfind_min()을 작성하시오. rfind_min()이 정확히 작동하는지 B의 rsort()내의 find_min()을 rfind_min()으로 교체한 후 Program 1.4의 main()을 이용하여 테스트한 결과를 제출하시오.

int rfind_min(int list [], int i, int n)
{
	int min;
	if (i < n) {
		min = rfind_min(list, i + 1, n);
		return (list[i] < list[min] ? i : min);
	}
	return n - 1 ;
}

 

 

3. 배열 관련 syntax

 

A. 교재 2장 Example 2.1에서 사용한 Program 2.2를 컴파일 및 실행하시오. 테스트 용 main()을 작성하여 호출.

#include <stdio.h>

void print1(int*, int);

int main()
{
	int one [] = { 0 , 1 , 2 , 3 , 4 };
	print1(&one[0], 5);
}

void print1(int* ptr, int rows)
{
	int i;
	printf("Address Contents\n");
	for(i = 0; i < rows; i ++)
		printf ("%8u%5d\n", ptr + i, *(ptr + i));
	printf ("\n");
}

 

B. Program 2.2에서 변수 ptr은 세 곳에서 사용되었는데 이들을 교재에 설명되어 있고 수업시간에 공부한 동일한 의미를 가진 C의 다른 syntax로 수정한 후 실행하여 A에서 Program 2.2를 실행했을 때와 동일한 결과가 나오는지 확인하시오. syntax 수정 전후 소스코드 및 실행 결과를 제출하시오.

#include <stdio.h>

void print1(int*, int);
void print2(int[], int);

int main()
{
	int one[] = { 0 , 1 , 2 , 3 , 4 };
	print1(&one[0], 5);
	print2(one, 5);
}

void print1(int* ptr, int rows)
{
	int i;
	printf("Address Contents\n");
	for(i=0; i<rows; i++)
		printf("%8u%5d\n", ptr + i, *(ptr + i));
	printf ("\n");
}

void print2(int ptr[], int rows)
{
	int i;
	printf("Address Contents\n");
	for(i=0; i<rows; i++)
		printf("%8u%5d\n", &ptr[i], ptr[i]);
	printf ("\n");
}