gracia   2년 전

아래 코드는 1003번 문제에 c++11 숏코드 앞쪽에있는 blueahj88 님 채점번호 1340414번 코드인데요


for (a = 1, b = 0; num--; b += a, a = b - a)

이코드가 도대체 어떻게 나온건지 궁금합니다

심지어 1,2번째 피보나치수에도 적용 되는게 장난이 아니네요


그냥 직관이 아니라 알고리즘을 통해서 결과를 낸거 같긴한데
뭘 어떻게 시작 해야될지 접근 방법을 전혀 모르겠습니다

저 식을 유추해내는 알고리즘이 뭔가요?

chogahui05   2년 전

어려운 질문이네요.

fibo(n)을 재귀적으로 호출했을 때 0이 나오는 횟수를 z(n), 1이 나오는 횟수를 o(n)이라고 합시다.

이걸 일반화 된 식으로 풀긴 어려우니까요.


나열된 것들을 먼저 봅시다.

1.png그러면 대충 규칙이 보이실 텐데요. 일단, 감을 못 잡으실 거 같으니까 이 상태에서 zero와 one을 채워보도록 하겠습니다.


2.png이것 때문에 b = a+b가 나온 것이지요.

기존에 zero = a, one = b라고 했을 때 말이죠. 이 과정을 수행한 후에 b = 21, a = 8이 됩니다.

이 상태에서 b-a를 하면 13이 되겠죠?


1열만 채웠을 때 과정은 직접 그려 보세요.

제가 봤을 땐, 저 코드 작성자 분도 저런 규칙으로 하셨을 겁니다.

gracia   2년 전

알고리즘도 중요하지만 역시 직관도 그에 못지않게 중요하다는건가요..

혹시나 이런때에 쓰이는 알고리즘이 있나 궁금해서 물어본거였는데

뭐 듣고보니 가령 일반해를 이끌어 내는 방법이 있다고 해도

알고리즘적인 측면보다는 수학적인 요소가 많겠군요 점화식이라던가..


답변감사합니다!

댓글을 작성하려면 로그인해야 합니다.