Компьютеры
и программирование

Ряд чисел Фибоначчи: такие разные решения

Предыстория задач Фибоначчи

Леонардо Фибоначчи (1170-1250) - итальянский математик, положивший начало введения в Европе арабской системы чисел. В 1202 году он опубликовал следующую задачу: "Пара кроликов находится в загороженном месте. Сколько их потомков появится в течении года? Каждая пара кроликов каждый месяц производит новую пару, которая во втором месяце становится продуктивной".

Число кроликов в каждом месяце соответствует числам Фибоначчи, каждое из которых получается как сумма двух предыдущих чисел. Числа Фибоначчи для бесконечной последовательности можно вычислить по формуле:

, если .

Кроме того, определяется, что f(1)=1 (соответствует новой паре кроликов к), f(2)=1 (соответствует взрослой паре кроликов К).

Сколько пар кроликов в течении года появится в питомнике? Для решения этой задачи вычисляют первые 13 чисел Фибоначчи. Результат отражает ситуацию в начале следующего года.

1к1
2К1
3Кк2
4КкК3
5КкККк5
6КкККкКкК8
7итд.13
821
934
1055
1189
12144
13233

Видим, что в начале следующего года кроликов должно быть 233 пары. На этом данная задача исчерпывается. Но ряды чисел Фибоначчи продолжают изучаться применительно к различным задачам.

Программные реализации

Программные реализации рядов чисел Фибоначчи различаются в зависимости от того, сколько членов последовательности нужно вычислить и вывести в программе, выводятся ли все числа или только одно с каким-либо номером, нужно ли предусмотреть возможность пользователя определить количество членов последовательности.

Если в программе определено, что все числовые значения относятся к целому типу (int), то следует считаться с тем, что максимальное значение для целочисленного типа составляет 32 767. Но программа в этом случае выводит корректно весь ряд чисел Фибоначчи до 46 члена включительно. Дело в том, что происходит преобразование типа данных от int к long int. Только времени такое вычисление и вывод чисел занимает больше, чем в случае, если определить для чисел Фибоначчи тип данных long int.

Если же определён тип данных long int, все члены последовательности Фибоначчи начиная с 47-го будут вычислены некорректно, поскольку максимальное значение для этого типа составляет 2 147 483 647. В случае типа double корректно выводятся числа Фибоначчи от 0 до 300 включительно.

Наиболее простая реализация для рядов чисел Фибоначчи с целочисленным типом данных выглядит так:

Код C++

#include <iostream>

using namespace std;

int Fib(int i)

{

int value = 0;

if(i < 1) return 0;

if(i == 1) return 1;

return Fib(i-1) + Fib(i - 2);

}

int main()

{

int i = 0;

while(i < 47)

{

cout << Fib(i) << endl;

i++;

}

return 0;

}

Как уже отмечалось, есть разница, используется ли тип данных int или long int: в первом случае для того, чтобы вычислить и вывести на экран весь ряд чисел Фибоначчи до 46-го включительно, требуется около 40 минут, а во втором - примерно на треть меньше.

Код C++

#include <iostream>

using namespace std;

long int Fib(int i)

{

int value = 0;

if(i < 1) return 0;

if(i == 1) return 1;

return Fib(i-1) + Fib(i - 2);

}

long int main()

{

int i = 0;

while(i < 47)

{

cout << Fib(i) << endl;

i++;

}

return 0;

}

Можно добиться и большего максимального значения, если определить тип данных как unsigned (без знака). Если максимальное значение для signed long int (то есть со знаком, используется по умолчанию) составляет 2 147 483 647, то для unsigned long int оно составляет 4 294 967 295. Ниже приведён код такой реализации для ряда чисел Фибоначчи.

Код C++

int Fib(int Place)

{

unsigned long OldValue = 0;

unsigned long Value = 1;

unsigned long Hold;

if(i < 1){return(0);}

for(int n = 1; n < Place;n++)

{

Hold = Value;

Value+=OldValue;

OldValue = Hold;

}

return(Value);

}

Функция для рядов чисел Фибоначчи с условием значения double для членов последовательности выглядит так:

Код C++

double fib(int place)

{

static double* lookup = NULL;

if(lookup == NULL)

{

lookup = new double[300];

lookup[0] = 0;

lookup[1] = 1;

for(int i = 2; i < 300; ++i)

{

lookup[i] = lookup[i - 1] + lookup[i - 2];

}

}

if(place < 300)

{

return lookup[place];

}

return fib(place - 1) + fib(place - 2);

}

Далее - способ отойти от компактности программы в пользу функциональности (пользователь имеет возможность определять, сколько членов последовательности Фибоначчи нужно вычислить и вывести, но максимальное значение определено типом int, так что возможны модификации с другими типами данных):

Код C++

#include <iostream>

using namespace std;

int Fib(int i)

{

int f1 = 0;

int f2 = 1;

int fn;

if (i < 1) { return 0; }

if (i == 1){ cout << "0 1\n"; }

if (i > 1)

{

cout << "0 1 ";

for (int j = 1; j < i;j++)

{

fn = f1 + f2;

cout << fn << " ";

f1 = f2;

f2 = fn;

}

}

cout << "\n\n";

return 0;

};

int main()

{

char choice;

int input;

cout << "Enter how long you wish the Fibanacci series to display: ";

cin >> input;

Fib(input);

cout << "Again? Y/N: ";

cin >> choice;

while (choice == 'y' || choice == 'Y')

{

cout << "\nEnter how long you wish the Fibanacci series to display: ";

cin >> input;

Fib(input);

cout << "Again? Y/N: ";

cin >> choice;

}

system("Pause");

return 0;

}

Поделиться с друзьями