Фибоначчи в линейном времени с помощью дополнительного указателя

У меня есть функция для нахождения n-го числа в последовательности Фибоначчи, в которой я рекурсивно вызываю функцию. Сумма хранится в переменной класса, и у меня есть дополнительный указатель, который я увеличиваю каждый раз при вызове функции.

Этот дополнительный указатель является хранителем ворот, который диктует базовый случай, когда выходить из цикла. Производительность, которую я получаю, использует этот алгоритм: \ $ O (n) \ $ линейное время и пространство \ $ O (1) \ $.

Я получаю ожидаемый ответ, но я смущен, если это приемлемое решение из цитаты из интервью.

var x = 0
var sum = 0
func myFibonacci(of n: Int, a: Int, b:Int) -> Int {
  x+=1
  if (x == n) {
    return sum
  } else {
    sum = a+b
    return myFibonacci(of: n, a: b, b: sum)
  }
}

let finalAns = myFibonacci(of: 9, a: 0, b: 1)
print("The nth number in Fibonacci sequence is \(finalAns)")

Выход: 34

Сложность времени: \ $ O (n) \ $ линейное время

Сложная сложность \ $ O (1) \ $

Это приемлемое решение для интервью по кодированию?

8 голосов | спросил paddy 28 ThuEurope/Moscow2017-12-28T11:47:07+03:00Europe/Moscow12bEurope/MoscowThu, 28 Dec 2017 11:47:07 +0300 2017, 11:47:07

1 ответ


12

В вашей функции используются глобальные переменные , что плохо по нескольким причинам:

  • Переменные должны быть сброшены до того, как функция снова будет вызвана.
  • Переменные могут быть изменены извне вашей функции, вызывая неправильные результаты.
  • Функция не является потокобезопасной.

Кроме того,

  • Логика программы не сразу очевидна (по крайней мере, это было не для меня).
  • Вызов функции с помощью n <= 0 вызывает переполнение целых чисел.

Глобальные переменные часто являются проблематичными, и здесь их можно легко избежать, делая код не только более безопасным, но и проще.

Во-первых, глобальная переменная sum устраняется путем создания он локальный:

var x = 0
func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    x += 1
    if (x == n) {
        return b
    } else {
        let sum = a + b
        return myFibonacci(of: n, a: b, b: sum)
    }
}

или полностью устранить:

var x = 0
func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    x += 1
    if (x == n) {
        return b
    } else {
        return myFibonacci(of: n, a: b, b: a + b)
    }
}

Теперь избавьтесь от глобальной переменной x, уменьшив n вместо в рекурсивном вызове:

func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    if n == 1 { 
        return b // Recursion terminates here
    }
    return myFibonacci(of: n - 1, a: b, b: a + b)
}

С небольшой модификацией он работает для n = 0. Отрицательные аргументы следует улавливать вместо рекурсии до тех пор, пока не произойдет переполнение целых чисел:

func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    precondition(n >= 0, "`n` must be non-negative")
    if n == 0 {
        return a // Recursion terminates here
    }
    return myFibonacci(of: n - 1, a: b, b: a + b)
}

Это то, что я ожидал бы в качестве рекурсивной реализации в интервью по кодированию (конечно, вы также можете реализовать его итеративно, или используйте выражение закрытой формы , например формулу Бине).

В качестве бонуса вы можете реализовать его и для отрицательных аргументов, сравните Обобщения чисел Фибоначчи :

func myFibonacci(of n: Int, a: Int, b: Int) -> Int {
    if n == 0 {
        return a // Recursion terminates here
    } else if n > 0 {
        return myFibonacci(of: n - 1, a: b, b: a + b)
    } else {
        return myFibonacci(of: n + 1, a: b - a, b: a)
    }
}
ответил Martin R 28 ThuEurope/Moscow2017-12-28T12:07:00+03:00Europe/Moscow12bEurope/MoscowThu, 28 Dec 2017 12:07:00 +0300 2017, 12:07:00

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132