クエリで Project Euler Problem 2

7887 ワード
初心者 SQLServer アルゴリズム ProjectEuler SQLServer テキストリンク

【お題】

Problem 2。

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

400万という数字に一瞬たじろぐけど、フィボナッチ数列って指数関数的に増加するから、あっという間に到達するんだよな。

【環境】

SQLServer SQLCMD
2017 14.0.1000.169

設定はデフォルト。

【クエリ 1】

偶数値の項は 3個毎に出現するから、3個一行に並べて縦に集計すればいい。

クエリに起こすと以下。

DECLARE @1st    INT = 1;                    -- 最初の項
DECLARE @2nd    INT = 2;                    -- 二つ目の項
DECLARE @Max    INT = 4000000;              -- 最大値

;WITH [CTE_Fib]([a], [b], [c]) AS (
    SELECT
          @1st
        , @2nd
        , @2nd + 1st
    UNION ALL
    SELECT
          [c] + [b]
        , ([c] + [b]) + [c]
        , (([c] + [b]) + [c]) + ([c] + [b])
    FROM [CTE_Fib]
    WHERE   ([c] + [b]) + [c] <= @Max
)
SELECT SUM([b]) FROM [CTE_Fib]
;
GO

-----------
    4613732

(1 行処理されました)

【クエリ 2】


で良ければ（ダメだろ）以下。

DECLARE @2nd    DEC(7, 0)   = 2;            -- 二つ目の項
DECLARE @Para   DEC(10, 9)  = 4.236067675;  -- 偶数項算出係数
DECLARE @Max    INT         = 4000000;      -- 最大値

;WITH [CTE_Fib]([b]) AS (
    SELECT @2nd
    UNION ALL
    SELECT CONVERT(DEC(7, 0), [b] * @Para) FROM [CTE_Fib]
    WHERE   [b] * @Para <= @Max
)
SELECT SUM([b]) FROM [CTE_Fib]
;
GO

----------------------------------------
                                 4613732

(1 行処理されました)

13桁以下の偶数までなら一応これでも求まる。それより大きいと誤差が発生するけど。