Консультация № 176795
20.02.2010, 14:46
0.00 руб.
0 1 1
Вычислить число Фибоначчи Fi по запрошенному с клавиатуры целому неотрицательному индексу i. F0 = 0, F1 = 1, ..., Fi + 2 = Fi + Fi + 1. Определить границы i при условии использования в программе переменных типа integer.

Обсуждение

Неизвестный
20.02.2010, 15:42
общий
это ответ
Здравствуйте, nasya_koshenka.
Границу можно определить из условия Fn = round(fi^n/sqrt(5)), где round - функция округления до ближайщего целого, fi = 1.618... - золотое сечение.
Итоговое выражение: n <= floor[log((2^m - 1)*sqrt(5))/log(fi)], где m - разрядность типа целого числа. Обычно unsigned int имеет 32 разряда, для которых формула даёт максимальный индекс 47.
В программе расчёт этого значения обозначен комментариями, его можно заменить на константу.

Приложение:
#include <stdio.h>
#include <math.h>

int main()
{
unsigned int i;
unsigned int fn;
unsigned int a, b, k;

// extra math start
double m = 8.0*sizeof(fn);
double fi = 1.6180339887;
unsigned maxi = floor(log((pow(2.0, m) - 1)*sqrt(5.0))/log(fi));
// extra math finish

printf("Enter the index: ");
scanf("%u", &i);
if (i > maxi)
printf("\nSorry, too big index");
else
{
fn = 1;
a = 1;
b = 1;
for (k = 3; k <= i; ++k)
{
a = fn;
fn = b;
b = a;
fn = fn + a;
}
printf("fn = %u\n", fn);
}
return 0;
}
Форма ответа