ошибка C2106: '=': левый операнд должен быть l-значением в последовательности Фибоначчи путем динамического программирования в C++

Question

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

#include<iostream> 
#include<ctime> 

int fib(int index) 
{ 
    int memo[] = {0}; 
    memo[0] = 0; 
    memo[1] = 1; 
    for(int i = 2; i <= index; i++) 
    { 
     fib(index) = fib(index - 1) + fib(index - 2); //error comes here 
    } 
    return fib(index); 
} 
int main() 
{ 
    time_t start, end, diff; 
    int index; 
    std::cout << "Please, enter the index of fibonacci sequence" << std::endl; 
    std::cin >> index; 
    start = time(NULL); 
    std::cout << "calculating...." << std::endl << fib(index) <<std::endl; 
    end = time(NULL); 
    diff = (time_t)difftime(end, start); 
    std::cout << "Time elapsed: " << diff << std::endl; 
    return 0; 
} 

Но, в fib(index) = fib(index - 1) + fib(index - 2); получаю ошибку Iam линии, как

error C2106: '=' : left operand must be l-value 

Так скажите, пожалуйста, что не так я сделал в этой строке. Заранее спасибо.

Answer 1

Вы назначаете l-значение (это то, что возвращает int fib(int)). Так же, как и сообщение об ошибке.

Также обратите внимание, что int memo[] = {0}; создает массив размером 1, поэтому запись вне индекса 0 недействительна.

Answer 2

Вы не можете назначить fib(index), как уже указывали другие. Существует обходное решение, возвращая ссылку или указатель.

Но сама программа неправа, поскольку она переходит в бесконечный цикл. Линия

fib(index) = fib(index - 1) + fib(index - 2); 

продолжает запуск выдумка (индекс), если индекс> 1. Правильный путь решения Фибоначчи с использованием DP является

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

Answer 3

Вы должны ввести временную переменную так:

int result = 0; 
for(int i = 2; i <= index; i++) 
{ 
    result = fib(index - 1) + fib(index - 2); //error comes here 
} 
return result; 

Но это только техническое решение. Как отметил Бала, ваш алгоритм как таковой не работает.

Это может быть решением, если вы ищете рекурсивный:

int fib(int index) 
{ 
    switch(index) { 
    case 0: 
     return 0; 
    case 1: 
     return 1; 
    default: 
     return fib(index - 1) + fib(index -1); 
    } 
} 

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

int fib(int index) 
{ 
    // Stores fib for given index 
    static std::map<int, int> memo; 

    if (index == 0) return 0; 
    else if (index == 1) return 1; 
    else { 
     auto it = memo.find(index); 
     if (it == memo.end()) { 
      int r = fib(index - 1) + fib(index -2); 
      memo[index] = r; 
     } else return *it; 
    } 
}