Скрипт вычисляет значения функции Аккермана, используя кэширование. Кэш вначале инициализируется, а потом происходит выполнение (ниже код).
Скрипт:
;; кэш для функции Аккермана
(defvar *akk-cache* nil)
;; счетчик рекурсивных вызовов (должен быть обнулен перед вызовом функции akk или akk-cache)
(defvar *akk-recursive-calls-counter* 0)
(defun print-akk-cache ()
(print *akk-cache*))
(defun print-akk-calls-counter ()
(format t "~a~%" *akk-recursive-calls-counter*))
;; эта функция инициализирует кэш указанным размером
(defun init-akk-cache (m n)
(setf *akk-cache* nil)
(setf *akk-cache* (make-list m))
(let ((cache-row (make-list n :initial-element 0)))
(dotimes (i m)
(setf (nth i *akk-cache*) (copy-list cache-row))))
(return-from init-akk-cache t))
;; установка значения в кэше
(defun set-akk-cache-value (m n value)
(setf (nth n (nth m *akk-cache*)) value)
(return-from set-akk-cache-value t))
;; получение значения из кэша
(defun get-akk-cache-value (m n)
(if (or (> m (length *akk-cache*)) (> n (length (nth 0 *akk-cache*))))
(format t "FUCK!~%"))
(let ((result (nth n (nth m *akk-cache*))))
(return-from get-akk-cache-value result)))
;; функция Аккермана без использования кэширования
(defun akk (m n)
(incf *akk-recursive-calls-counter*)
(cond ((= m 0) (+ n 1))
((= n 0) (akk (- m 1) 1))
(t (akk (- m 1) (akk m (- n 1))))))
;; функция Аккермана с использованием кэширования
(defun akk-cache (m n)
(incf *akk-recursive-calls-counter*)
(if (/= (get-akk-cache-value m n) 0)
(return-from akk-cache (get-akk-cache-value m n))
(let ((value (cond ((= m 0) (+ n 1))
((= n 0) (akk-cache (- m 1) 1))
(t (akk-cache (- m 1) (akk-cache m (- n 1)))))))
(set-akk-cache-value m n value)
(return-from akk-cache value))))
;;
(defun akk-with-calls-counting ()
(loop for m from 0 to 3 do
(loop for n from 0 to 14 do
(setf *akk-recursive-calls-counter* 0)
(format t "(~2a ~2a) ~12a [~a]~%" m n (akk m n) *akk-recursive-calls-counter*))))
(defun akk-cache-with-calls-counting ()
(loop for m from 0 to 3 do
(loop for n from 0 to 14 do
(setf *akk-recursive-calls-counter* 0)
(format t "(~2a ~2a) ~12a [~a]~%" m n (akk-cache m n) *akk-recursive-calls-counter*))))
Я работаю в Emacs/Inferior Lisp, поэтому привожу коды для запуска:
(init-akk-cache 10 1000000)
(akk-cache-with-calls-counting)
Я дошел до (3 14), дальше у меня шло переполнение стека (я 4 * не считал). Если возможно, посчитайте, пожалуйста, например, не от 0 до 3 и от 0 до 14, как сейчас, а от 0 до 5 и от 0 до 20, например. Если будет переполнение стека, то нужно увеличить размер кэша, например, на 10х10000000 и так далее.
Мой компьютер не позволяет мне такое сделать, буду очень благодарен, если поможете.
