Функция чисел Фибоначчи, предшествующих вводимому числу

@EMTEC · Регистрация: 29.10.2011

Author24 — интернет-сервис помощи студентам

С помощью рекурсивной функции вычислить и вывести числа Фибоначчи, предшествующие вводимому числу

@Duha666 · 11.03.2012, 18:30

C++

void find_fib(int a, int b, int x)
{
    if (b >= x)
        return;
    cout << b << ' ';
    find_fib(b, a + b, x);
}
 
find_fib(0, 1, x);

@Черный ворон · 11.03.2012, 18:30

вот здесь:
Рекурсия в нахождении числа ряда Фибоначчи.

@~~-=ЮрА=-~~ · 11.03.2012, 19:07

jeka061288, я постарался одновременно показать как решать данную задачу с циклом и рекурсией

C

#include <stdio.h>
 
int direct_fibo(int val)
{
    int fib1 = 1;
    int fib2 = 1;
    
    int fib_sum = fib2 + fib1;
    while(fib_sum <= val)
    {
        printf("%d ",fib1);
        fib_sum = fib2 + fib1;
        fib1 = fib2;
        fib2 = fib_sum;
    }
    return fib_sum;
}
 
int rekurs_fibo(int fib1, int fib2, int val)
{
    int fib_sum = fib2 + fib1;
    if(fib_sum <= val)
    {
        printf("%d ",fib1);
        fib_sum =+ rekurs_fibo(fib2, (fib1 + fib2), val);
    }
    else
        printf("%d ",fib1);
    return fib_sum;
}
 
int main()
{
    int value;
    int direct_sum;
    int rekurs_sum;
    while(1)
    {
        printf("Enter value : ");
        scanf("%d",&value);
        direct_sum = direct_fibo(value);
        printf("\ndirect_sum %d\n",direct_sum);
        rekurs_sum = rekurs_fibo(1,1,value);
        printf("\nrekurs_sum %d\n",rekurs_sum);
    }
    return 0;
}

go · 11.03.2012, 19:15

C++

long fibon(const unsigned& n)
{
   return !n || n == 1 ? 1 : fibon(n - 1) + fibon(n - 2);
}

@EMTEC · 11.03.2012, 19:17 **[ТС]**

Подскажите while(1) - это бесконечный ввод и как правильно понять - как работает rekurs_sum = rekurs_fibo(1,1,value); ?

@~~-=ЮрА=-~~ · 11.03.2012, 19:31

Сообщение от jeka061288

Подскажите while(1) - это бесконечный ввод

- да я решил оставить возможность постоянного ввода при желании можно записать так

Сообщение от -=ЮрА=-

while(1)
* * * * {
* * * * * * * * printf("Enter value : ");
* * * * * * * * scanf("%d",&value);
* * * * * * * * direct_sum = direct_fibo(value);
* * * * * * * * printf("\ndirect_sum %d\n",direct_sum);
* * * * * * * * rekurs_sum = rekurs_fibo(1,1,value);
* * * * * * * * printf("\nrekurs_sum %d\n",rekurs_sum);
* * * * }

- всё что красным убираем и получаем одноразовый ввод

@EMTEC · 11.03.2012, 19:31 **[ТС]**

Спасибо ,понял.

@~~-=ЮрА=-~~ · 11.03.2012, 19:35

Сообщение от jeka061288

и как правильно понять - как работает rekurs_sum = rekurs_fibo(1,1,value); ?

- я специально приводил всесте и

Сообщение от -=ЮрА=-

int direct_fibo(int val)

и

Сообщение от -=ЮрА=-

int rekurs_fibo(int fib1, int fib2, int val)

, они имеют аналогичный функционал и логику, рекурсия как бы заменяет цикл, мы вызываем функцию повторно вместо того чтобы переходить к след итерации.

Смотри тут изменяем величины в цикле

Сообщение от -=ЮрА=-

fib_sum = fib2 + fib1;
* * * * * * * * fib1 = fib2;
* * * * * * * * fib2 = fib_sum;

,
а здесь вместо того чтобы организовывать итерации, просто вызываем функцию с изменёнными аргументами

Сообщение от -=ЮрА=-

fib_sum =+ rekurs_fibo(fib2, (fib1 + fib2), val);

Тут для понимания лучше всего поможет пошаговое прохождение алгоритма

Добавлено через 1 минуту
jeka061288, рекурсия подразумевает повторный вызов функции внутри её тела, благодаря чему возможно изменение её аргументов без итераций, т.е. как бы вызываем функцию уже с результатами предыдущих расчётов

@EMTEC · 11.03.2012, 19:37 **[ТС]**

Благодарю вас за помощь и разъяснения ,все понятно!

@Черный ворон · 11.03.2012, 20:50

Сообщение от -=ЮрА=-

jeka061288, я постарался одновременно показать как решать данную задачу с циклом и рекурсией

C

#include <stdio.h>
 
int direct_fibo(int val)
{
    int fib1 = 1;
    int fib2 = 1;
    
    int fib_sum = fib2 + fib1;
    while(fib_sum <= val)
    {
        printf("%d ",fib1);
        fib_sum = fib2 + fib1;
        fib1 = fib2;
        fib2 = fib_sum;
    }
    return fib_sum;
}
 
int rekurs_fibo(int fib1, int fib2, int val)
{
    int fib_sum = fib2 + fib1;
    if(fib_sum <= val)
    {
        printf("%d ",fib1);
        fib_sum =+ rekurs_fibo(fib2, (fib1 + fib2), val);
    }
    else
        printf("%d ",fib1);
    return fib_sum;
}
 
int main()
{
    int value;
    int direct_sum;
    int rekurs_sum;
    while(1)
    {
        printf("Enter value : ");
        scanf("%d",&value);
        direct_sum = direct_fibo(value);
        printf("\ndirect_sum %d\n",direct_sum);
        rekurs_sum = rekurs_fibo(1,1,value);
        printf("\nrekurs_sum %d\n",rekurs_sum);
    }
    return 0;
}

хм... мне очень долгое время преподаватель всё продолжает упорно объяснять, что "двойное" сравнение как в 10 строке ( while(fib_sum <= val) ) не есть хорошо. вроде как это два сравнения и сработает медленнее чем инкрементация переменной (в данном случае val) перед циклом и в условии выхода сравнение только "<".
так как же всё-таки более правильно?

@~~-=ЮрА=-~~ · 11.03.2012, 21:13

Черный ворон, если нужно пропечатать все числа фибоначи до указанного числа то следует использовать именно такое условие,как вариант попробуй изменить условие на меньше и погляди что станет с выводом.,Использование того или иного условия обусловлено требованиями алгоритма,а не требованиями преподавателя...

@~~-=ЮрА=-~~ · 11.03.2012, 21:16

Чтобы снять все вопросы, предлагаю провести сравнение для ввода 89

Отработка с условием <=
Enter value : 89
1 1 2 3 5 8 13 21 34 55
direct_sum 144
1 1 2 3 5 8 13 21 34 55
rekurs_sum 144
Enter value :

Отработка с условием <
Enter value : 89
1 1 2 3 5 8 13 21 34
direct_sum 89
1 1 2 3 5 8 13 21 34
rekurs_sum 89
Enter value :

Как видим для условия < в ряде отсутсвует 55
Использование того или другого условия диктуется требованиями алгоритма и реализации,
если бы условие <= было ненужным его бы попросту исключили из операторов языка, но почему то же не исключают.
Не вопрос 90% задач могут быть решены без этого условия, остальные 10% никак не могут
или же обход этого условия колоссально увеличит сложность алгоритма...

Добавлено через 53 секунды
Резюме

Сообщение от Черный ворон

while(fib_sum <= val) ) не есть хорошо

- правда?

Сообщение от -=ЮрА=-

90% задач могут быть решены без этого условия, остальные 10% никак не могут или же обход этого условия колоссально увеличит сложность алгоритма...

@EMTEC 1 / 1 / 0 Регистрация: 29.10.2011 Сообщений: 110
		1
	Функция чисел Фибоначчи, предшествующих вводимому числу 11.03.2012, 18:27. Показов 1738. Ответов 12 Метки нет (Все метки) С помощью рекурсивной функции вычислить и вывести числа Фибоначчи, предшествующие вводимому числу 0

@Черный ворон 138 / 132 / 57 Регистрация: 31.01.2012 Сообщений: 435
	11.03.2012, 18:30	3
	вот здесь: Рекурсия в нахождении числа ряда Фибоначчи. 1

@EMTEC 1 / 1 / 0 Регистрация: 29.10.2011 Сообщений: 110
	11.03.2012, 19:17 [ТС]	6
	Подскажите while(1) - это бесконечный ввод и как правильно понять - как работает rekurs_sum = rekurs_fibo(1,1,value); ? 0

@~~-=ЮрА=-~~ Заблокирован
	11.03.2012, 19:31	7
	Сообщение от jeka061288 Подскажите while(1) - это бесконечный ввод - да я решил оставить возможность постоянного ввода при желании можно записать так Сообщение от -=ЮрА=- while(1) * * * * { * * * * * * * * printf("Enter value : "); * * * * * * * * scanf("%d",&value); * * * * * * * * direct_sum = direct_fibo(value); * * * * * * * * printf("\ndirect_sum %d\n",direct_sum); * * * * * * * * rekurs_sum = rekurs_fibo(1,1,value); * * * * * * * * printf("\nrekurs_sum %d\n",rekurs_sum); * * * * } - всё что красным убираем и получаем одноразовый ввод 1

@EMTEC 1 / 1 / 0 Регистрация: 29.10.2011 Сообщений: 110
	11.03.2012, 19:31 [ТС]	8
	Спасибо ,понял. 0

@~~-=ЮрА=-~~ Заблокирован
	11.03.2012, 19:35	9
	Сообщение от jeka061288 и как правильно понять - как работает rekurs_sum = rekurs_fibo(1,1,value); ? - я специально приводил всесте и Сообщение от -=ЮрА=- int direct_fibo(int val) и Сообщение от -=ЮрА=- int rekurs_fibo(int fib1, int fib2, int val) , они имеют аналогичный функционал и логику, рекурсия как бы заменяет цикл, мы вызываем функцию повторно вместо того чтобы переходить к след итерации. Смотри тут изменяем величины в цикле Сообщение от -=ЮрА=- fib_sum = fib2 + fib1; * * * * * * * * fib1 = fib2; * * * * * * * * fib2 = fib_sum; , а здесь вместо того чтобы организовывать итерации, просто вызываем функцию с изменёнными аргументами Сообщение от -=ЮрА=- fib_sum =+ rekurs_fibo(fib2, (fib1 + fib2), val); Тут для понимания лучше всего поможет пошаговое прохождение алгоритма Добавлено через 1 минуту jeka061288, рекурсия подразумевает повторный вызов функции внутри её тела, благодаря чему возможно изменение её аргументов без итераций, т.е. как бы вызываем функцию уже с результатами предыдущих расчётов 1

@EMTEC 1 / 1 / 0 Регистрация: 29.10.2011 Сообщений: 110
	11.03.2012, 19:37 [ТС]	10
	Благодарю вас за помощь и разъяснения ,все понятно! 0

@~~-=ЮрА=-~~ Заблокирован
	11.03.2012, 21:13	12
	Черный ворон, если нужно пропечатать все числа фибоначи до указанного числа то следует использовать именно такое условие,как вариант попробуй изменить условие на меньше и погляди что станет с выводом.,Использование того или иного условия обусловлено требованиями алгоритма,а не требованиями преподавателя... Изображения 1

@~~-=ЮрА=-~~ Заблокирован
	11.03.2012, 21:16	13
	Чтобы снять все вопросы, предлагаю провести сравнение для ввода 89 Отработка с условием <= Enter value : 89 1 1 2 3 5 8 13 21 34 55 direct_sum 144 1 1 2 3 5 8 13 21 34 55 rekurs_sum 144 Enter value : Отработка с условием < Enter value : 89 1 1 2 3 5 8 13 21 34 direct_sum 89 1 1 2 3 5 8 13 21 34 rekurs_sum 89 Enter value : Как видим для условия < в ряде отсутсвует 55 Использование того или другого условия диктуется требованиями алгоритма и реализации, если бы условие <= было ненужным его бы попросту исключили из операторов языка, но почему то же не исключают. Не вопрос 90% задач могут быть решены без этого условия, остальные 10% никак не могут или же обход этого условия колоссально увеличит сложность алгоритма... Добавлено через 53 секунды Резюме Сообщение от Черный ворон while(fib_sum <= val) ) не есть хорошо - правда? Сообщение от -=ЮрА=- 90% задач могут быть решены без этого условия, остальные 10% никак не могут или же обход этого условия колоссально увеличит сложность алгоритма... 0