[MahovIV]

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

Код:

#include <stdio.h>
#include <conio.h>

int main() {

	int T, N[40], i;
	  scanf("%d", &T);
	    while(T > 0) {
	   scanf("%d", &i);
	     for(i = 3; i <= 40; i++)
			 N[i - 2] = 0;
		 N[i - 1] = 1;
	       N[i] = N[i - 1] + N[i - 2];
	       printf("%d\n", N[i]);
	}
	getch();
	return 0;
}

Скажите, в чём ошибка?

[lmikle]

Сообщение от MahovIV

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

Код:

#include <stdio.h>
#include <conio.h>

int main() {

	int T, N[40], i;
	  scanf("%d", &T);
	    while(T > 0) {
	   scanf("%d", &i);
	     for(i = 3; i <= 40; i++)
			 N[i - 2] = 0;
		 N[i - 1] = 1;
	       N[i] = N[i - 1] + N[i - 2];
	       printf("%d\n", N[i]);
	}
	getch();
	return 0;
}

Скажите, в чём ошибка?

Классический алгоритм рассчета чисел фибоначи - рекурсивный.

Код:

int fib(int N)
{
  if (N <= 2) return 1
  else return fib(N-1) + fib(N-2);
}

Кажется так...

[Bargest]

И где хоть что-то, связанное с числами фибоначчи, и что хоть вводится?

Код:

a1 = 0;
a2 = 1;
for (int i = 0; i < needed; ++i)
{
   int t = a1 + a2;
   a1 = a2;
   a2 = t;
}

И в a2 будет число последовательности фибоначчи в позиции needed (нумерация с нуля), если не считать 0 числом последовательности.

[MahovIV]

Сообщение от lmikle

Классический алгоритм рассчета чисел фибоначи - рекурсивный.

Код:

int fib(int N)
{
  if (N <= 2) return 1
  else return fib(N-1) + fib(N-2);
}

Кажется так...

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

[Bargest]

И кстати для больших чисел будет удобнее так:

Код:

const int fi = 1,6180339887498948482045868343656

int f = (int)((pow(fi, n) - (pow(-fi, -n)))/(2*fi-1) + 0.5);

[MahovIV]

Я изменил программу вот так:

Код:

#include <stdio.h>
#include <conio.h>

int main() {

	int T, N[40], i;
	  scanf("%d", &T);
	    while(T > 0) {
	   scanf("%d", &i);
	     for(i = 1; i <= 40; i++)
                         {
			 N[0] = 0;
		 N[1] = 1;
	       N[i] = N[i - 1] + N[i - 2];
	       printf("%d\n", N[i]);
                        }
		   T--;
	}
	getch();
	return 0;
}

В результате отображается сначала значение -858993460, а потом все 40 первых значений последовательности Фибоначчи.

[angvelem]

А кто предварительно переменные инициализировать будет? Они локальные, а значит там "мусор".

[MahovIV]

Сообщение от angvelem

А кто предварительно переменные инициализировать будет? Они локальные, а значит там "мусор".

Я что-то не понял.

[angvelem]

В С вроде так:

Код:

  int T=0, N[40]=0, i; 

[Bargest]

#include <stdio.h>
#include <conio.h>

int main() {

int T, N[40], i;
scanf("%d", &T);
while(T > 0)
{
scanf("%d", &i);
for(i = 1; i <= 40; i++)
{
N[0] = 0;
N[1] = 1;
N[i] = N[i - 1] + N[i - 2];
printf("%d\n", N[i]);
}
T--;
}
getch();
return 0;
}

Не пойму смысла запихивать N[0] = 0 и N[1] = 1 внутрь цикла, а также при i = 1 будут использоваться элементы с индексами 0 и -1 (которого не существует).
А также не пойму смысла массива вообще, когда задача решается без него.

[MahovIV]

Сообщение от Bargest

Не пойму смысла запихивать N[0] = 0 и N[1] = 1 внутрь цикла, а также при i = 1 будут использоваться элементы с индексами 0 и -1 (которого не существует).
А также не пойму смысла массива вообще, когда задача решается без него.

Задача без массива решается, но очень медленно.

[Bargest]

Без массива она решается быстрее. Гораздо. Как я показывал. И без рекурсии. И экономнее в памяти.

[MahovIV]

Сообщение от Bargest

Без массива она решается быстрее. Гораздо. Как я показывал. И без рекурсии. И экономнее в памяти.

Вы можете подсказать, как это сделать при помощи массивов? Мне нужно отображение не всего массива, а отдельного элемента массива.