題目2：在斐波那契數列中，找出4百萬以下的項中值為偶數的項總和。

<?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：在斐波那契數列中，找出4百萬以下的項中值為偶數的項總和。 ，包括了方面的內容，希望對PHP教程有興趣的朋友有所幫助。