본문 바로가기

재귀함수2

[C/자료구조] 하노이탑 문제 하노이탑이란? 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 하노이탑의 조건 한 번에 한개의 원판만 옮길 수 있다. 맨 위에 있는 원판만 이동할 수 있다. 크기가 작은 원판위에 큰 원판이 쌓일 수 없다. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다. 이제 문제 자체는 이해했으니, 이를 체계적으로 정의해보자. "체계적"이라함은, 문제의 입력과 출력을 보다 함수에 가깝게 정의하자는 것이다. 우리는 "원반의 이동횟수를 최소화하고자 할 때, 각 원반을 옮기는 모든 순서를 출력하는 것"으로 한다. 이때 각 이동의 출력은 '3번 원반을 A에서 C와 같이로 정하며.. 2022. 10. 22.
[C/자료구조] 재귀함수를 이용한 피보나치 수열과 반복문을 이용한 피보나치 수열 피보나치 수열이란? 피보나치 수열이란 다음과 같이 정의되는 수열이다 피보나치 수열에서는 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만든다. 정의에 따라 수열을 만들어 보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 피노나치 수열은 이탈리아 수학자 피보나치(Fivonacci)가 발견한 수열로서 한 쌍의 토끼가 번식하는 상황을 수열로 만든 것이다. 피보나치 수열은 수학과 과학의 많은 분야에서 사용되고 있다. 피보나치 수열은 정의 자체가 순환적으로 되어 있다. 따라서 구현 시에 순환 호출을 사용하는 것이 자연스러운 방법이다. 피보나치 수열을 재귀함수로 이용하여 프로그램해 보면 다음과 같다. #define _CRT_SECURE_NO_WARNINGS #i.. 2022. 10. 21.

티스토리툴바