Make an array to store the calculated numbers in m

问题:

Im trying to make an array to store calculated numbers from formula and put them into memory. So that later when the number is called up again, it doesn't have to be re-calculated. Cause its in memory already.

The formula is

fib(n-1) + fib(n-2);

The rest of my code is this

#include <iostream>
using namespace std;

// Returns the nth number in the fibonacci sequence
int fib(int n);

int main()
{
    cout << fib(46) << endl;

    system("pause");
    return 0;
}

int fib(int n)
{
    // Base cases
    if (n == 1 || n == 2) return 1;

    // Recursive cases
    return fib(n-1) + fib(n-2);
}

Thanks Guys

回答1:

Your definition of Fibonacci numbers doesn't take F₀=0 into account.

Here's a modification of your code, to allow for an incremental extension of the sequence. It only calculates the numbers it needs, and postpones higher numbers for later. Note that you won't be able to request a number higher than F₄₆ without switching datatypes (long long will help you somewhat).

#include <iostream>
#include <vector>
using namespace std;

static vector<int> fib_seq;

// Returns the nth number in the fibonacci sequence                             
int fib(int n);

int main()
{
  cout << fib(46) << endl;

  system("pause");
  return 0;
}

int fib(int n)
{
  // Make sure that there are at least two entries                              
  if(fib_seq.size() < 2) {
    fib_seq.resize(2);
    fib_seq[0] = 0;
    fib_seq[1] = 1;
  }
  // Fill the sequence with more numbers if needed                              
  for(int i = (int)fib_seq.size(); i <= n; ++i)
    fib_seq.push_back(fib_seq[i-2] + fib_seq[i-1]);
  // Return the requested number                                                
  return fib_seq[n];
}

回答2:

If you are asking how to modify the given code so that it can save the values instead of just printing them to the console, then here is a way:

// Stores the numbers of the fibonacci sequence up to n inside buff
void fib(int n,int* buff);

int main()
{
    //the array to store the fibonacci series
    int buff[47];
    unsigned int i;

    //call the recursive fibonacci which will populate the array
    fib(46,buff);

    //let's also print it
    for(i = 0; i < 47; i ++)
    {
        printf("%d\n",buff[i]);
    }

    return 0;
}

// Stores the numbers of the fibonacci sequence up to n inside buff
void fib(int n,int* buff)
{

    // Base cases
    if (n == 1)
    {
         buff[n-1] = 0;
         buff[n] = 1;
         return ;
    }

    //place the recursive call after the base cases
    fib(n-1,buff);

    //and here stores the result in the buffer
    buff[n] = buff[n-1] + buff[n-2];
    return;
}