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

Рекурсия в нахождении числа ряда Фибоначчи. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.80
deematter
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 7
18.12.2011, 13:52     Рекурсия в нахождении числа ряда Фибоначчи. #1
Лаба: написать программу, находящуую заданный элемент ряда Фибоначчи.
Написал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
 
void main()
{
    int M[100], i, n;
    
    printf("Программа подсчитывает значение требуемого элемента ряда Фибоначчи.\n");
    printf("Введите номер желаемого числа: ");
    scanf("%d", &n);
        if ((n<=0) || (scanf("%d", &n) != 1))
        {   printf("Неккоректное значение!\n");
            return;
        }
        
    M[0] = 1;
    M[1] = 1;
    for (i=2; i<n; i++)
    {   M[i] = M[i-1] + M[i-2];
    }
    
    printf("%d'й член ряда Фибоначчи равен %d", n, M[i-1]);
}
Препод посмотрел, сказал поставит зачот если добавлю рекурсию. Надо сказать, он весьма нелюбим студентами и всегда старается всех завалить на самых мелких недочетах. Поэтому хотел спросить совета - как лучше всего использовать здесь рекурсию? Боюсь сделать что-то не так, а сдавать после завтра уже.
Я изначально хотел for записать в отдельную функцию, а потом просто вызвать в ходе программы, это вроде бы считается за рекурсию? Поправьте меня или подскажите код, которым это реализуется красиво и качественно?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
rostik123
 Аватар для rostik123
0 / 0 / 0
Регистрация: 19.10.2011
Сообщений: 22
18.12.2011, 14:10     Рекурсия в нахождении числа ряда Фибоначчи. #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<conio.h>
unsigned    long fibo(unsigned  long);
void main()
{
using   namespace std;
unsigned    long n;_  
    cout<<"Enter n:"; cin >> n;
    cout << "Fibo number:" << fibo(n) << endl;
    _getch();
}
unsigned    long fibo(unsigned  long number)
{
if(number==1)
return 1;
else    if (number==0)
return 0;
else
return fibo(number-1) + fibo(number-2);
}
deematter
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 7
18.12.2011, 14:26  [ТС]     Рекурсия в нахождении числа ряда Фибоначчи. #3
Цитата Сообщение от rostik123 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<conio.h>
unsigned    long fibo(unsigned  long);
void main()
{
using   namespace std;
unsigned    long n;_  
    cout<<"Enter n:"; cin >> n;
    cout << "Fibo number:" << fibo(n) << endl;
    _getch();
}
unsigned    long fibo(unsigned  long number)
{
if(number==1)
return 1;
else    if (number==0)
return 0;
else
return fibo(number-1) + fibo(number-2);
}
Боюсь, я не понимаю большую часть кода, не смогу объяснить преподу что и для чего.
А мой код совсем не исправить?
И плюс к этому - я на Убунту не могу правильно подключить conio.h.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
18.12.2011, 15:11     Рекурсия в нахождении числа ряда Фибоначчи. #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
 
typedef unsigned long long ulong;
 
ulong fib (int n)
{
    if (n==1 || n==2) return 1;
    return fib(n-1)+fib(n-2);
}
 
 
int main()
{
    int n;
    std:: cin >> n;
    std:: cout << fib(n) << "\n";
    system ("pause");
    return 0;
}
А если меморизацию поставите - зачет в кармане

Добавлено через 23 минуты
Что-то вроде
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
#include <iostream>
 
typedef _int64 ulong;
int mem[20]={0};
 
 
ulong fib (int n)
{
    if (n==1 || n==2) return 1;
    if (mem[n]!=0) return mem[n];
    else 
    {
        mem[n]=fib(n-1)+fib(n-2);
        return mem[n];
    }
}
 
 
int main()
{
    int n;
    std:: cin >> n;
    std:: cout << fib(n) << "\n";
    system ("pause");
    return 0;
}
Так гораздо быстрее работает
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
18.12.2011, 15:20     Рекурсия в нахождении числа ряда Фибоначчи. #5
Цитата Сообщение от Dani Посмотреть сообщение
mem[n]=fib(n-1)+fib(n-2);
лучше бы, наверное,
C++
1
mem[n]=fib(n-2)+fib(n-1);
дабы при вычислении fib(n-1) использовалось уже готовое к этому времени fib(n-2)
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
18.12.2011, 15:26     Рекурсия в нахождении числа ряда Фибоначчи. #6
я еще не выспался, массив типа int, а надо ulong.

Добавлено через 30 секунд
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
#include <iostream>
 
typedef _int64 ulong;
ulong mem[20]={0};
 
 
ulong fib (int n)
{
    if (n==1 || n==2) return 1;
    if (mem[n]!=0) return mem[n];
    else 
    {
        mem[n]=fib(n-2)+fib(n-1);
        return mem[n];
    }
}
 
 
int main()
{
    int n;
    std:: cin >> n;
    std:: cout << fib(n) << "\n";
    system ("pause");
    return 0;
}
deematter
0 / 0 / 0
Регистрация: 18.12.2011
Сообщений: 7
18.12.2011, 18:52  [ТС]     Рекурсия в нахождении числа ряда Фибоначчи. #7
Всем огромное спасибо, особенно Deni - ваш пример я использовал в качестве основного, правда без меморизации)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.08.2013, 12:20     Рекурсия в нахождении числа ряда Фибоначчи.
Еще ссылки по теме:

Рекурсия, ряд Фибоначчи (определить количество рекурсивных вызовов функции) C++
C++ Написал программу которая показывает числа из ряда Фибоначчи
C++ рекурсия числа Фибоначчи

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

Или воспользуйтесь поиском по форуму:
plosha
1 / 1 / 0
Регистрация: 05.06.2013
Сообщений: 8
15.08.2013, 12:20     Рекурсия в нахождении числа ряда Фибоначчи. #8
есть такая программа:
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "iostream"
using namespace std;
unsigned long F_Rec(short n)
    {
        if (n==1 || n==2) return 1;
        else return F_Rec(n-1)+F_Rec(n-2);
    }
int main ()
{
    short n;
    cout<<"n="; cin>>n;
    cout<<"F_Rec("<<n<<")="<<F_Rec(n)<<endl;
    return 0;
    }
Подскажите плиз, как можно вывести не число, соответствующее вводимому номеру(как сейчас), а все числа идущие до этого номера.
Yandex
Объявления
15.08.2013, 12:20     Рекурсия в нахождении числа ряда Фибоначчи.
Ответ Создать тему
Опции темы

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