(자료구조) 대학수업 Fibonacci 수열, 서로소

과제 #02

Fibonacci 수열은 F[0] = 0, F[1] = 1, 그리고 i>1에 대해 F[i-1]+F[i-2]로 구성된다.
단계 1. N(0≤N≤30)값을 scanf_s로 입력 받아라. 입력된 값이 허용 범위를 벗어나면 수행을 멈춘다.
단계 2. Malloc을 이용하여 N+1개의 정수를 저장할 수 있는 배열을 생성하라.
단계 3. Iteration으로 Fibonacci 수열을 구현하고 단계 2의 배열을 이용하여 F(N)값을 계산 및 출력하라.
단계 4. 단계 3을 수행하는데 걸린 계산 시간을 출력하라.
단계 5. Malloc된 배열을 free시킨다.
단계 6. Recursion을 이용하여 Fibonacci수열을 구현하고 F(N)값을 계산하여 출력하라.
단계 7. 단계 6을 수행하는데 걸린 계산 시간을 출력하라.
단계 8. 단계 1부터 다시 반복하여 수행한다.
<계산시간 측정코드>

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main()
{
	clock_t start, finish;
    double elapsed;
    start = clock();
    //수행 시간을 측정할 프로그램 코드가 들어갈 부분임.
    finish = clock();
    
    //아래는 start의 finish 사이의 명령이 수행되는데 걸린 시간을 millisecond 단위로 환산하여 출력하는 명령임.
    elapsed =((double)(finish) - (double)(start)) / CLOCKS_PER_SEC;
    printf("time: %f\n", elapsed * 1000.0);
    return 0;
}

예제:
컴퓨터학부 202020394 홍길동
(scanf_s) 3
(화면출력) 2
(scanf_s) 2
(화면출력) 1
(scanf_s) 6
(화면출력) 8
(scanf_s) -1
계산시간: ???ms

문제 풀이

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int fibonacci(int n) {
	if (n == 0) {
		return 0;
	}
	else if (n == 1 || n == 2) {
		return 1;
	}
	
	else {
		return fibonacci(n - 2) + fibonacci(n - 1);
	}
}

int main() {
	
	
	clock_t start, finish;
	double elapsed;
	while (1) {
		int N; // 정수 개수

		scanf_s("%d", &N, sizeof(N));
		if (N < 0 || N > 50) {
			printf("허용 범위를 벗어납니다.\n");
			return 0;
		}
		int* array;
		start = clock();
		array = (int*)malloc(sizeof(int) * (N + 1));

		for (int i = 0; i < N + 1; i++) {
			if (i == 0) {
				array[i] = 0;
			}
			else if (i == 1) {
				array[i] = 1;
			}
			else {
				array[i] = array[i - 1] + array[i - 2];
			}

		}

		finish = clock();
		printf("F(%d)값 :%d\n", N, array[N]);


		free(array);


		
		elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
		printf("time: %f\n", elapsed * 1000.0);

		int result = 0;
		start = clock();
		result = fibonacci(N);

		printf("F(%d)값 :%d\n", N, result);



		finish = clock();
		elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
		printf("time: %f\n", elapsed * 1000.0);
	}
	return 0;
}

주의해줘야 할 점 : scanf만 쓰다가 scanf_s를 쓰기 시작하다보니 생소해서 쓰는 법을 찾느라 헤맸던거 같다. 재귀함수 쓸 때는 base case를 꼭 생각해주자.

새로 알게 된점 : 문제를 iterasive function과 recursive function으로 풀었는데 시간을 측정하였을 때 iterasive function은 말 그대로 반복 함수 이므로 자신에게서 자신에게로 함수가 적용됨으로 0으로 수렴한다. 그래서 시간을 측정할 때 recursive function, 재귀 함수는 숫자가 커질수록 시간이 증가하고 iterasive function, 반복 함수는 0에 수렴한다.

결과

추가과제#02

다음은 주어진 두 개의 정수 x,y가 서로소인 지 판단하기 위한 recursive equation 이다.
prime(x, y) =
{if x = 1 or y = 1 (base case) [true]
{if x ≠ 1, y ≠ 1 and x = y (base case) [false]
{if x ≠ 1, y ≠ 1 and x < y (recursive case) [prime(x,y-x)]
{if x ≠ 1, y ≠ 1 and x > y (recursive case) [prime(x-y,y)]
파일(in.txt)에 저장된 두 개의 정수 x,y를 입력 받아, 위의 식을 이용하여 recursive program을 작성하여, x와 y가 서로소인 지 판별하여 서로소이면 true, 서로소가 아니면 false를 출력하라.(서로소란 1 이외에 공약수를 갖지 않는 두 정수를 말한다.)

예제 :
입력 : (in.txt) 3 12
출력 : false
입력 : (in.txt) 12 15
출력 : false
입력 : (in.txt) 17 21
출력 : true
입력 : (in.txt) 51 100
출력 : true

문제 풀이

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>


int r_prime(int a, int b) {
	if (b == 0) {
		return a;
	}
	else{
		return r_prime(b, a % b);
	}
} // 유클리드 호제법 알고리즘 사용
int main() {
	
	int x, y;
	FILE* fp = NULL;
	fopen_s(&fp, "in.txt", "r");
	if (fp == NULL) {
		return 0;
	}
	fscanf_s(fp, "%d %d", &x, &y);
	

	if (r_prime(x, y) == 1) {
		printf("true");
	}
	else {
		printf("false");
	}
}

주의해야 할 점 : 서로소를 구하는 방법은 유클리드 호제법을 알고 있으면 구하기 쉽다. 시간 날 때 알고리즘을 보는 법을 추천한다.

결과