Форум программистов, компьютерный форум, киберфорум
Basic
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
1

Обобщение чисел Фибоначчи

15.06.2016, 15:44. Показов 1410. Ответов 9
Метки нет (Все метки)

Программа вычисляет числа, заданные рекуррентной формулой
An = An-1 + An-2 + An-3 , где A1 = A2 = A3 = 1

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
REM
REM  f(n) = f(n - 1) + f(n - 2) + f(n - 3)
REM         f(1) = f(2) = f(3) = 1
REM
 
DECLARE FUNCTION f! (n!)
CLS
 
INPUT "N ="; n
 
FOR i = 1 TO n
   PRINT f(i);
NEXT i
END
 
FUNCTION f (n)
   IF n <= 3 THEN
      f = 1
   ELSE
      f = f(n - 1) + f(n - 2) + f(n - 3)
   END IF
END FUNCTION
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.06.2016, 15:44
Ответы с готовыми решениями:

Сумма первых 15 нечетных чисел Фибоначчи с первыми 5 четными числами Фибоначчи
Ребята вообщем такое задание :Напишите программу для вычисления сумму первых 15 нечетных чисел...

Вычисление чисел Фибоначчи и номера числа Фибоначчи с накопителями
Требуется три накопителя - текущий номер, само число Фибонначи и предыдущее число...

Определить номер N числа Фибоначчи, при котором сумма N первых чисел Фибоначчи превышает заданное число М
Определить номер N числа Фибоначчи, при котором сумма N первых чисел Фибоначчи превышает заданное...

Набрать с чисел Фибоначчи в интервале от 1 до 100, только просто числа, а также их порядковые номера в ряду Фибоначчи
Помогите с задачкой Набрать с чисел Фибоначчи в интервале от 1 до 100, только просто числа, а...

9
Модератор
Эксперт функциональных языков программированияЭксперт Python
29667 / 16217 / 3242
Регистрация: 12.02.2012
Сообщений: 26,872
Записей в блоге: 5
15.06.2016, 18:31 2
Лучший ответ Сообщение было отмечено echs как решение

Решение

Вот так будет считаться быстрее:

Visual Basic
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
28
29
30
31
32
33
34
'::: Быстрый вариант
 
Function G(n As Double, Optional c As Double = 1, _
           Optional p As Double = 1, Optional pp As Double = 1) As Double
           
     If n <= 3 Then
        G = c
     Else
        G = G(n - 1, c + p + pp, c, p)
     End If
           
           
End Function
 
'::: Медленный вариант
 
Function B(n As Double) As Double
 
   If n <= 3 Then
      B = 1
   Else
      B = B(n - 1) + B(n - 2) + B(n - 3)
   End If
   
 
End Function
 
Sub test()
 
    For i% = 1 To 30
        Debug.Print i%; " "; G(CDbl(i%))
    Next i%
    
End Sub
Сравните скорость выполнения.
1
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
15.06.2016, 19:44  [ТС] 3
Catstail
Пожалуйста, вы не могли бы пояснить ваш код!
Вроде написал много программ с рекурсией, а
все еще не понятно...
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
29667 / 16217 / 3242
Регистрация: 12.02.2012
Сообщений: 26,872
Записей в блоге: 5
15.06.2016, 20:21 4
Лучший ответ Сообщение было отмечено echs как решение

Решение

geh, это классика. Называется "накопительные параметры".

Visual Basic
1
2
3
4
5
6
7
8
Function G(n As Double, Optional c As Double = 1, _
           Optional p As Double = 1, Optional pp As Double = 1) As Double
     If n <= 3 Then
        G = c
     Else
        G = G(n - 1, c + p + pp, c, p)
     End If
End Function
У функции G один обязательный параметр (n) и три необязательных: c - текущее число (n), p - предыдущее число (n-1) и pp - предпредыдущее (n-2). Если n < 3, функция возвращает с. Легко убедиться, что при n=1 и 2 функция вернет 1, что верно.

Если n больше или равно 3, то вычисляем следующее число с+p+pp и заносим его в c; старое значение c заносим в p, старое значение p -> в pp. Старое значение pp затирается (оно уже не нужно). Уменьшаем n на 1 и делаем ОДИН рекурсивный вызов. Все. При вычислении n-го члена последовательности нужно будет порядка n рекурсивных вызовов.

А вот при простой рекурсии будет происходить многократное перевычисление ранее вычисленных членов. Это порождает огромное дерево вычислений, и соответствующее снижение производительности.

Добавлено через 7 минут
Чтобы подсчитать число рекурсивных вызовов я чуть подработал код. Переменная counter хранит число рекурсивных вызовов:

Visual Basic
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
Private counter As Long
 
Function G(n As Double, Optional c As Double = 1, _
           Optional p As Double = 1, Optional pp As Double = 1) As Double
     counter = counter + 1
     If n <= 3 Then
        G = c
     Else
        G = G(n - 1, c + p + pp, c, p)
     End If
End Function
 
Function B(n As Double) As Double
   counter = counter + 1
   If n <= 3 Then
      B = 1
   Else
      B = B(n - 1) + B(n - 2) + B(n - 3)
   End If
End Function
 
Sub test()
    For i% = 1 To 20
        counter = 0
        Debug.Print i%; " "; G(CDbl(i%)); " "; counter
    Next i%
End Sub
А вот результаты:

Код
Функия B (простая рекурсия):

 1   1   1 
 2   1   1 
 3   1   1 
 4   3   4 
 5   5   7 
 6   9   13 
 7   17   25 
 8   31   46 
 9   57   85 
 10   105   157 
 11   193   289 
 12   355   532 
 13   653   979 
 14   1201   1801 
 15   2209   3313 
 16   4063   6094 
 17   7473   11209 
 18   13745   20617 
 19   25281   37921 
 20   46499   69748 

Функция G (рекурсия с накопительным параметром)

 1   1   1 
 2   1   1 
 3   1   1 
 4   3   2 
 5   5   3 
 6   9   4 
 7   17   5 
 8   31   6 
 9   57   7 
 10   105   8 
 11   193   9 
 12   355   10 
 13   653   11 
 14   1201   12 
 15   2209   13 
 16   4063   14 
 17   7473   15 
 18   13745   16 
 19   25281   17 
 20   46499   18
Комментарии излишни.
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
15.06.2016, 20:59  [ТС] 5
Catstail
Спасибо!
0
6141 / 908 / 305
Регистрация: 25.02.2011
Сообщений: 1,292
Записей в блоге: 1
17.06.2016, 16:03 6
Можно и без рекурсии:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
Function fibo(n As Long) As Long
    Dim i As Long, a As Long, b As Long, c As Long, d As Long
    a = 1
    b = 1
    c = 1
    For i = 4 To n
        d = a + b + c
        a = b
        b = c
        c = d
    Next i
    fibo = c
End Function
или (убираем одну переменную)
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
Function fibo2(n As Long) As Long
    Dim i As Long, a As Long, b As Long, c As Long
    a = 1
    b = 1
    c = 1
    For i = 4 To n
        c = a + b + c
        b = c - a - b
        a = c - a - b
    Next i
    fibo2 = c
End Function
Сравнение скорости выполнения с рекурсией не производил
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
29667 / 16217 / 3242
Регистрация: 12.02.2012
Сообщений: 26,872
Записей в блоге: 5
17.06.2016, 16:25 7
Цитата Сообщение от m-ch Посмотреть сообщение
Можно и без рекурсии:
- конечно! А еще интереснее вывести формулу таких чисел в аналитическом виде. Для этого нужно решить рекуррентное соотношение:

https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{n}={F}_{n-1}+{F}_{n-2}+{F}_{n-3}

а для этого придется найти корни характеристического полинома:

https://www.cyberforum.ru/cgi-bin/latex.cgi?{\lambda }^{3}+{\lambda }^{2}+\lambda-1=0
0
6141 / 908 / 305
Регистрация: 25.02.2011
Сообщений: 1,292
Записей в блоге: 1
17.06.2016, 17:00 8
Я хотел по другому задать вопрос.
Если задача легко решается без рекурсии, то зачем реализовывать рекурсию?
При этом, как в примере из первого поста, рекурсия существенно увеличивает вычисления.
На мой взгляд, рекурсию нужно применять там, где без нее не обойтись, либо код с рекурсией значительно проще написать и производится меньше вычислений.
Если задача решается без рекурсии за тоже время, то лучше реализовать ее без рекурсии.
0
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
17.06.2016, 18:05  [ТС] 9
m-ch
Программист только тот, кто умеет писать рекурсивные
программы. Что касается чисел Фибоначчи, то они при
большом N все меньше отличаются от геометрической
прогрессии со знаменателем https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac {\sqrt5+1}{2}
1
526 / 761 / 133
Регистрация: 10.08.2015
Сообщений: 3,633
19.06.2016, 03:39 10
Цитата Сообщение от geh Посмотреть сообщение
Программист только тот, кто умеет писать рекурсивные
программы.
Программист - тот, кто умеет применять алгоритмы к структурам данных
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.06.2016, 03:39

Дано 100 целых чисел. Сколько среди них чисел Фибоначчи
дано 100 целіх чисел от 1 до 50 сколько среди них чисел фібоначі ???

Определить в заданной последовательности целых чисел количество чисел Фибоначчи
Определить в заданной последовательности целых чисел количество чисел Фибоначчи.

Определить, сколько из данных чисел входит во множество чисел Фибоначчи
Приветствую форумчане!Помогите пожалуйста решить задачку! Условие: Дано 100 целых чисел от 1 до...

Определить в заданной последовательности целых чисел количество чисел Фибоначчи
Определить в заданной последовательности целых чисел количество чисел Фибоначчи.


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

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