002. Even Fibonacci Numbers (피보나치 수 중에서 짝수 구하기)

​문제 (English)

Each new term in the Fibonacci sequince is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

$ 1,2,3,5,8,13,21,34,55,89,...$

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

 

Answer: 4613732

문제 분석

---

피보나치 수는 k = (k-1) + (k-2)가 되는 수 들이다. 이러한 수들 중에서 k%2==0이 되는 수만을 더하면 된다. 

더 이상 더 효율화할 수 있는 꺼리가 없다.

 

풀이

---

연속되는 피보나치 수를 {...a,x,y,z,b,..}라하면, z=y+x이다. 

이렇게 계산되고 난 후에, [x=y, y=z]로 놓고 다시 z=y+x를 구하면서 z값을 갱신하면, 연속되는 피보나치 수를 구할 수 있다.

let z = x + y, where x=1, y=1

let sum = 0

while z < bound 

    if z is even   

        sum += z

    x=y, y=z, z=x+y

return sum

 

Rust 소스 코드는, 

fn get_fibo_even_sum(bound: u64) -> u64{
    let mut sum: u64 = 0;
    let mut x = 1;
    let mut y = 1;

    let mut z = x + y;
    while z < bound{        
        if z%2 == 0 {
            sum += z;            
        }        
        x = y;  y = z;
        z = x + y;
    }
    return sum;
}

 

 

전체 소스코드

---

p2.rs 

#[test]
fn test(){
    assert_eq!(10, get_fibo_even_sum(10));    
    assert_eq!(44, get_fibo_even_sum(100));
}

#[cfg(test)]
fn get_fibo_even_sum(bound: u64) -> u64{
    let mut sum: u64 = 0;
    let mut x = 1;
    let mut y = 1;

    let mut z = x + y;
    while z < bound{        
        if z%2 == 0 {
            sum += z;            
        }        
        x = y;  y = z;
        z = x + y;
    }
    return sum;
}

 

끝