Table of Contents

Even Fibonacci numbers #

Each new term in the Fibonacci sequence 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.

偶数斐波那契数 #

斐波那契数列中的每一项都是前两项的和。从 1 和 2 开始的前 10 项为：

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

求斐波那契数列中不超过 400 万的、值为偶数的各项之和。

知识点 #

斐波那契数列递推公式：

$$ F(n) = F(n-1) + F(n-2), \quad F(1)=1,\; F(2)=2 $$

暴力解法 #

逐项生成斐波那契数，若当前项为偶数则累加，直到超过 400 万：

total = 0
while current < 4_000_000:
    if current 为偶数:
        total += current
    生成下一项

C #

#include <stdio.h>

int main(void) {
    int first = 0;
    int second = 1;
    int total = 0;
    int current = first + second;

    while (current < 4000000) {
        if (current % 2 == 0) {
            total += current;
        }
        first = second;
        second = current;
        current = first + second;
    }

    printf("%d\n", total);
    return 0;
}

Java #

class Main {
    public static void main(String[] args) {
        int firstNumber = 0;
        int secondNumber = 1;
        int total = 0;
        int currentNumber = firstNumber + secondNumber;

        while (currentNumber < 4000000) {
            if (currentNumber % 2 == 0) {
                total += currentNumber;
            }
            firstNumber = secondNumber;
            secondNumber = currentNumber;
            currentNumber = firstNumber + secondNumber;
        }

        System.out.println(total);
    }
}

Go #

package main

import "fmt"

func main() {
	first, second := 0, 1
	total := 0
	current := first + second

	for current < 4_000_000 {
		if current%2 == 0 {
			total += current
		}
		first, second = second, current
		current = first + second
	}

	fmt.Println(total)
}

Rust #

fn main() {
    let mut first = 0;
    let mut second = 1;
    let mut total = 0;
    let mut current = first + second;

    while current < 4_000_000 {
        if current % 2 == 0 {
            total += current;
        }
        first = second;
        second = current;
        current = first + second;
    }

    println!("{}", total);
}

优化：每 3 项必有一个偶数 #

斐波那契数列的奇偶性按「奇、偶、奇、奇、偶、奇、奇、偶、……」循环，因此每 3 个连续项中恰有 1 个偶数，无需逐项判断奇偶。

偶数项子序列为 2, 8, 34, 144, ……，本身也满足递推。设连续两个偶数项为 E(n-2) 与 E(n-1)，则：

$$ E(n) = 4 \cdot E(n-1) + E(n-2) $$

以首两项 E(0)=2、E(1)=8 代入验证：

$$ 4 \times 8 + 2 = 34,\quad 4 \times 34 + 8 = 144 $$

直接遍历偶数项子序列，利用上述递推生成下一项，无需判断奇偶。

C #

#include <stdio.h>

int main(void) {
    int prev = 2;
    int curr = 8;
    int total = 2;

    while (curr < 4000000) {
        total += curr;
        int next = 4 * curr + prev;
        prev = curr;
        curr = next;
    }

    printf("%d\n", total);
    return 0;
}

Java #

class Main {
    public static void main(String[] args) {
        int prev = 2;
        int curr = 8;
        int total = 2;

        while (curr < 4000000) {
            total += curr;
            int next = 4 * curr + prev;
            prev = curr;
            curr = next;
        }

        System.out.println(total);
    }
}

Go #

package main

import "fmt"

func main() {
	prev, curr := 2, 8
	total := 2

	for curr < 4_000_000 {
		total += curr
		prev, curr = curr, 4*curr+prev
	}

	fmt.Println(total)
}

Rust #

fn main() {
    let mut prev = 2;
    let mut curr = 8;
    let mut total = 2;

    while curr < 4_000_000 {
        total += curr;
        let next = 4 * curr + prev;
        prev = curr;
        curr = next;
    }

    println!("{}", total);
}

两种方法结果均为 4613732。