Ряд чисел Фибоначчи: такие разные решения
Предыстория задач Фибоначчи
Леонардо Фибоначчи (1170-1250) - итальянский математик, положивший начало введения в Европе арабской системы чисел. В 1202 году он опубликовал следующую задачу: "Пара кроликов находится в загороженном месте. Сколько их потомков появится в течении года? Каждая пара кроликов каждый месяц производит новую пару, которая во втором месяце становится продуктивной".
Число кроликов в каждом месяце соответствует числам Фибоначчи, каждое из которых получается как сумма двух предыдущих чисел. Числа Фибоначчи для бесконечной последовательности можно вычислить по формуле:
, если 
.
Кроме того, определяется, что f(1)=1 (соответствует новой паре кроликов к), f(2)=1 (соответствует взрослой паре кроликов К).
Сколько пар кроликов в течении года появится в питомнике? Для решения этой задачи вычисляют первые 13 чисел Фибоначчи. Результат отражает ситуацию в начале следующего года.
| 1к | 1 |
| 2К | 1 |
| 3Кк | 2 |
| 4КкК | 3 |
| 5КкККк | 5 |
| 6КкККкКкК | 8 |
| 7итд. | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
| 11 | 89 |
| 12 | 144 |
| 13 | 233 |
Видим, что в начале следующего года кроликов должно быть 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;
}
Поделиться с друзьями
