짝수인 피보나치 수의 합을 구하라.
n번째 피보나치 수열을 구하는 최속 알고리즘은 2 by 2 행렬을 이용하는 것으로 잘 알려져 있다. (O(log2n)) 하지만 본 문제에서는 한계가 4백만으로 낮으므로, 직접 구하도록 한다. 3n-1 번째 숫자만이 짝수이므로 나머지 검사를 할 필요는 없다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
use integer; sub addUntil { my $i = shift; my @n = (1,1,2); my $r; while($n[2] <= $i) { $r+=$n[2]; $n[0]=$n[1]+$n[2]; $n[1]=$n[0]+$n[2]; $n[2]=$n[0]+$n[1]; } return $r; } printf("%d",addUntil(4000000)); |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <stdio.h> unsigned long int addUntil(unsigned long int); unsigned long int addUntil(unsigned long int end) { unsigned long int result = 0; unsigned long int nth[3] = { 1, 1, 2 }; while (nth[2] <= end) { result += nth[2]; nth[0] = nth[1] + nth[2]; nth[1] = nth[2] + nth[0]; nth[2] = nth[0] + nth[1]; } return result; } void main(void) { printf("%lu\n", addUntil(4000000UL)); } |