Форум по программированию Delphi Sources

 



Вернуться   Форум по программированию Delphi Sources > C/C++ > C/C++
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Результаты опроса: Актуальна ли эта тема?
Да 2 66.67%
Нет 1 33.33%
Голосовавшие: 3. Вы еще не голосовали в этом опросе

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.01.2013, 21:18
MahovIV MahovIV вне форума
Новичок
 
Регистрация: 30.12.2012
Сообщения: 77
Репутация: 10
По умолчанию Числа Фибоначчи

Мне необходимо написать программу, которая вычисляет элемент последовательности Фибоначчи. Я думал сделать программу вот так:
Код:
#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;
}
Скажите, в чём ошибка?
Ответить с цитированием
  #2  
Старый 11.01.2013, 21:24
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 7,375
Версия Delphi: 7, XE3, 10.2
Репутация: 49088
По умолчанию

Цитата:
Сообщение от 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);
}

Кажется так...
Ответить с цитированием
  #3  
Старый 11.01.2013, 21:26
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

И где хоть что-то, связанное с числами фибоначчи, и что хоть вводится?
Код:
a1 = 0;
a2 = 1;
for (int i = 0; i < needed; ++i)
{
   int t = a1 + a2;
   a1 = a2;
   a2 = t;
}
И в a2 будет число последовательности фибоначчи в позиции needed (нумерация с нуля), если не считать 0 числом последовательности.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.

Последний раз редактировалось Bargest, 11.01.2013 в 21:36.
Ответить с цитированием
  #4  
Старый 11.01.2013, 21:27
MahovIV MahovIV вне форума
Новичок
 
Регистрация: 30.12.2012
Сообщения: 77
Репутация: 10
По умолчанию

Цитата:
Сообщение от lmikle
Классический алгоритм рассчета чисел фибоначи - рекурсивный.
Код:
int fib(int N)
{
  if (N <= 2) return 1
  else return fib(N-1) + fib(N-2);
}

Кажется так...
Я учусь в университете. Там необходимо загружать задачи по программированию на серверь, где проверяется моё решение. Рекурсивный алгоритм мне не подходит. Программа слишком медленно запускается. Бестрее будет при помощи массива.
Ответить с цитированием
  #5  
Старый 11.01.2013, 21:46
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

И кстати для больших чисел будет удобнее так:
Код:
const int fi = 1,6180339887498948482045868343656

int f = (int)((pow(fi, n) - (pow(-fi, -n)))/(2*fi-1) + 0.5);
__________________
jmp $ ; Happy End!
The Cake Is A Lie.

Последний раз редактировалось Bargest, 11.01.2013 в 21:50.
Ответить с цитированием
  #6  
Старый 11.01.2013, 23:48
MahovIV MahovIV вне форума
Новичок
 
Регистрация: 30.12.2012
Сообщения: 77
Репутация: 10
По умолчанию

Я изменил программу вот так:
Код:
#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 первых значений последовательности Фибоначчи.
Ответить с цитированием
  #7  
Старый 12.01.2013, 00:06
Аватар для angvelem
angvelem angvelem вне форума
.
 
Регистрация: 18.05.2011
Адрес: Омск
Сообщения: 3,970
Версия Delphi: 3,5,7,10,12,XE2
Репутация: выкл
По умолчанию

А кто предварительно переменные инициализировать будет? Они локальные, а значит там "мусор".
__________________
Je venus de nulle part
55.026263 с.ш., 73.397636 в.д.
Ответить с цитированием
  #8  
Старый 12.01.2013, 00:15
MahovIV MahovIV вне форума
Новичок
 
Регистрация: 30.12.2012
Сообщения: 77
Репутация: 10
По умолчанию

Цитата:
Сообщение от angvelem
А кто предварительно переменные инициализировать будет? Они локальные, а значит там "мусор".
Я что-то не понял.
Ответить с цитированием
  #9  
Старый 12.01.2013, 00:20
Аватар для angvelem
angvelem angvelem вне форума
.
 
Регистрация: 18.05.2011
Адрес: Омск
Сообщения: 3,970
Версия Delphi: 3,5,7,10,12,XE2
Репутация: выкл
По умолчанию

В С вроде так:
Код:
  int T=0, N[40]=0, i; 
__________________
Je venus de nulle part
55.026263 с.ш., 73.397636 в.д.
Ответить с цитированием
  #10  
Старый 12.01.2013, 12:30
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

Цитата:
#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 (которого не существует).
А также не пойму смысла массива вообще, когда задача решается без него.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.

Последний раз редактировалось Bargest, 12.01.2013 в 12:33.
Ответить с цитированием
Этот пользователь сказал Спасибо Bargest за это полезное сообщение:
MahovIV (15.01.2013)
  #11  
Старый 12.01.2013, 19:11
MahovIV MahovIV вне форума
Новичок
 
Регистрация: 30.12.2012
Сообщения: 77
Репутация: 10
По умолчанию

Цитата:
Сообщение от Bargest
Не пойму смысла запихивать N[0] = 0 и N[1] = 1 внутрь цикла, а также при i = 1 будут использоваться элементы с индексами 0 и -1 (которого не существует).
А также не пойму смысла массива вообще, когда задача решается без него.
Задача без массива решается, но очень медленно.
Ответить с цитированием
  #12  
Старый 12.01.2013, 21:36
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

Без массива она решается быстрее. Гораздо. Как я показывал. И без рекурсии. И экономнее в памяти.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.
Ответить с цитированием
  #13  
Старый 13.01.2013, 19:26
MahovIV MahovIV вне форума
Новичок
 
Регистрация: 30.12.2012
Сообщения: 77
Репутация: 10
По умолчанию

Цитата:
Сообщение от Bargest
Без массива она решается быстрее. Гораздо. Как я показывал. И без рекурсии. И экономнее в памяти.
Вы можете подсказать, как это сделать при помощи массивов? Мне нужно отображение не всего массива, а отдельного элемента массива.
Ответить с цитированием
Ответ



Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 11:15.


 

Сайт

Форум

FAQ

RSS лента

Прочее

 

Copyright © Форум "Delphi Sources", 2004-2019

ВКонтакте   Facebook   Twitter