Частичная сумма Фибоначчи, как улучшить производительность?

Question

Мне нужно улучшить производительность этого алгоритма. Я считаю, что ответ заключается в применении периода pisano.

Этот алгоритм должен вернуть последнюю цифру суммы чисел фибра из f (m) в f (n).

Вот то, что я до сих пор:

def fib(n) 
    a = [] 
    a << 0 << 1 
    (n+1).times do |i| 
     a << a[-1] + a[-2] 
    end 
    a[n] 
end 


def fib_partial_sum(m, n) 
    if n == m 
     fib(m) % 10 
    else 
     m = fib(m + 1) - 1 
     n = fib(n + 2) - 1 
     (n - m) % 10 
    end 
end 

if __FILE__ == $0 
    m, n = gets.split().map(&:to_i) 
    puts "#{fib_partial_sum(m, n)}" 
end 

Последняя цифра любого Фибо NUM повторяется каждые 60 номеров. Таким образом, мы можем сделать это, п, т = п% 60, м% 60. Улучшение, но не совсем там, терпит неудачу на входе 567717153638 567717153638):

def fib(n) 
    a = [] 
    a << 0 << 1 
    (n+1).times do |i| 
     a << a[-1] + a[-2] 
    end 
    a[n] 
end 

def fib_partial_sum(m, n) 
    if n == m 
     fib(m) 
    else 
     m = m % 60 
     n = n % 60 

     m = fib(m + 1) - 1 
     n = fib(n + 2) - 1 
     (n - m) % 10 
    end 
end 

if __FILE__ == $0 
    m, n = gets.split().map(&:to_i) 
    puts "#{fib_partial_sum(m, n)}" 
end 

Answer 1

Следующая требуется только один проход номера между нулем и не более [n,m+60].min, где m..n представляет собой диапазон интересов и имеет минимальную потребность в памяти. Это делает использование @ nloveladyallen обозрения, что последняя цифра чисел Фибоначчи имеет периодичность 60.

кодекса

def fib_last(m,n) 
    n -= 60*((n-m)/60) 
    fib_sum(m,n) % 10 
end 

def fib_sum(m,n) 
    return nil if m < 0 || m > n 
    return n if n < 2 
    next_to_last, last = fib(m-1) 
    (m..n).reduce(0) do |tot,_| 
    current = next_to_last + last 
    next_to_last = last 
    last = current 
    tot + current 
    end 
end 

def fib(m) 
    next_to_last, last = -1, 1 
    0.upto(m).each do |n| 
    current = next_to_last + last 
    next_to_last, last = last, current 
    end 
    [next_to_last, last] 
end 

Пример

m, n = 6, 12 
(n+1).times { |i| puts "#{i}: #{fib(i)}" } 
0: [0, 0] 
1: [0, 1] 
2: [1, 1] 
3: [1, 2] 
4: [2, 3] 
5: [3, 5] 
6: [5, 8] 
7: [8, 13] 
8: [13, 21] 
9: [21, 34] 
10: [34, 55] 
11: [55, 89] 
12: [89, 144] 

fib_last(6,12) #=> 4 (fib_sum(6,12) #=> 8 + 13 + 21 + 34 + 55 + 89 + 144 = 364) 
fib_last(1,2) #=> 2 (fib_sum(1,2) #=> 1 + 1 = 2) 
fib_last(1,3) #=> 4 (fib_sum(1,3) #=> 1 + 1 + 2 = 4) 
fib_last(1,4) #=> 7 (fib_sum(1,4) #=> 1 + 1 + 2 + 3 = 7) 
fib_last(2,3) #=> 3 (fib_sum(2,3) #=> 1 + 2 = 3) 

Answer 2

Вот хорошее решение для проблема, она передает все ограничения времени и памяти. Таким образом, вам никогда не придется вычислять фибро num больше, чем f (60). Он может эффективно обрабатывать очень большие входы.

def fib(n) 
    a, b = 0, 1 
    (n-1).times do 
     a, b = b, (a + b) % 10 
    end 
    b 
end 

def fib_partial_sum(m, n) 
    if n == m 
     fib(m % 60) 
    else 
     m = m % 60 
     n = n % 60 

     m = fib(m + 1) - 1 
     n = fib(n + 2) - 1 

     (n - m) % 10 
    end 
end 

if __FILE__ == $0 
    m, n = gets.split().map(&:to_i) 
    puts "#{fib_partial_sum(m, n)}" 
end 

(Максимальное время используется: 0,05/5,00, максимальная память используется:. 8699904/536870912)