현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

C 피보나치 재귀함수 질문있습니다.

godgod4801의 이미지
글쓴이: godgod4801 / 작성시간: 금, 2018/10/19 - 8:41오후

안녕하세요!
이제막 프로그래밍 배우기 시작한 완전 초보입니다.

똑똑한 프로그래머님들께 질문이 있습니다..
오늘 피보나치 재귀함수코드에 대해서 과제를 받았는데, 뭐부터 어떻게 써내려가야할지 모르겠네요..

출력은 아래처럼 나와야하고,
----------------------------------------
숫자를 입력하세요: 4
5 Fib(4) = 3

숫자를 입력하세요: 6
9 Fib(6) = 8
----------------------------------------

조건은,

• nummer는 Lese_int를 사용하여 읽습니다.
• 추가 출력은 한 줄로 제한됩니다.
• 루프가 사용되지 않습니다.
• 숫자를 입력시 화면 같이 표시됩니다.

이렇습니다..

현재 제가 쓴 코드는 아래와 같은데, 학교에서 준 예시를 거의 복붙한 상태밖에 안되네요.
수업때 설명을 충분히 해주고 과제를 주어야하는데, 피보나치에 대해서 설명도 없이 해오라고 하니
전혀 모르겠네요....ㅜㅜ.

똑똑한 프로그래머님 불쌍한 새내기 도와주세요..

File attachments: 
첨부파일 크기
Image icon 피보나치.png183.25 KB
Forums: 
프로그래밍 QnA
세벌의 이미지

글쓴이: 세벌 / 작성시간: 토, 2018/10/20 - 3:40오전

1. 피보나치 수 모르면 구글에게 물어보면 됩니다. 처음부터 다 아는 사람 없으니 포기하진 마시길.

https://en.wikipedia.org/wiki/Fibonacci_number
풀어 쓰면
Fib(1) = 1
Fib(2) = 1
Fib(3) = Fib(2)+Fib(1) = 1+1 = 2
Fib(4) = Fib(3)+Fib(2) = 2+1 = 3
Fib(5) = Fib(4)+Fib(3) = 3+2 = 5
Fib(6) = Fib(5)+Fib(4) = 5+3 = 8
...

2. 피보나치 수 알려드렸으니, 프로그램 만들면 됩니다. 아래 코드 참고하세요.

#include <stdio.h>
int Fib(int n);
 
int main()
{
	int num;
 
	printf("Input a number: ");
	scanf("%d", &num);
 
	printf("Fib(%d) = %d\n", num, Fib(num) );
}
 
int Fib(int n)
{
	if(n<1) return 0;
	if(n==1) return 1;
	if(n==2) return 1;
 
	return Fib(n-1) + Fib(n-2);
}

3. kldp에서 코드 넣는 방법은 https://kldp.org/node/158191 참고하세요.
소스코드를 화면 캡처해서 이미지 파일 첨부하시면 답하기 어렵습니다.

사족.

수업때 설명을 충분히 해주고 과제를 주어야하는데, 피보나치에 대해서 설명도 없이 해오라고 하니
대학생이죠? 대학교 수업이 원래 그래요. 잘 이겨내시길...

세벌 https://sebuls.blogspot.kr/

godgod4801의 이미지

글쓴이: godgod4801 / 작성시간: 토, 2018/10/20 - 5:24오전

아 그렇군요!! 다음부터 저렇게 코드 처리해서 올리겠습니다.
네 맞습니다.. 대학교 수업진행중인데.. 정말 신세계 경험하고 있습니다..
오늘 10시간동안 여기 저기 엄청 다 찾으면서 코드 얼추 적었었는데, 마지막 결과가 합한 숫자로 안나오고 연계되서 나오더라구요.
그건 어떻게 해야할지 몰라서 계속 끙끙하고 있었는데, 적어주신 코드보고 시원하게 이해됬습니다. 이렇게 깔끔하게 정리할 수 있네요. 눈물나네요ㅜㅜ
너무 감사합니다..!!

세벌의 이미지

글쓴이: 세벌 / 작성시간: 일, 2018/10/21 - 2:09오전

재귀함수 연습용으로는 좋은 문제인데, 제 방법으로 풀려면 계산 시간이 꽤 걸립니다.
Fib(46) 구하는 데 한참 걸리더군요...

빠르게 계산하도록 프로그램을 고쳐보셔요. 조건을 살짝 바꾸어서 재귀함수 안 써도 되는 거로!

시간 날 때 해 보셔요.

세벌 https://sebuls.blogspot.kr/

세벌의 이미지

글쓴이: 세벌 / 작성시간: 일, 2018/10/21 - 11:16오후

재귀를 안 쓰는 예입니다. 참고하세요.

int Fib(int n)
{
	static int prev=1, fi=1, tmp;
	int i;
	if(n<1) fi=0;
	if(n==1) fi=1;
	if(n>1) {
		for(i=2;i<n;i++){
			tmp=fi;
			fi+=prev;
			prev=tmp;
		}
 
	}
	return fi;
}

세벌 https://sebuls.blogspot.kr/

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2018/10/22 - 4:57오전

여담으로 'Lese'_int, 'zahl'a 같은 걸 보니 독일어인 것 같군요. 조건에 있는 "• 루프가 사용되지 않습니다." 부분은 제가 보기에는 재귀 함수를 익히기 위해서 집어넣은 것 같으니까, "재귀를 안 쓰는 예"에 쓴 대로 제출하면 좋은 점수를 받을 수 없을 거라고 장담합니다.

루프를 안 쓰는 또 다른 방법이 있긴 한데... 지금 상황에서는 기초 따라가는 것에만 충실하세요.

세벌의 이미지

글쓴이: 세벌 / 작성시간: 월, 2018/10/22 - 5:59오전

변수 이름을 왜 암호처럼 쓰나 했더니 그게 독일어였군요.

문제에서 루프 안 쓰는 거라고 했으니, 재귀 안 쓰는 예는 좋은 점수 못 받는 거 당연하겠죠.

루프를 안 쓰는 또 다른 방법이 있긴 한데...
궁금해지네요. 어떤 방법인가요?

세벌 https://sebuls.blogspot.kr/

Anonymouse의 이미지

글쓴이: Anonymouse / 작성시간: 월, 2018/10/22 - 10:30오전

피보나치 수열은 generating function 을 이용해서 일반항을 만들 수 있습니다.
이를 이용하면 O(1) 로 피보나치 수를 구할 수 있습니다.

단, 일반항은 제곱근, 제곱, 나눗셈이 포함되므로 부동소수점 처리가 필요하고
결국 n 이 커지면 정확성이 떨어져서 정확한 수를 못 얻는다는 단점이 있습니다.
( bigfloat 이 필요하고 n제곱으로 인해 연산 속도도 떨어질 수 있습니다. )

이를 상쇄하기 위해 정수 연산만으로 정확한 수를 얻도록 식을 조정하려 할 경우
결국 n제곱에 대한 루프 연산이 필요해지므로 결국 O(1) 으로는 처리가 안됩니다.

n 범위가 작다면 상관은 없겠지만 근본적으로 해결하기는 어렵죠.
뭐 다른 방법이 있는지는 모르겠습니다만.

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2018/10/22 - 2:08오후

피보나치 수열의 n번째 항을 10진 표기법으로 나타냈을 때 자릿수가 이미 O(n)이라는 점을 생각해 보면,
결국 무슨 수를 써도 n번째 항을 O(n)보다 작은 시간복잡도로 계산할 수 없다는 사실을 알 수 있지요.
오라클이 나타나서 n번째 항을 그냥 불러주더라도 받아 적는 데만 O(n)의 시간이 걸릴 테니.

뭐 그렇게 따지면 세벌님의 코드도 O(n^2)이라고 해야 정확하겠습니다만.

사견입니다만 피보나치 수열 계산은 행렬 F = [1 1; 1 0]의 거듭제곱으로 계산하는 방식이 제일 흥미로웠던 것 같습니다. 일반항을 쓰는 방법도 재미는 있지만, 실수 연산을 하든 a+b√5꼴 계산을 하든 이래저래 골치아픈 일이여서요.

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.