Найдите «краткое математическое определение» функции в SICP - PullRequest
Новая
       19

Найдите «краткое математическое определение» функции в SICP

2 голосов
/ 02 мая 2019

Структура и интерпретация компьютерных программ дает эту реализацию функции Аккерманна: 

(define (A x y) 
  (cond ((= y 0) 0)
      ((= x 0) (* 2 y))
      ((= y 1) 2)
      (else (A (- x 1) (A x (- y 1))))))

В упражнении 1.10 запрашиваются "краткие математические определения" следующих функций, которые вызывают A: 

(define (f n) (A 0 n)) 
(define (g n) (A 1 n)) 
(define (h n) (A 2 n))

Выходы f и g для целых чисел 1 - 4 распознаются как 2n и 2 ^ n.Но h - это 2^(2^n-1), формула, которую я не мог распознать, просто посмотрев шаблон в выходных данных.Как можно завершить это упражнение?Есть ли способ получения математической записи, возможно, основанный на записи для функции Аккермана?

Ответы [ 3 ]

2 голосов
/ 02 мая 2019

Вы можете использовать саму схему, чтобы помочь найти ответы на следующие вопросы: 

(define (*^ x y) `(* ,x ,y))

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (*^ 2 y))
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

;> (A 0 100)
;'(* 2 100)
;> (A 0 234)
;'(* 2 234)

предлагает (A 0 n) = (* 2 n). 

(define (*^ x y) `(* ,x ,y))

(define (A x y)
  (cond ((= x 0) (*^ 2 y))
        ((= y 0) 0)
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

;> (A 1 10)
;'(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 2)))))))))
;> (A 1 5)
;'(* 2 (* 2 (* 2 (* 2 2))))

переупорядочил правила, чтобы избежать ошибки. мы можем видеть, что он делает * 2 n раз, так что 2 ^ n. 

(define (*^ x y) `(* ,x ,y))

(define (A x y)
  (cond ((= x 0) (*^ 2 y))
        ((= x 1) `(expt 2 ,y))
        ((= y 0) 0)
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

;> (A 2 5)
;'(expt 2 (expt 2 (expt 2 (expt 2 2))))
;> (A 2 6)
;'(expt 2 (expt 2 (expt 2 (expt 2 (expt 2 2)))))

Это подтверждает идею, что мы получаем башню экспонентов.

2 голосов
/ 03 мая 2019

В книге уже введен метод подстановки, поэтому его использование не является неправильным.

Начните с (A 0 n)

Это 

(cond ((= n 0) 0)
      ((= 0 0) (* 2 n))
      ((= 0 1) 2)
      (else (A (- 0 1) (A 0 (- n 1)))))

, чтоясно 2n.

Далее (A 1 n) равно 

(cond ((= n 0) 0)
      ((= 1 0) (* 2 n))
      ((= n 1) 2)
      (else (A (- 1 1) (A 1 (- n 1))))))

, что составляет 

(A 0 (A 1 (- n 1)))

или, используя преимущество предыдущего шага, 

(* 2 (A 1 (- n 1))

То есть 

A 1 n = 2 * (A 1 (n-1))
      = 2 * 2 * (A 1 (n-2))
      = ...

Поскольку мы знаем, что A x 1 = 2 для всех x, мы видим, что 

A 1 n = 2 * 2 * ... * 2

с n факторами, т.е. 2 n .

Применение аналогичных рассуждений к последнему делу, оставленному в качестве упражнения.

2 голосов
/ 02 мая 2019

Уже выяснив, что (fn) = (* 2 n) и (gn) = (expt 2 n) мы можем использовать эту информацию вместе с определением A, чтобы выяснить, что (A 2 n) будет:

Ввод x = 2: 

(define (A2 y) 
  (cond ((= y 0) 0)
        ((= y 1) 2)
        (else (A 1 (A2 (- y 1))))))

Ввод факта (A 1 n) = (expt 2 n) 

(define (A2 y) 
  (cond ((= y 0) 0)
        ((= y 1) 2)
        (else (expt 2 (A2 (- y 1))))))

из этого вы можете видетьшаблон рекурсии более ясно, что A2 дает вложенные полномочия двух, как 2 ^ (2 ^ (2 ^ 2)).Я думаю, что ваш ответ 2 ^ (2 ^ n-1) может быть неправильным.

...