2

Условие: реализуйте функцию seqA, находящую элементы следующей рекуррентной последовательности

a_0 = 1; a_1 = 2 ; a_2 = 3; a_{k+3} = a_{k+2} + a_{k+1} - 2 a_{k}

Код:

seqA :: Integer -> Integer
seqA n 
   | n == 0 = 1
   | n == 1 = 2
   | n == 2 = 3
   | otherwise = helper n
 helper k = helper(k-1) + helper(k-2) - 2*helper(k-3)
Nicolas Chabanovsky
  • 51,426
  • 87
  • 267
  • 507
anon
  • 21
  • Как вы обнаружили, что там ошибка? – tutankhamun Oct 01 '15 at 13:57
  • Проверяющая система stepic мне выдает ошибку:

    Failed test #1. Run time error: main: <>

     – anon Oct 01 '15 at 14:00
  • Если вам дан исчерпывающий ответ, отметьте его как верный (галка напротив выбранного ответа). – Nicolas Chabanovsky Oct 01 '15 at 15:29

2 Answers2

9

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

Правильный код:

seqA :: Integer -> Integer
seqA n 
    | n == 0 = 1
    | n == 1 = 2
    | n == 2 = 3
    | otherwise = seqA(n-1) + seqA(n-2) - 2*seqA(n-3)

Однако он страшно неэффективен, я даже не рискну предположить его вычислительную сложность, но вычисление 30-го члена последовательности уже занимает несколько секунд. Вычисления 50-го и тем более 100-го я не дождался.

Для более эффективного вычисления, вы можете попробовать вот такой код:

seqA :: Num a => [a]
seqA = 1:2:3:(f 1 2 3) where f x y z = let n=z+y-2*x in n:(f y z n)

Тогда

take 100 seqA

выведет Вам первые 100 членов последовательности, а seqA !! n - любой n-ый элемент последовательности.

Alexander Razorenov
  • 321
0
seqA :: Integer -> Integer
seqA n
  | n == 0    = 1
  | n == 1    = 2
  | n == 2    = 3
  | otherwise = let
      helper a b c 0 = a
      helper a b c n = helper b c ((c + b) - 2 * a) (n - 1)
    in helper 1 2 3 n
serghei
  • 255