В Лисп реализовать функцию f (n)=5f (n−1)^3+4f (n−2)^2

@Юлия1111 · Регистрация: 19.02.2014

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

В Лисп реализовать функцию
f (n)=5f (n−1)^3+4f (n−2)^2 ,
f (1)=2,
f (2)=4
Сначала определите функцию так, чтобы порождался рекурсивный
процесс — реализация f1, а затем преобразуйте процедуру к
итерационному процессу — реализация f2. С помощью системной
функции time сравните вычислительную сложность f1 и f2 при n=10

@Taatshi · 19.02.2014, 01:59

Эта тема была перенесена из раздела О форуме и сайтах.

Перенес: Taatshi

@Catstail · 19.02.2014, 10:07

Совершенно аналогичная задача решена чуть ниже.

Добавлено через 19 минут
Вот два рекурсивных решения - "плохое" и "хорошее":

Lisp

;; Плохое (многократное перевычисление):
 
(defun f (n)
  (cond ((= n 1) 2)
        ((= n 2) 4)
        (t (let ((fn-1 (f (- n 1)))
                 (fn-2 (f (- n 2))))
                (+ (* 5 fn-1 fn-1 fn-1) (* 4 fn-2 fn-2))))))
 
;; хорошее
 
(defun ff (n &optional (c 4) (p 2))
  (cond ((= n 1) p)
        ((= n 2) c)
        (t (ff (- n 1) (+ (* 5 c c c) (* 4 p p)) c))))

Вот статистика вызова (HomeLisp):

Lisp

(f 5)
 
==> 34114102773320869165589504
 
*** Статистика обращений ***
LET ......................  4
+ ........................  4
* ........................  8
- ........................  8
F ........................  9
COND .....................  9
= ........................  16
 
(ff 5)
 
==> 34114102773320869165589504
 
*** Статистика обращений ***
- ........................  3
+ ........................  3
FF .......................  4
COND .....................  4
* ........................  6
= ........................  8

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

@helter · 19.02.2014, 15:49

Кстати, плохое решение не так уж плохо. В частности, ясность - его достоинство. А сделать эффективным его можно, кэшируя результаты. Вспомогательные функция и макрос из On Lisp:

Lisp

(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind (val win) (gethash args cache)
          (if win
              val
              (setf (gethash args cache) 
                    (apply fn args)))))))
(defmacro _f (op place &rest args)
  (multiple-value-bind (vars forms var set access) 
                       (get-setf-method place)
    `(let* (,@(mapcar #'list vars forms)
            (,(car var) (,op ,access ,@args)))
       ,set)))

Определив функцию f, пишем

Lisp

1	(_f memoize (symbol-function 'foo))

и функция f заменилась на свой кэширущий аналог.

@Catstail · 19.02.2014, 16:00

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

ясность - его достоинство

- это да...

@Юлия1111 0 / 0 / 0 Регистрация: 19.02.2014 Сообщений: 2
		1
	В Лисп реализовать функцию f (n)=5f (n−1)^3+4f (n−2)^2 19.02.2014, 01:48. Показов 1331. Ответов 4 Метки нет (Все метки) В Лисп реализовать функцию f (n)=5f (n−1)^3+4f (n−2)^2 , f (1)=2, f (2)=4 Сначала определите функцию так, чтобы порождался рекурсивный процесс — реализация f1, а затем преобразуйте процедуру к итерационному процессу — реализация f2. С помощью системной функции time сравните вычислительную сложность f1 и f2 при n=10 0

@Taatshi
	19.02.2014, 01:59 #2
	Эта тема была перенесена из раздела О форуме и сайтах. Перенес: Taatshi 0

@Catstail Модератор 36590 / 20320 / 4218 Регистрация: 12.02.2012 Сообщений: 33,621 Записей в блоге: 13
	19.02.2014, 16:00	5
	Сообщение от helter ясность - его достоинство - это да... 0

Опции темы

В Лисп реализовать функцию f (n)=5f (n−1)^3+4f (n−2)^2

Решение