문제 2: 피보나치 수열에서 400만 개 미만의 항 중 짝수 항의 합을 구하세요.

<?php

/**
 * 题目2：在斐波那契数列中，找出4百万以下的项中值为偶数的项之和。
 *
 * @autor 花生米
 * @date  2015-09-08
 * @desc  php version 5.4.33
 */

$max = 40000000000;

/**
 * 思路1
 * 时间复杂度：O(n)
 * 这是最容易想到的方法
 */
if (false) {
    $a = 1;
    $b = 2;
    $s = 0;//总和
    while ($b < $max) {
        //偶数则加
        if (($b & 1) == 0) {
            $s += $b;
        }
        $t = $b;
        $b = $a + $b;
        $a = $t;
    }
}

/**
 * 思路2：（优）
 * 时间复杂度：O(n)
 * 斐波那契数列
 * 0 1 1 2 3 5 8 13 21 34 55 89 144 ...
 *   a b c a b c a  b  c  a  b   c
 * 仔细观察可知，都是每三项一个偶数，而且
 * 8   = 4 * 2 + 0;
 * 34  = 4 * 8 + 2;
 * 144 = 4 * 34 + 8;
 * 故思路2就是这个方式来求解
 */
if (false) {
    $a = 0;//第一项从0开始
    $b = 2;//第二项从2开始
    $s = 0;
    while ($b < $max) {
        if (($b & 1) == 0) {
            $s += $b;
        }
        $t = $b;
        $b = 4 * $b + $a;
        $a = $t;
    }
}

저작권 안내: 이 글은 해당 블로거의 원본 글이므로 블로거의 허락 없이 복제할 수 없습니다.

위는 질문 2를 소개합니다. 피보나치 수열에서 400만 개 미만의 항 중에서 짝수인 항의 합을 구하세요. , 관련 내용을 포함하여 PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.