2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Хвостовая рекурсия Haskell
Сообщение08.04.2020, 22:27 


11/12/16
403
сБп
Здравствуйте! Мне нужно составить код для вычисления следующей рекуррентной последовательности: $a_0 = 1, a_1 = 2, a_2 = 3, a_n = a_{n-1} + a_{n-2} - 2a_{n-3}$. С помощью обычной рекурсии и хвостовой рекурсии.

С обычной я разобрался.
Код:
seq :: Integer -> Integer
seq n | n >= 0  && n <= 2   = (n + 1)
      | n > 2               = seq (n - 1) + seq (n - 2) - 2 * seq (n - 3)
      | otherwise           = error "arg must be >= 0"
С хвостовой пока не получается. Помогите, пожалуйста.

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение08.04.2020, 22:58 
Заслуженный участник


09/05/12
25179
Для хвостовой рекурсии нужно, чтобы в каждом теле функции был только один рекурсивный вызов, а тут их три. При этом каждый член последовательности зависит от трех предыдущих, а хвостовая рекурсия позволяет сосчитать только один. Какой вывод из этого следует сделать?

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 00:04 


11/12/16
403
сБп
По видимому это будет функция от четырех аргументов. Только какая она будет не понятно.

Что-нибудь вроде:
Код:
helperS n1 n2 n3 n = helperS n1 n2 (n1 + n2 - 2 * n3) (n - 2)

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 00:21 
Заслуженный участник


09/05/12
25179
gogoshik в сообщении #1452950 писал(а):
Только какая она будет не понятно.
Допустим, вы пытаетесь считать какой-нибудь десятый член последовательности вручную. Что именно вы будете делать? Опишите свои действия - просто словами.

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 00:28 


11/12/16
403
сБп
Pphantom в сообщении #1452959 писал(а):
Допустим, вы пытаетесь считать какой-нибудь десятый член последовательности вручную. Что именно вы будете делать? Опишите свои действия - просто словами.
Возьму 9, 8 и 7 члены последовательности и подставлю в данную рекуррентную формулу.

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 00:38 
Заслуженный участник


27/04/09
28128
gogoshik в сообщении #1452950 писал(а):
Код:
helperS n1 n2 n3 n = helperS n1 n2 (n1 + n2 - 2 * n3) (n - 2)
Идея как будто та, но исполнение не то, да. Можно ещё попробовать как-то преобразовать исходную последовательность, чтобы её рекуррентная формула была вида $A_n = \ldots A_{n-1} \ldots$, без вхождений $A_{n-2}$ и так далее. Получится — и хвостовая рекурсия получится.

-- Чт апр 09, 2020 02:39:51 --

gogoshik в сообщении #1452960 писал(а):
Возьму 9, 8 и 7 члены последовательности и подставлю в данную рекуррентную формулу.
Но откуда они будут вам известны? А вот Pphantom может вполне намекать на динамическое программирование. (Результат тут везде правда выйдет одинаковый.)

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 00:40 
Заслуженный участник


09/05/12
25179
gogoshik в сообщении #1452960 писал(а):
Возьму 9, 8 и 7 члены последовательности и подставлю в данную рекуррентную формулу.
А откуда вы их возьмете? Нет, честный набор действий напишите.
arseniiv в сообщении #1452963 писал(а):
Можно ещё попробовать как-то преобразовать исходную последовательность, чтобы её рекуррентная формула была вида $A_n = \ldots A_{n-1} \ldots$, без вхождений $A_{n-2}$ и так далее.
Можно, но это задача уже не по программированию. Так-то можно не мелочиться и просто найти явное выражение для $a_n$...

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 01:43 
Заслуженный участник


27/04/09
28128

(СПОЙЛЕРНЫЙ ответ Pphantom)

Pphantom в сообщении #1452964 писал(а):
Можно, но это задача уже не по программированию.
Как раз по нему, я предлагаю последовательность $A_n = (a_n, a_{n+1}, a_{n+2})$. :-)

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 02:05 
Заслуженный участник


09/05/12
25179
arseniiv, тогда согласен. :mrgreen:

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 12:55 


11/12/16
403
сБп
Pphantom в сообщении #1452964 писал(а):
А откуда вы их возьмете? Нет, честный набор действий напишите.
Будет так:
Код:
a(0) = 1
a(1) = 2
a(2) = 3
a(n) = a(n-1) + a(n-2) - 2 * a(n-3)
n=3: a(3) = a(2) + a(1) - 2 * a(0) = 3 + 2 - 2 * 1 = 3
n=4: a(4) = a(3) + a(2) - 2 * a(1) = 3 + 3 - 2 * 2 = 2
n=5: a(5) = a(4) + a(3) - 2 * a(2) = 2 + 3 - 2 * 3 = -1
n=6: a(6) = a(5) + a(4) - 2 * a(3) = (-1) + 2 - 2 * 3 = -5
n=7: a(7) = a(6) + a(5) - 2 * a(4) = (-5) + (-1) - 2 * 2 = -10
n=8: a(8) = a(7) + a(6) - 2 * a(5) = (-10) + (-5) - 2 * (-1) = -13
n=9: a(9) = a(8) + a(7) - 2 * a(6) = (-13) + (-10) - 2 * (-5) = -13
n=10: a(10) = a(9) + a(8) - 2 * a(7) = (-13) + (-13) - 2 * (-10) = -6


a(0) = 1
a(1) = 2
a(2) = 3
a(n+3) = a(n+2) + a(n+1) - 2 * a(n)
n=0: a(3) = a(2) + a(1) - 2 * a(0) = 3 + 2 - 2 * 1 = 3
n=1: a(4) = a(3) + a(2) - 2 * a(1) = 3 + 3 - 2 * 2 = 2
n=2: a(5) = a(4) + a(3) - 2 * a(2) = 2 + 3 - 2 * 3 = -1
n=3: a(6) = a(5) + a(4) - 2 * a(3) = (-1) + 2 - 2 * 3 = -5
n=4: a(7) = a(6) + a(5) - 2 * a(4) = (-5) + (-1) - 2 * 2 = -10
n=5: a(8) = a(7) + a(6) - 2 * a(5) = (-10) + (-5) - 2 * (-1) = -13
n=6: a(9) = a(8) + a(7) - 2 * a(6) = (-13) + (-10) - 2 * (-5) = -13
n=7: a(10) = a(9) + a(8) - 2 * a(7) = (-13) + (-13) - 2 * (-10) = -6


n=0: a(0) = 1
n=1: a(1) = 2
n=2: a(2) = 3
k = n - 3
a(n) = a(k+2) + a(k+1) - 2 * a(k)
n=3, k=0: a(3) = a(2) + a(1) - 2 * a(0) = 3 + 2 - 2 * 1 = 3
n=4, k=1: a(4) = a(3) + a(2) - 2 * a(1) = 3 + 3 - 2 * 2 = 2
n=5, k=2: a(5) = a(4) + a(3) - 2 * a(2) = 2 + 3 - 2 * 3 = -1
n=6, k=3: a(6) = a(5) + a(4) - 2 * a(3) = (-1) + 2 - 2 * 3 = -5
n=7, k=4: a(7) = a(6) + a(5) - 2 * a(4) = (-5) + (-1) - 2 * 2 = -10
n=8, k=5: a(8) = a(7) + a(6) - 2 * a(5) = (-10) + (-5) - 2 * (-1) = -13
n=9, k=6: a(9) = a(8) + a(7) - 2 * a(6) = (-13) + (-10) - 2 * (-5) = -13
n=10, k=7: a(10) = a(9) + a(8) - 2 * a(7) = (-13) + (-13) - 2 * (-10) = -6 

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 13:13 
Заслуженный участник


09/05/12
25179
Угу. А теперь смотрите: вы каждый раз используете три уже вычисленных ранее значения, двигаясь в сторону роста номера до тех пор, пока не добираетесь до нужного. После этого процесс останавливается и на выход выдается последний результат. Сможете теперь описать функцию, которая "реализует" одну строчку ваших выкладок?

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 16:11 


11/12/16
403
сБп
В общем получается что-то такое:

Код:
seQ n | n >= 0      = seqHelp n 3 2 1
      | otherwise   = error "arg must be >= 0"

seqHelp 0 _ _ pp = pp
seqHelp 1 _ p _  = p
seqHelp 2 c _ _  = c
seqHelp n c p pp = let q = c + p - 2 * pp in seqHelp (n - 1) q c p


Код:
*Test> seQ 301
1276538859311178639666612897162414
(0.02 secs, 8240640 bytes)


Спасибо! :D

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 16:27 
Заслуженный участник


09/05/12
25179
Да. Это не единственный возможный вариант, но вполне подходящий. :-)

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 16:59 
Заслуженный участник


27/04/09
28128
Да, я бы его немножко подсократил и заодно скрыл бы хелпер от глаз других функций того же модуля, окажись их много:

Используется синтаксис Haskell
a n | n >= 0    = go n 1 2 3
    | otherwise = error "a: arg must be nonnegative"
    where
      go 0 a0 _  _  = a0
      go n a0 a1 a2 = go (n - 1) a1 a2 (a2 + a1 - 2 * a0)

More is less. :D Чем меньше можно нечайно сломать, тем лучше.

UPD: Учёл совет warlock66613 ниже.

 Профиль  
                  
 
 Re: Хвостовая рекурсия Haskell
Сообщение09.04.2020, 23:49 
Заслуженный участник


02/08/11
6874
Я бы ещё переименовал h в go - это общепринятое название для функции-шага хвостовой рекурсии и его использование упростит чтение кода другими людьми.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group