CODEWITHSUNDEEP
c++arraysfibonacci
user3684741
user3684741

Reputation: 13

How can I create an array with Fibonacci numbers up to a certain integer n?

So for an assignment I've been asked to create a function that will generate an array of fibonacci numbers and the user will then provide an array of random numbers. My function must then check if the array the user has entered contains any fibonacci numbers then the function will output true, otherwise it will output false. I have already been able to create the array of Fib numbers and check it against the array that the user enters however it is limited since my Fib array has a max size of 100.

bool hasFibNum (int arr[], int size){

int fibarray[100];
fibarray[0] = 0;
fibarray[1] = 1;
bool result = false;
for (int i = 2; i < 100; i++)
{
    fibarray[i] = fibarray[i-1] + fibarray[i-2];

}

for (int i = 0; i < size; i++)
{
    for(int j = 0; j < 100; j++){
        if (fibarray[j] == arr[i])
            result = true;
    }
}

return result;
}

So basically how can I make it so that I don't have to use int fibarray[100] and can instead generate fib numbers up to a certain point. That point being the maximum number in the user's array.

So for example if the user enters the array {4,2,1,8,21}, I need to generate a fibarray up to the number 21 {1,1,2,3,5,8,13,21}. If the user enters the array {1,4,10} I would need to generate a fibarray with {1,1,2,3,5,8,13}

Quite new to programming so any help would be appreciated! Sorry if my code is terrible.

Upvotes: 1

Views: 4585

Answers (2)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275270

Here is a function that returns a dynamic array with all of the Fibonacci numbers up to and including max (assuming max > 0)

std::vector<size_t> make_fibs( size_t max ) {
  std::vector<size_t> retval = {1,1};
  while( retval.back() < max ) {
    retval.push_back( retval.back()+*(retval.end()-2) );
  }
  return retval;
}

I prepopulate it with 2 elements rather than keeping track of the last 2 separately.

Note that under some definitions, 0 and -1 are Fibonacci numbers. If you are using that, start the array off with {-1, 0, 1} (which isn't their order, it is actually -1, 1, 0, 1, but by keeping them in ascending order we can binary_search below). If you do so, change the type to an int not a size_t.

Next, a sketch of an implementation for has_fibs:

template<class T, size_t N>
bool has_fibs( T(&array)[N] ) {
  // bring `begin` and `end` into view, one of the good uses of `using`:
  using std::begin; using std::end;
  // guaranteed array is nonempty, so 
  T m = *std::max_element( begin(array), end(array) ); will have a max, so * is safe.
  if (m < 0) m = 0; // deal with the possibility the `array` is all negative

  // use `auto` to not repeat a type, and `const` because we aren't going to alter it:
  const auto fibs = make_fibs(m);

  // d-d-d-ouble `std` algorithm:
  return std::find_if( begin(array), end(array), [&fibs]( T v )->bool {
    return std::binary_search( begin(fibs), end(fibs), v );
  }) != end(array);
}

here I create a template function that takes your (fixed sized) array as a reference. This has the advantage that ranged-based loops will work on it.

Next, I use a std algorithm max_element to find the max element.

Finally, I use two std algorithms, find_if and binary_search, plus a lambda to glue them together, to find any intersections between the two containers.

I'm liberally using C++11 features and lots of abstraction here. If you don't understand a function, I encourage you to rewrite the parts you don't understand rather than copying blindly.

This code has runtime O(n lg lg n) which is probably overkill. (fibs grow exponentially. Building them takes lg n time, searching them takes lg lg n time, and we search then n times).

Upvotes: 1

Michal Hosala
Michal Hosala

Reputation: 5697

It is possible that I still don't understand your question, but if I do, then I would achieve what you want like this:

bool hasFibNum (int arr[], int size){
    if (size == 0) return false;
    int maxValue = arr[0];
    for (int i = 1; i < size; i++)
    {
        if (arr[i] > maxValue) maxValue = arr[i];
    }
    int first = 0;
    int second = 1;
    while (second < maxValue)
    {
        for (int i = 0; i < size; i++)
        {
            if (arr[i] == first) return true;
            if (arr[i] == second) return true;
        }
        first = first + second;
        second = second + first;
    }

    return false;
}

Upvotes: 1

Related Questions