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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 44, средняя оценка - 4.80
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
#1

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

05.04.2012, 01:25. Просмотров 6890. Ответов 25
Метки нет (Все метки)

Добрый день. Подскажите, пожалуйста, алгоритм рекурсивной процедуры вычисления n-го числа Фибоначчи.

Только начал изучать процедуры и рекурсии, поэтому задача вызвала затруднения.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2012, 01:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсивная процедура вычисления n-го числа Фибоначчи (C++):

Рекурсивная процедура вычисления факториала - C++
Обязательно все через рекурсии надо сделать!! Помогите студенту сдать зачет

Рекурсивная процедура вычисления биномиальных коэффициентов - C++
Помогите, пожалуйста! Нужно сдать сегодня. А в рекурсии Си не бум-бум Написать рекурсивную процедуру вычисления биномиальных ...

Рекурсивная процедура перевода числа из десятичной системы счисления в двоичную - C++
3) Написать рекурсивную процедуру перевода нату¬рального числа из десятичной системы счисления в двоич¬ную.

Рекурсивная функция: вычисление суммы чисел Фибоначчи, пока они меньше введенного числа - C++
Вроде примитивная задача, но реализовать не смог, да и нигде такого не обсуждалось, так что вот: Требуется реализовать рекурсивную функцию,...

Рекурсивная процедура для вывода на экран цифр натурального числа в обратном порядке! - C++
Написать рекурсивную процедуру для вывода на экран цифр натурального числа в обратном порядке!

Рекурсивная процедура для вывода на экран цифр натурального числа в обратном порядке - C++
Разработать блок-схему и программу для решения задач с использованием функций. Задание:Написать рекурсивную процедуру для вывода на экран...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 01:39 #2
у тебя должна происходить проверка на базовый случай - это когда аргумет функции твоей равен 1 или 0,в этих случаях функция возвращает 1 и 0 соответсвенно,если другой аргумент,происходит вызов функции с меньшим на единицу аргументом
или тебе надо попроще и с куском кода?
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 02:14  [ТС] #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 #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
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
05.04.2012, 02:19 #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 #6
Цитата Сообщение от kkk008009kkk Посмотреть сообщение
alexey31415,
Проверку на базовый случай реализовал:



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



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


соответственно нерекурсивная функция отвечает за корректное начало работы рекурсивной)))
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 02:41  [ТС] #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 #8
в С нет процедур))

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

void NAZVANIE() {}

Добавлено через 3 минуты
тебе нужно вытащить число!
я знаю 3 способа (на вскидку)
1) процедура внутри себя изменяет значение переменной (так называемый побочный эффект) - обычно это плохо
2) через параметр (задается ref, out) //в С#, НО ЯЗЫКИ ПОХОЖИ, сорь за капс
3) возвращение значения функции
kkk008009kkk
46 / 46 / 1
Регистрация: 24.03.2011
Сообщений: 315
05.04.2012, 02:53  [ТС] #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 #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  [ТС] #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
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
05.04.2012, 03:34 #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  [ТС] #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
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 03:46 #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
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
05.04.2012, 04:19 #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 ), второй параметр это порядковый номер члена ряда, который нужно вычислить.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.04.2012, 04:19
Привет! Вот еще темы с ответами:

Рекурсивная функция вычисления разрядности числа в двоичном виде - C++
Есть неработающий код: #include &lt;iostream&gt; using namespace std; unsigned char capacity (unsigned char number) { ...

Рекурсивная функция для вычисления количества цифр натурального числа - C++
Нужно написать рекурсивную функцию для вычисления количества цифр натурального числа. Подскажите какой алгоритм нужен, для обычного...

Напишите функцию для вычисления и-го числа Фибоначчи - C++
Напишите функцию для вычисления и-го числа Фибоначчи. Реализуйте функцию итеративно и рекурсивно. Скорость рекурсивной версии не должна...

Написать программу для вычисления n-го числа Фибоначчи - C++
Написать программу для вычисления n-го числа Фибоначчи, используя рекурсию: F(n) = F(n -1) + F(n - 2); F(1) = F(2) = 1.


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.04.2012, 04:19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru