Вычислить член y(x) последовательности, определенный рекурентной формулой

@ZzzDa · Регистрация: 04.12.2010

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

Задание такое: вычислить член y(x) последовательности, определенный рекурентной формулой

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\operatorname{y}_{x + 2} - 6 \operatorname{y}_{x + 1} + 9 \operatorname y_x = 3^x (x+3)<br /> \operatorname y_0 = 1 \qquad \operatorname y_1 = 1$

Оригинал

y(x+2)-6*y(x+1)+9*y(x)=(3^x)*(x+3) y(0)=1 y(1)=1

Есть конечно пример, но там Fn(x), и у меня как-то не получается соотнести...
Fn(x)=3*Fn-1(x)+2*Fn+1(x) F0(x)=3 F1(X)=5

Lisp
1
2
3
4
5
6
7
8
9
(defun f(n x)
 
(cond
 
((= n 0) 3)
 
((= n 1) 5)
 
(t (/ (- (f (- n 1) x) (* 3 (f (- n 2) x))))))

@Nameless One · 08.10.2012, 03:11

Нужно всего-лишь из формулы выразить член с наибольшим номером:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\operatorname y_{x+2} = 6 \operatorname y_{x+1} - 9 \operatorname y_x + 3^x (x + 3)$

Lisp
1
2
3
4
5
6
7
(defun rec (x)
  (if (or (= x 0) (= x 1))
      1
    (+ (* 6 (rec (- x 1)))
       (- (* 9 (rec (- x 2))))
       (* (expt 3 (- x 2))
          (+ x 1)))))

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

Есть конечно пример, но там Fn(x)

Ну да, если заменить y(x) на Fn(x), то сразу все меняется...

@Catstail · 08.10.2012, 11:55

А вот тоже рекурсивное решение, но выполняющееся значительно быстрее:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defun rec-n (x &optional (r '(1 1)))
   (let* ((l (length r))
          (rr (+ (* 6 (car r))
                 (* -9 (cadr r))
                 (* (expt 3 (- l 2))
                    (+ l 1))))
         )
         (cond ((<= x 1) 1)
               ((= x l) rr) 
               (t (rec-n x (cons rr r))))))
 
==> rec-n
 
;; Проверка:
 
(rec-n 100)
 
==> 10076145907831553533093851548047661502598904162641551

Простое рекурсивное решение вынуждено много раз пересчитывать одно и то же:

Lisp
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
35
36
37
38
(trace rec)
 
==> rec
 
(rec 5)
 
    Вход в функцию rec Аргументы: 5
      Вход в функцию rec Аргументы: 4
        Вход в функцию rec Аргументы: 3
          Вход в функцию rec Аргументы: 2  <-!!!
            Вход в функцию rec Аргументы: 1
            Возврат из функции rec Результат: 1
            Вход в функцию rec Аргументы: 0
            Возврат из функции rec Результат: 1
          Возврат из функции rec Результат: 0
          Вход в функцию rec Аргументы: 1
          Возврат из функции rec Результат: 1
        Возврат из функции rec Результат: 3
        Вход в функцию rec Аргументы: 2  <-!!!
          Вход в функцию rec Аргументы: 1
          Возврат из функции rec Результат: 1
          Вход в функцию rec Аргументы: 0
          Возврат из функции rec Результат: 1
        Возврат из функции rec Результат: 0
      Возврат из функции rec Результат: 63
      Вход в функцию rec Аргументы: 3
        Вход в функцию rec Аргументы: 2  <-!!!
          Вход в функцию rec Аргументы: 1
          Возврат из функции rec Результат: 1
          Вход в функцию rec Аргументы: 0
          Возврат из функции rec Результат: 1
        Возврат из функции rec Результат: 0
        Вход в функцию rec Аргументы: 1
        Возврат из функции rec Результат: 1
      Возврат из функции rec Результат: 3
    Возврат из функции rec Результат: 513
 
==> 513

rec-n ведет себя значительно лучше:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(trace rec-n)
 
==> rec-n
 
(rec-n 5)
 
    Вход в функцию rec-n Аргументы: 5
      Вход в функцию rec-n Аргументы: 5 (0 1 1)
        Вход в функцию rec-n Аргументы: 5 (3 0 1 1)
          Вход в функцию rec-n Аргументы: 5 (63 3 0 1 1)
          Возврат из функции rec-n Результат: 513
        Возврат из функции rec-n Результат: 513
      Возврат из функции rec-n Результат: 513
    Возврат из функции rec-n Результат: 513
 
==> 513

@Nameless One · 08.10.2012, 12:56

Если улучшать производительность, то можно воспользоваться техникой мемоизации (описана у Норвига в PAIP):

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(defun memo (fn &key (test #'equal))
  (let ((table (make-hash-table :test test)))
    #'(lambda (&rest args)
        (multiple-value-bind (result found) (gethash args table)
          (if found
              result
              (setf (gethash args table)
                    (apply fn args)))))))
 
(defun memoize (fn &key (test #'equal))
  (setf (symbol-function fn)
        (memo (symbol-function fn) :test test)))
 
(defmacro defun-memoized (name args &body body)
  `(memoize (defun ,name ,args ,@body)))
 
(defun-memoized rec (x)
  (if (or (= x 0) (= x 1))
      1
      (+ (* 6 (rec (- x 1)))
         (* -9 (rec (- x 2)))
         (* (expt 3 (- x 2))
            (+ x 1)))))

@Catstail · 08.10.2012, 13:06

Спасибо, интересно!!!

@Nameless One · 08.10.2012, 13:12

Catstail, кстати, а зачем в твоем собирать в список все предыдущие результаты, если достаточно только знать последние два? Из-за этого твой вариант проигрывает наивной реализации.

@Catstail · 08.10.2012, 13:53

Сообщение от Nameless One

зачем в твоем собирать в список все предыдущие результаты

- согласен.

Сообщение от Nameless One

Из-за этого твой вариант проигрывает наивной реализации

- не согласен... В какой системе тестировал? Сейчас проверю в LispWorks.

Проверил... (rec 30) считается секунд 15-20, (rec-n 30) - молниеносно.

@Nameless One · 08.10.2012, 15:03

Тестировал в SBCL на Fedora 17:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
CL-USER> (progn (time (rec-naive 5000)) nil)
Evaluation took:
  0.040 seconds of real time
  0.038994 seconds of total run time (0.038994 user, 0.000000 system)
  97.50% CPU
  106,256,020 processor cycles
  21,873,072 bytes consed
  
NIL
CL-USER> (progn (time (rec-catstail 5000)) nil)
Evaluation took:
  0.154 seconds of real time
  0.152977 seconds of total run time (0.152977 user, 0.000000 system)
  99.35% CPU
  408,982,739 processor cycles
  21,115,344 bytes consed
  
NIL
CL-USER>

@Catstail · 08.10.2012, 16:37

Странно... Возможно, в SBCL какая-то оптимизация неявно выполняется. В LispWorks (и в HomeLisp) разница имеет другой знак и другой порядок. Попробую исключить лишнее накопление, посмотрю, что получится.

@ZzzDa · 08.10.2012, 16:45 **[ТС]**

Спасибо конечно, но вроде погорячился с созданием темы) Сам решил)

Lisp
1
2
3
4
5
6
(defun y(x)
(cond
((= x 0)1)
((= x 1)1)
(t(+(-(* 6 (y(- x 1)))(* 9 (y(- x 2))))(* (expt 3 (- x 2))(+ x 1))))
))

@Catstail · 08.10.2012, 17:07

Вот и славно...

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Programma_Boinc 01.01.2026 Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

@Catstail Супер-модератор 38163 / 21098 / 4306 Регистрация: 12.02.2012 Сообщений: 34,686 Записей в блоге: 14
	08.10.2012, 13:06
	Спасибо, интересно!!! 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	08.10.2012, 13:12
	Catstail, кстати, а зачем в твоем собирать в список все предыдущие результаты, если достаточно только знать последние два? Из-за этого твой вариант проигрывает наивной реализации. 0

@Catstail Супер-модератор 38163 / 21098 / 4306 Регистрация: 12.02.2012 Сообщений: 34,686 Записей в блоге: 14
	08.10.2012, 16:37
	Странно... Возможно, в SBCL какая-то оптимизация неявно выполняется. В LispWorks (и в HomeLisp) разница имеет другой знак и другой порядок. Попробую исключить лишнее накопление, посмотрю, что получится. 0

@Catstail Супер-модератор 38163 / 21098 / 4306 Регистрация: 12.02.2012 Сообщений: 34,686 Записей в блоге: 14
	08.10.2012, 17:07
	Вот и славно... 0