PrepBro
← Назад к вопросам

Числа Фибоначчи с мемоизацией

1.8 Middle🔥 191 комментариев
#Конкурентность и горутины#Кэширование#Основы Go

Условие

Реализуйте функцию вычисления n-го числа Фибоначчи с мемоизацией (кэшированием результатов).

Сигнатура

func fibonacci(n int) int

Требования

  • Использовать мемоизацию для избежания повторных вычислений
  • F(0) = 0, F(1) = 1
  • F(n) = F(n-1) + F(n-2)

Примеры

fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(10) = 55 fibonacci(20) = 6765

Бонус

Реализуйте потокобезопасную версию с использованием sync.Map или sync.Mutex.

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение

Реализуем функцию вычисления чисел Фибоначчи с мемоизацией.

Простая версия с кэшем

func fibonacci(n int) int {
    cache := make(map[int]int)
    
    var fib func(int) int
    fib = func(x int) int {
        if x <= 1 {
            return x
        }
        
        if val, ok := cache[x]; ok {
            return val
        }
        
        result := fib(x-1) + fib(x-2)
        cache[x] = result
        return result
    }
    
    return fib(n)
}

Потокобезопасная версия с sync.Map

var fibCache sync.Map

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    
    val, ok := fibCache.Load(n)
    if ok {
        return val.(int)
    }
    
    result := fibonacci(n-1) + fibonacci(n-2)
    fibCache.Store(n, result)
    return result
}

Быстрая итеративная версия

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

Анализ сложности

  • Простая мемоизация: O(n) время, O(n) память
  • sync.Map версия: O(n) время, O(n) память, потокобезопасна
  • Итеративная: O(n) время, O(1) память

Для production рекомендуется итеративная версия.

Числа Фибоначчи с мемоизацией | PrepBro