Каков реальный ответ на SICP 3.57? - PullRequest
Новая
       97

Каков реальный ответ на SICP 3.57?

6 голосов
/ 23 сентября 2019

SICP Упражнение 3.57: Сколько сложений выполняется, когда мы вычисляем n-е число Фибоначчи, используя определение fib, основанное на процедуре add-streams?Покажите, что количество добавлений было бы экспоненциально больше, если бы мы реализовали (задержка «exp») просто как (lambda () «exp»), без использования оптимизации, предусмотренной процедурой memo-proc, описанной в 3.5.1.

Есть много решений онлайн.Большинство утверждают, что неоптимизированная версия memo-proc-последовательности FIB-последовательности такая же, как вычисление незапамятной регулярной FIB-функции.При отслеживании дополнений для неоптимизированной версии memo-proc я вижу другую историю.

Пусть A (n) будет количеством дополнений, выполненных для (stream-ref fibs n)

  • A (0) = 0
  • A (1) = 0
  • A (2) = 1
  • A (3) = 3
  • A (4) = 7
  • A (5) = 14
  • A (6) = 26

При использовании подстановки и определения функций для не-оптимизированный (незапамятный поток) я могу точно видеть, что это за добавления и почему они происходят, но у меня возникают проблемы с придуманием хорошего уравнения, чтобы ответить на вопрос, что оно на самом деле экспоненциально.

Добавлениянапример, для A (4):

  • 1 + 0
  • 1 + 0
  • 1 + 1
  • 1 +0
  • 1 + 1
  • 1 + 0
  • 2 + 1

Вот некоторый псевдокод для отображения замен (stream-refвыдумки 4), где '.'представляет infix stream-cons, а {e} представляет обещание выполнить e. 

(cddddr fibs)
(cddr (add-streams (cdr fibs) fibs))
(cddr (stream-map + (cdr fibs) fibs)))
(cddr ((+ 1 0) . {stream-map + (cddr fibs) (cdr fibs)}))
(cdr (stream-map + (cddr fibs) (cdr fibs)))
(cdr (stream-map + ((+ 1 0) . {stream-map + (cddr fibs (cdr fibs)}) (cdr fibs))
(cdr (+ 1 1) . {stream-map + (stream-map + (cddr fibs) (cdr fibs)) (cddr fibs)})
(stream-map + (stream-map + (cddr fibs) (cdr fibs)) (cddr fibs))
(stream-map + (stream-map + ((+ 1 0) . {stream-map + (cddr fibs) (cdr fibs)}) (cdr fibs)) (cddr fibs)
(stream-map + (stream-map + ((+ 1 0) . {stream-map + (cddr fibs) (cdr fibs)}) (1 . {stream-map + (cdr fibs) fibs)})) (cddr fibs))
(stream-map + ((+ 1 1) . {stream-map + (stream-map + (cddr fibs) (cdr fibs)) (stream-map + (cdr fibs) fibs)}) ((+ 1 0) . {stream-map + (cddr fibs) (cdr fibs)})
(+ 2 1) . {stream-map + (stream-map + (stream-map + (cddr fibs) (cdr fibs)) (stream-map + (cdr fibs) fibs))) (stream-map + (cddr fibs) (cdr fibs))}

Вот фактический код ракетки: 

#lang racket
(define-syntax-rule (delay f) (lambda () f))
(define (force f) (f))

(define stream-null? null?)
(define the-empty-stream '())

(define-syntax-rule (cons-stream a b)
  (cons a (delay b)))
(define stream-car car)
(define (stream-cdr stream) (force (cdr stream)))

(define (add-streams s1 s2)
  (define (add x y)
    (begin
      (display "Adding ")
      (display x)
      (display " + ")
      (display y)
      (newline)
      (+ x y)))
  (stream-map add s1 s2))

(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc 
                    (map stream-cdr 
                         argstreams))))))

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define fibs 
  (cons-stream 
   0 (cons-stream
      1 (add-streams 
         (stream-cdr fibs) fibs))))

(stream-ref fibs 4)

Большинство ответов онлайн говорят что-то вроде a (n)= a (n - 1) + a (n - 2) + 1 Отслеживаемый вывод рассказывает другую историю

1 Ответ

2 голосов
/ 26 сентября 2019

Фактический ответ (мне потребовалось некоторое время, чтобы разобраться с картинками потоков, чтобы разобраться с этим), что вы можете выразить количество дополнений как:

a (n) =

  • 0, если n = 0 или 1
  • , иначе n - 1 + a (n - 1) + a (n - 2)

Здесь термин n - 1происходит от сложений, которые необходимо выполнить при сложении двух потоков, а затем два других термина - это дополнения, которые необходимо выполнить по очереди.Обратите внимание, что это хуже, чем простой рекурсивный случай.

Вы можете проверить, что это правильно, выполнив эту хакерскую вещь: 

(define/contract (fib-count m)
  (-> natural-number/c natural-number/c)
  (define count 0)
  (define fibs (cons-stream
                0
                (cons-stream
                 1
                 (stream-map (λ (a b)
                               (set! count (+ count 1))
                               (+ a b))
                             (stream-cdr fibs) fibs))))
  (stream-ref fibs m)
  count)

(define/contract (add-count n)
  (-> natural-number/c natural-number/c)
  (define (a m)
    (case m
      [(0 1) 0]
      [else (+ (- m 1)
               (a (- m 1))
               (a (- m 2)))]))
  (a n))
...