Description

I love Fibonacci numbers in general, but I must admit I love some more than others.

I would like for you to write me a function that when given a number (n) returns the n-th number in the Fibonacci Sequence.

For example:

nthfibo(4) == 2

Because 2 is the 4th number in the Fibonacci Sequence.

For reference, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

要点

斐波那契数列相邻两项的变化，可以通过一个线性变换得到，即

\[ \begin{bmatrix} a_n\\ a_{n+1} \end{bmatrix} = \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix} \begin{bmatrix} a_{n-1}\\ a_{n} \end{bmatrix} \]

Solutions

Julia



using Test


# 斐波那契数列对应的线性变换
F = [0 1; 1 1]
#> 2×2 Matrix{Int64}:
#>  0  1
#>  1  1

nthfibo(n::Int64)::Int64 = (F^(n-1)*[0, 1])[1]
#> nthfibo (generic function with 1 method)

@test nthfibo(4) == 2
#> Test Passed
#>   Expression: nthfibo(4) == 2
#>    Evaluated: 2 == 2

R

library(tidyverse)
Matrix <- modules::use("../src/R/toolkit/Matrix.R")

nthfibo <- function(n) {
    matrix_pow <- Matrix$`%^%`
    F <- c(0, 1, 1, 1) %>%
        matrix(2)

    (matrix_pow(F, n - 1) %*% c(0, 1))[1, 1]
}

nthfibo(4) == 2
#> [1] TRUE