Форум программистов, компьютерный форум CyberForum.ru

Рекурсивная процедура вычисления n-го числа Фибоначчи - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 44, средняя оценка - 4.80
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 01:25     Рекурсивная процедура вычисления n-го числа Фибоначчи #1
Добрый день. Подскажите, пожалуйста, алгоритм рекурсивной процедуры вычисления n-го числа Фибоначчи.

Только начал изучать процедуры и рекурсии, поэтому задача вызвала затруднения.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alexey31415
 Аватар для alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 01:39     Рекурсивная процедура вычисления n-го числа Фибоначчи #2
у тебя должна происходить проверка на базовый случай - это когда аргумет функции твоей равен 1 или 0,в этих случаях функция возвращает 1 и 0 соответсвенно,если другой аргумент,происходит вызов функции с меньшим на единицу аргументом
или тебе надо попроще и с куском кода?
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 02:14  [ТС]     Рекурсивная процедура вычисления n-го числа Фибоначчи #3
alexey31415,
Проверку на базовый случай реализовал:

void F ( int n, int &fib )
{
if ( n == 0 ) fib = 0;
if ( n == 1 ) fib = 1;


}
А далее не знаю алгоритм.

Вызов функции с меньшим на 1 элементов.
Число фибоначи-это сумма двух предыдущих. Не знаю, как реализовать сложение процедур от n-1 и n-2 , чтобы получить n
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
05.04.2012, 02:17     Рекурсивная процедура вычисления n-го числа Фибоначчи #4
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Not_Rekurs(int N_Pos)
{
    if (N_Pos==1 || N_Pos==2) 
     {
        return 1;                                  //первые две единицы, если с нуля, то это условие надо переписать
     }
    else return Rekurs (N_Pos, 2, 1, 1);   //опять же, если с нуля, то вызывать с аргументами (N_Pos, 2, 0, 1)
}
 
int Rekurs(int N_Pos, int N_tek, int Pred, int Tek)  //номер позиции(по которой надо найти), текущий номер позиции, предыдущий элемент, текущий элемент
{
   if (N_tek+1==N_Pos) return (Pred+Tek);  //дошли ли мы до нужного нам номера?  да- выход из рекурсии и возврат значения
     else return Rekurs(N_Pos, N_tek+1, Tek, Pred+Tek);  //если нет, продолжаем рекурсию, но меняем значения, увеличиваем номер текущего элемента, предыдущий элемент заменяем текущим, а текущий- следующим (их суммой)
}
если ряд фибонначи начинается с 1, то код вроде такой
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
05.04.2012, 02:19     Рекурсивная процедура вычисления n-го числа Фибоначчи #5
C++
1
2
3
4
5
6
7
8
int fib(int n,int fib0, int fib1)
{
if(n==0)
return fib0;
else if(n==1)
return fib1;
else return fib(n-1,fib0,fib1)+fib(n-2,fib0,fib1);//fib0 и fib1 -- первые 2 числа, обычно они по 1
}
Кстати, если тебе нужны сами числа Фибоначчи, а не рекурсия, то лучше считать их по формуле общего члена. В интернетах ее полно. Рекурсия быстро сожрет память.
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
05.04.2012, 02:27     Рекурсивная процедура вычисления n-го числа Фибоначчи #6
Цитата Сообщение от kkk008009kkk Посмотреть сообщение
alexey31415,
Проверку на базовый случай реализовал:



А далее не знаю алгоритм.



Число фибоначи-это сумма двух предыдущих. Не знаю, как реализовать сложение процедур от n-1 и n-2 , чтобы получить n
если идти так, как вы предлагается, то там будет ветвящееся дерево параллельных (казалось бы) рекурсий, поэтому предлагаю идти с начала...
как только он доберется вглубь до нужного номера- он присвоит его предыдущему, другой без долгих раздумий своему предыдущему и так до нерекурсивной функции, которая и выведет результат


соответственно нерекурсивная функция отвечает за корректное начало работы рекурсивной)))
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 02:41  [ТС]     Рекурсивная процедура вычисления n-го числа Фибоначчи #7
FesS92, Это функция. Я же ясно указал, что нужна процедура. Но серовно, спасибо.

Добавлено через 3 минуты
UFO94, Не работает, пишет ошибку:

too few arguments to function `int fib(int, int, int)'
Кстати, это тоже функция?

Читайте, пожалуйста, внимательнее темы, чтобы зря не растрачивать свое время.
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
05.04.2012, 02:48     Рекурсивная процедура вычисления n-го числа Фибоначчи #8
в С нет процедур))

неофициально процедура- это функция, которая не возвращает значения

void NAZVANIE() {}

Добавлено через 3 минуты
тебе нужно вытащить число!
я знаю 3 способа (на вскидку)
1) процедура внутри себя изменяет значение переменной (так называемый побочный эффект) - обычно это плохо
2) через параметр (задается ref, out) //в С#, НО ЯЗЫКИ ПОХОЖИ, сорь за капс
3) возвращение значения функции
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 02:53  [ТС]     Рекурсивная процедура вычисления n-го числа Фибоначчи #9
FesS92,
Программа не работает:

6 too many arguments to function `int Not_Rekurs(int)'
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
05.04.2012, 02:56     Рекурсивная процедура вычисления n-го числа Фибоначчи #10
Цитата Сообщение от kkk008009kkk Посмотреть сообщение
FesS92,
Программа не работает:
как функцию в коде вызываешь?

мои две функции готовы... скорее всего ты просто вызываешь не ту процедуру или не совсем так)

пример: я хочу найти пятый элемент последовательности, я вызываю

X=Not_Rekurs(5);

нерекурсивная функция (Not_Rekurs) просто уменьшает количество вводимых(не нужных) параметров и правильно запускает рекурсивный блок с правильными начальными значениями (Rekurs)

нужная вам функция- Not_Rekurs,
нужный вам рекурсивный блок (функция) - Rekurs ))

(простите, я спать)) )
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 02:58  [ТС]     Рекурсивная процедура вычисления n-го числа Фибоначчи #11
Сейчас уточнил, нужно сделать процедуру наподобие

void xxx( int &x );
функцию, которая ничего не возвращает, то есть тип её результата это void

Добавлено через 49 секунд
FesS92,
Not_Rekurs(k);
Но это не важно, компилятор до этой строки не доходит.

Добавлено через 1 минуту
FesS92, Ту ошибку исправил, сейчас новая

16 C:\Documents and Settings\Admin\Рабочий стол\C++\Безымянный2.cpp `Rekurs' undeclared (first use this function)
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
05.04.2012, 03:34     Рекурсивная процедура вычисления n-го числа Фибоначчи #12
C++
1
2
3
unsigned long int fibonacci( unsigned long int number ) {
    return ( number == 0 || number == 1 ) ? number : fibonacci( number - 1 ) + fibonacci( number - 2 );
}
Добавлено через 14 минут
Как вы вообще представляете рекурсивную функцию вычисления n-го числа фибоначи которая возвращает void? У меня конечно мелькнуло что то в голове, но это бред полный получается.
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 03:36  [ТС]     Рекурсивная процедура вычисления n-го числа Фибоначчи #13
Toshkarik, Задание:
Рекурсивная процедура вычисления n-го числа Фибоначчи
Решение Ваше подходит под определение?

Просто написал с факториалом, получилось по другому в синтаксисе:

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


void Factorial ( int n, int &fact )
{
if ( n == 0 ) fact = 1;
else {
Factorial(n-1, fact);
fact *= n;

}
}

main()
{
int k,u;
scanf("%d",&k);
Factorial (k,u);
printf("%d",u);
getch();

}
Добавлено через 1 минуту
Цитата Сообщение от Toshkarik Посмотреть сообщение
Как вы вообще представляете рекурсивную функцию вычисления n-го числа фибоначи которая возвращает void? У меня конечно мелькнуло что то в голове, но это бред полный получается.
Сложно представляю, поэтому и создал тему
alexey31415
 Аватар для alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 03:46     Рекурсивная процедура вычисления n-го числа Фибоначчи #14
C++
1
2
3
4
5
6
7
8
// рекурсивный метод вычисления чисел Фибоначчи 
unsigned long fibonacci( unsigned long number ) 
{ 
if ( ( number == 0 ) || ( number == 1 ) ) // основные случаи 
return number; 
else // рекурсивный шаг 
return fibonacci( number - 1 ) + fibonacci( number - 2 ) ; 
}
и не нужно функций с 3-4 параметрами
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
05.04.2012, 04:19     Рекурсивная процедура вычисления n-го числа Фибоначчи #15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
/*
 *
 */
void fibonacci( unsigned long int &number, int count, unsigned long int prev = 0 ) {
    if ( count > 1 ) {
 
    number += prev;
 
    fibonacci( number, count - 1, number - prev );
    }
}
 
int main() {
    unsigned long int fib = 1;
 
    fibonacci( fib, 10 );
 
    std::cout << fib << std::endl;
 
    return 0;
}
Вот пожалуйста, рекурсивная "процедура" на С++. Первый параметр это переменная где будет храниться число фибоначчи ( должна обязательно изначально быть равна 1, так как ряд начинается с 0 и 1 ), второй параметр это порядковый номер члена ряда, который нужно вычислить.
FesS92
48 / 48 / 6
Регистрация: 22.02.2012
Сообщений: 137
05.04.2012, 08:23     Рекурсивная процедура вычисления n-го числа Фибоначчи #16
Цитата Сообщение от alexey31415 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
// рекурсивный метод вычисления чисел Фибоначчи 
unsigned long fibonacci( unsigned long number ) 
{ 
if ( ( number == 0 ) || ( number == 1 ) ) // основные случаи 
return number; 
else // рекурсивный шаг 
return fibonacci( number - 1 ) + fibonacci( number - 2 ) ; 
}
и не нужно функций с 3-4 параметрами
Зато идет ветвистая рекурсия))
alexey31415
 Аватар для alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 09:46     Рекурсивная процедура вычисления n-го числа Фибоначчи #17
Цитата Сообщение от FesS92 Посмотреть сообщение
Зато идет ветвистая рекурсия
не бывает так,чтоб было всё хорошо,согласен в этом случае нагрузка на процессор больше,но писать меньше надо
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.04.2012, 10:01     Рекурсивная процедура вычисления n-го числа Фибоначчи #18
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
void fibb( int n, int &res )
{   
    static int arr[1000] = { };
    
    if ( n == 1 || n == 2 )
    {
        res = 1;
        return;
    }   
    
    if ( !arr[n - 1] )
        fibb(n - 1, arr[n - 1]);
    
    if ( !arr[n - 2] )
        fibb(n - 2, arr[n - 2]);
        
    res = arr[n - 1] + arr[n - 2];
}
 
int main()
{
    int x;
    fibb(7, x);
    std::cout << x;
}
alexey31415
 Аватар для alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 13:45     Рекурсивная процедура вычисления n-го числа Фибоначчи #19
давайте уже проведём конкурс на самую изобретательную реализацию вычисления чисел Фибоначчи
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.04.2012, 14:17     Рекурсивная процедура вычисления n-го числа Фибоначчи
Еще ссылки по теме:

Проведите программу вычисления числа Фибоначчи с заданным номером C++
C++ Рекурсивная процедура перевода числа из десятичной системы счисления в двоичную
C++ С помощью цикла написать программу вычисления числа Фибоначчи

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.04.2012, 14:17     Рекурсивная процедура вычисления n-го числа Фибоначчи #20
Цитата Сообщение от alexey31415 Посмотреть сообщение
давайте уже проведём конкурс на самую изобретательную реализацию вычисления чисел Фибоначчи
C
1
2
3
4
5
6
#include <stdio.h>
 
main(int n, int x, int r)
{       
    return x ? scanf("%d", &n) : 0, r = n < 2 ? n : main(n - 1, 0, 0) + main(n - 2, 0, 0), x ? printf("%d\n", r) : 0, r;
}
Компилировать только как С, С++ компиляторы на такое ругаться будут.
Вводим номер числа - получаем число.
Yandex
Объявления
05.04.2012, 14:17     Рекурсивная процедура вычисления n-го числа Фибоначчи
Ответ Создать тему
Опции темы

Текущее время: 11:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru