что делает int numbers [n + 2]; заявление делать? - PullRequest
Новая
       106

что делает int numbers [n + 2]; заявление делать?

0 голосов
/ 08 мая 2020 
  #include<iostream>

    int fastFibonacci(int n) 
    {
      int numbers[n+2]; // int numbers[n].
      numbers[0] = 0;
      numbers[1] = 1;
      for (int i = 2; i <= n; i++)
      {
          numbers[i] = numbers[i - 1] + numbers[i - 2];
      }
      return numbers[n];
    }

    int main() {
      int n;
      std::cout << "Enter a Number";
      std::cin >> n;
      int result = fastFibonacci(n);
      std::cout << result << "\n";
      return 0;
    }

в этом коде при вводе 0 или 1 получаю правильный ответ. Но проблема в том, что когда я заменяю int numbers [n + 2]; на закомментированную часть, он начинает давать мне неправильный ответ, когда ввод 0 или 1. Почему? кто-нибудь, пожалуйста, объясните мне.

Ответы [ 2 ]

2 голосов
/ 08 мая 2020

В этой функции 

int fastFibonacci(int n) 
{
  int numbers[n+2]; // int numbers[n].
  numbers[0] = 0;
  numbers[1] = 1;
  for (int i = 2; i <= n; i++)
  {
      numbers[i] = numbers[i - 1] + numbers[i - 2];
  }
  return numbers[n];
}

используется массив переменной длины с n + 2 элементами, объявленными в этой строке 

  int numbers[n+2]; // int numbers[n].

Массивы переменной длины не являются стандартной функцией C ++. Его можно реализовать как расширение собственного языка компилятора C ++.

Использование массива переменной длины делает функцию очень небезопасной, поскольку может произойти переполнение стека.

Как и в самой функции, явно используются два элемента массива 

  numbers[0] = 0;
  numbers[1] = 1;

, тогда в массиве должно быть не менее двух элементов, даже если параметр имеет значение меньше 2.

Для вычисления n-го числа Фибоначчи там объявлять массив такого размера не нужно.

Кроме этого, аргумент функции должен иметь беззнаковый целочисленный тип. В противном случае функция может вызвать неопределенное поведение, если пользователь передает отрицательное число.

Также для больших значений n может быть целочисленное переполнение для типа int.

Функция может быть реализована разными способами.

Вот одна из возможных его реализаций. 

#include <iostream>
#include <functional>

unsigned long long fibonacci( unsigned int n )
{
    unsigned long long a[] = { 0, 1 };

    while ( n-- )
    {
        a[1] += std::exchange( a[0], a[1] );
    }

    return a[0];
}

int main() 
{
    const unsigned int N = 10;

    for ( unsigned int i = 0; i < N; i++ )
    {
        std::cout << i << ": " << fibonacci( i ) << '\n'; 
    }

    return 0;
}

Вывод программы: 

0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
1 голос
/ 08 мая 2020

int numbers[n+2]; - это объявление массива int s с пробелом для n + 2 int s, это массив переменной длины и не является частью стандарта C ++ , хотя некоторые компиляторы допускают это, вы не должны использовать это значение.

Если вам нужен массив переменной длины, используйте std::vector.

С int numbers[n+2]; if n равно 0, у вас все еще есть место для 2 int s, если у вас есть int numbers[n];, в массиве будет место для 0 int s, поэтому код не удастся, потому что вы пытаетесь получить доступ к памяти, которая не существует с numbers[0] и numbers[1].

Есть несколько хороших способов реализовать последовательность Фибоначчи, на сайте вы можете найти много вопросов по этому поводу на нескольких языках программирования, вот один из них Фибоначчи серия в C ++

Edit

Итак, я видел ваши комментарии об использовании вектора, для создания последовательности вам не понадобится вектор только два переменные для хранения двух суммируемых чисел, чтобы сохранить последовательность е в vactor, вы можете сделать это, например: 

#include <iostream>
#include <vector>
#include <iomanip>

//passing the vector by reference
void fastFibonacci(unsigned long long n, std::vector<unsigned long long>& sequence) {

   unsigned long long first = 0;
   unsigned long long second = 1;
   sequence.push_back(first); //add first values to the vector
   sequence.push_back(second); //add first values to the vector
   for (unsigned long long i = 0, value = 0; i < n && value <= LLONG_MAX ; ++i) {
      value = first + second;
      first = second;
      second = value;
      sequence.push_back(value); //adding values to the vector
   }  
}

int main() {  
   unsigned long long limit; //number of values in the sequence
   int num = 1;
   std::vector<unsigned long long> sequence; //container for the sequence

   std::cout << "Enter upper limit: ";
   std::cin >> limit;
   fastFibonacci(limit, sequence);

   //print the sequence in a range based loop formatted with <iomanip> library
   for(auto& i : sequence){
      std::cout << std::setw(4) << std::left << num++ << " " << i << std::endl; 
   }
   return 0;
}

Если вы хотите вывести только одно из чисел в последовательности, просто используйте, например: 

std::cout << sequence[10];

Вместо всего вектора.

Код, который вы публикуете в комментарии к другому ответу, не будет работать, потому что доступ к вектору находится за пределами в numbers[i] = numbers[i - 1] + numbers[i - 2];, если, например, i = 5, ваш вектор имеет только 2 узла, но вы обращаетесь к 6-му узлу numbers[5].

...