что является лучшим подходом для генерации рядов Фибоначчи

Question

Два общих подхода для генерации рядов Фибоначчи:

1. Традиционный подход *1004*, то есть выполнение цикла for внутри функции.
2. Рекурсия

Я наткнулся на другое решение

#include <iostream>

using namespace std;

void fibo() {
 static int y = 0;
 static int x = 1;
 cout << y << endl;
 y = x + y;
 x = y - x;
}

int main() {
 for (int i = 1; i <= 1; i++) {
  fibo();
 }
 return 0;
}

Похоже, что это решение отлично работает на начальных этапах, но по сравнению с традиционным и рекурсивным подходом оно имеет какие-либо существенные недостатки?

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

Answer 1

Недостатки, которые я сразу вижу:

• По сути, делая состояние глобальным, оно не поточно-ориентированное
• Вы можете проходить последовательность только один раз, поскольку нет способа сбросить

Я бы предпочел подход, который сохраняет состояние внутри объекта, который вы можете запросить для следующего значения - итератор, в основном. (Я никогда не был уверен, насколько легко последовательность Фибоначчи отображается на итераторы C ++; хотя она прекрасно работает с C # и Java IEnumerable<T> и Iterable<T>.)

Answer 2

Решение, которое вы нашли, подходит для случаев, когда вам нужно сохранить состояние (например, когда вы вычисляете число Фибоначчи, делаете что-то на его основе, а затем вычисляете другое), но использование этого из двух мест в вашем коде скорее всего даст смешные результаты. Это потому, что статические переменные всегда будут одинаковыми, независимо от того, откуда вы их вызываете. Я бы вместо этого предложил:

class FiboNumbers {
  public:
    FiboNumbers() :
        x_(1), y_() {}

    int getNext() {
        x_ += y_;
        y_ = x_ - y_;
        return x_;
    }

  private:
    int x_, y_;
};

Это обеспечивает такое же сохранение состояния, но позволяет создавать несколько экземпляров класса, что позволяет вам иметь разные части кода, которые вычисляют их собственные ряды Фибоначчи.

Незначительное примечание: код, который я разместил, будет производить ту же серию, что и пример, который вы опубликовали, но он создаст реальную последовательность Фибоначчи, которая начинается с 0 1 1 2 ...

Answer 3

Я студент C ++ (через 1,5 месяца).

Оставьте отзыв об этом другом способе, о котором я думал в серии Фибоначчи.

#include<iostream>

using namespace std;

void fibseries(long int n)
{
    double x=0;double y=1;
    for (long int i=1;i<=n;i++)
     {
        if(i%2==1)
         {
            cout<<x<<" ";
            x=x+y;
         } 
        else 
         {
            cout<<y<<" ";
            y=x+y;
         }
     }
}

main()
{
    long int n=0;
    cout<<"The number of terms ";
    cin>>n;
    fibseries(n);
    return 0;
}

Answer 4

Как было сказано ранее, преимущество статических переменных в принципе состоит в том, что дешевле вычислять n -й элемент последовательности, где n - 1 - это уже было оценено.

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

Использование class, как рекомендует Sevis, безусловно, является лучшим способом реализации такого статического подхода: это делает все более безопасным, дает вам простой способ вернуться к началу последовательности (просто путем повторной инициализации объекта), а также позволяет реализовать дополнительные функции, такие как возврат k шагов, поиск текущей позиции и т. д.

Answer 5

Я не уверен, что эта функция действительно должна делать.Он работает только в том цикле, который вы представляете, и, как уже отмечали другие, он работает только один раз.(И, возможно, в вашем цикле есть опечатка, так как ваша полная программа выводит "0", и ничего больше.) Какое преимущество она предлагает по сравнению с:

int y = 0;
int x = 1;
for ( int i = 0; i < count; ++ i ) {
    std::cout << y <<std::endl;
    y = x + y;
    x = y - x;
}

?Он более сложный, гораздо менее надежный и гораздо менее полезный.

Answer 6

Я думаю, что этот подход с указателем был бы более полезным для вас.

void main()
{
    int i,p, *no,factorial,summ;

    int fib(int p);

    clrscr();

    printf("\n Enter The Number:");
    scanf("%d", no);
    printf("\n The Fibonnacci series: \n");

    for(i=0; i < *no; i++)
        printf("%d\n", fib(i));

    getch();
}

int fib(int p)
{
    if(p == 0)
        return(0);
    if(p >= 1 && p <= 2)
        return(1);
    else
        return(fib(p - 1) + fib(p - 2));
}