피 보 나치 알고리즘 의 세 가지 해법 (swift)

제목:
피 보 나치 수 는 보통 F (n) 로 표시 되 는데 형 성 된 서열 을 피 보 나치 수열 이 라 고 한다.이 수열 은 0 과 1 로 시작 되 며, 뒤의 모든 숫자 는 앞의 두 개의 숫자 를 합 친 것 이다.즉:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2),    N > 1.

주어진 N, 계산 F (N).
해법:

//    ：    ，      O(2^n)
func fib(_ n : Int) -> Int{
    if n <= 1 {
        return n
    }
    return fib(n-2) + fib(n-1)
}

//    ：  ，     O(n)
func fib(_ n : Int) -> Int{
    if n <= 1 {
        return n
    }

    var first : Int = 0
    var second : Int = 1
    for _ in 1.. Int{
    let c : Double = sqrt(5)
    
    return Int((pow((1+c)/2, Double(n)) - pow((1-c)/2, Double(n)))/c)
}