Good job! Can you prove this recurrence for only even-valued terms in the Fibonacci sequence? That is, if we let the sequence be a, a0 = 0, a1 = 2, a2 = 8, a3 = 34, …, and so on. The recurrence is this: a0 = 0, a1 = 2, an = a[n-1]*4 + a[n-2] for n >= 2. It’ll be a good exercise on Fibonacci numbers. Good luck!
피보나치 수열 a는 다음과 같이 귀납적으로 정의된다.
a0 = 0, a1 = 1,
a[n] = a[n-1] + a[n-2] (n>=2)
또, 수열 a에서 짝수 값을 갖는 항은
a0 = 0 (even), a1 = 1 (odd)
a2 = a1 + a0 = (odd) + (even) = (odd)
a3 = a2 + a1 = (odd) + (odd) = (even)
a4 = a3 + a2 = (even) + (odd) = (odd)
a5 = a4 + a3 = (odd) + (even) = (odd)
a6 = a5 + a4 = (odd) + (odd) = (even)
...계속.
에 의해서
a[3k] (k는 0 이상인 정수)
뿐이다.
피보나치 수열에서 짝수 값만 가지는 수열*only* even-valued terms in Fibonacci sequence
b를 정의해보자. b는 위 내용에 따라서
b[n] = a[3n]
으로 둘 수 있다. 수열 a를 새롭게 풀어보면
b[n] = a[3n]
= a[3n-1] + a[3n-2]
= a[3n-2] + a[3n-3] + a[3n-2]
= 2 * a[3n-2] + a[3n-3]
= 2 * (a[3n-3] + a[3n-4]) + a[3n-3]
= 3 * a[3n-3] + a[3n-4] + a[3n-5] + a[3n-6]
= 4 * a[3n-3] + a[3n-6]
= 4 * b[n-1] + b[n-2]
따라서, 수열 b를 다음과 같이 귀납적으로 정의할 수 있다.
b0 = 0, b1 = 2,
b[n] = 4 * b[n-1] + b[n-2] (n>=2)
근데, 내가 맞게 한건가?
Samsung 3D LED TV Full commercial (60 Sek.)
"오해 하나를 바로 잡자. 프로그래밍 언어가 컴퓨터를 돌리기위해 만들어진 것이 아니다. 컴퓨터가 프로그램을 돌리기위해 만들어진 것이다. 만들어진 컴퓨터를 사용하기위해 고안한 것이 프로그래밍 언어가 아니고, 그 전에 이미 논리학자와 수학자들이 프로그래밍 언어를 고안했다. 그리고 나서 전기회로로 구현된 디지탈 컴퓨터가 발명되었다."
SNU 4190.310 Programming Languages ©Kwangkeun Yi, Seoul National Univ., 2006
원래 소스는 앞의 두 항을 받아서 400만 미만의 값들을 더하는 형태였는데, 문제의 답을 구하는 데에는 충분했지만 문제에서 주어진 것이 아닌 다른 질의를 하려면 굉장히 귀찮아지는 단점이 있었다. 때문에 두 수를 받아서 범위 내에 있는 피보나치 수열의 짝수 항을 더하도록 다시 만들었다.
def sum_even_fib(minimum, maximum, a=0, b=1):
'''
This recursion function is to find the sum of all even-valued terms in
the Fibonacci sequence which is more than minimum and do not exceed
maximum.
>>> sum_even_fib(1, 4000000)
4613732
>>> sum_even_fib(1, 1000)
798
>>> sum_even_fib(123, 456)
144
'''
c = a + b
if c > maximum:
return 0
if c >= minimum and c % 2 == 0:
return c + sum_even_fib(minimum, maximum, b, c)
else:
return sum_even_fib(minimum, maximum, b, c)
if __name__ == "__main__":
print sum_even_fib(1, 4000000)
Python의 doctest 모듈도 한번 써봤다.
