Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.05.2013, 18:41   #1
gani_ali
Новичок
Джуниор
 
Регистрация: 20.05.2013
Сообщений: 3
По умолчанию Фиббоначи

Значит сижу я, думаю, не написать ли мне программу, находящую числа Фиббоначи. Сделал рекурсивно, использовал unsigned long. Ищу я свой 60-й член прогрессии. Ищу. Ищу. Сижу, думаю, то ли не вмещается, то ли компьютер думает, то ли прога слишком громоздкая - долго выполняется. Вопрос 1 - нельзя ли не через рекурсию сделать?
Вопрос 2 - Так что мне, ждать, или не дождусь?)
gani_ali вне форума Ответить с цитированием
Старый 20.05.2013, 18:45   #2
gani_ali
Новичок
Джуниор
 
Регистрация: 20.05.2013
Сообщений: 3
По умолчанию

Покопался, открыл для себя новый тип - long long)) но вопрос на счет того, можно ли без рекурсии написать, открыт)
gani_ali вне форума Ответить с цитированием
Старый 20.05.2013, 19:14   #3
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
Покопался, открыл для себя новый тип - long long)) но вопрос на счет того, можно ли без рекурсии написать, открыт)
Мало того, что можно, так ещё и нужно. Рекурсивное вычисление чисел Фибоначчи (и любых других линейных рекурсивных последовательностей) хорошо только одним: в его реализации сложно ошибиться. Но расходы времени кошмарны.
Рекурсивный код:
Код:
int fibonacci_rec(int n){
  if(n==1 || n==2) return 1;
  return fibonacci_rec(n-1) + fibonacci_rec(n-2);
}
Теперь вместо этого будем вычислять элементы от первого до требуемого:
Код:
int fibonacci_linear(int n){
  int a=1, b=1;
  int temp;
  for(int i=2; i<n; ++i){
    a = a+b;
    { //Обмен местами
      temp = a;
      a = b;
      b = temp;
    }
  }
  return b;
}
Как нетрудно видеть, цикл прокрутится n раз.
И ещё быстрее (подумайте на досуге, почему это работает):
Код:
int fibonacci_log(int n){  
      int a = 1, ta, 
      b = 1, tb,
      c = 1, rc = 0,  tc,
      d = 0, rd = 1; 
 
  while (n) { 
    if (n&1) {
      tc = rc;
      rc = rc*a + rd*c;
      rd = tc*b + rd*d;
    } 
    ta = a; tb = b; tc = c;
    a = a*a  + b*c;
    b = ta*b + b*d;
    c = c*ta + d*c;     
    d = tc*tb+ d*d;
 
    n >>= 1;  
  }  
  return rc;
}
Abstraction вне форума Ответить с цитированием
Старый 20.05.2013, 19:27   #4
gani_ali
Новичок
Джуниор
 
Регистрация: 20.05.2013
Сообщений: 3
По умолчанию

Спасибо большое, да, так лучше)
gani_ali вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Ассемблер. Вывести на экран первые N чисел последовательности Фиббоначи nekromant7 Помощь студентам 0 29.03.2012 11:43
Ряд Фиббоначи С++ tracer Помощь студентам 3 17.05.2011 20:55
найти н-ую пцифру в последовательности фиббоначи в паскале halk Помощь студентам 29 10.10.2009 21:44