Poza nawiasem

Ä?wiczenie 1.11

Ä?wiczenie proste, biorÄ?c pod uwagÄ? to, co opisywa??em wcze??niej. Nale??y funkcjÄ? f(n) zapisaÄ? jako procedurÄ? obliczajÄ?cÄ? warto??ci za pomocÄ? procesu iteracyjnego i rekurencyjnego. Definicja funkcji jest nastÄ?pujÄ?ca:

Wersja rekurencyjna:

(define (f n)
  (cond ((< n 3) n)
        (else (+ (f (- n 1))
                 (* 2 (f (- n 2)))
                 (* 3 (f (- n 3)))))))

Wersja iteracyjna:

(define (f n)
  (define (f-iter a b c count)
    (cond ((= count 2) c)
          (else (f-iter b c (+ c (* 2 b) (* 3 a)) (- count 1)))))
  (cond ((< n 3) n)
        (else (f-iter 0 1 2 n))))

Ä?wiczenie 1.12

Zadanie polega na napisaniu procedury obliczajÄ?cej elementy tr??jkÄ?ta Pascala. Nie sprecyzowano czy funkcja ma zwracaÄ? pojedyncze elementy, czy ca??e tr??jkÄ?ty, stworzy??em wiÄ?c trzy funkcje: pascal-number oblicza warto??Ä? n-tej liczby w podanym wierszu tr??jkÄ?ta Pascala, pascal-row oblicza ca??y n-ty wiersz (zwracajÄ?c listÄ? liczb), za?? pascal-triangle oblicza ca??y tr??jkÄ?t o zadanej wysoko??ci (zwracajÄ?c listÄ? wierszy).

(define (pascal-number r n)
  (if (or (= n 1)
          (= n r))
      1
      (+ (pascal-number (- r 1) (- n 1))
         (pascal-number (- r 1) n))))
 
(define (make-list-by-iterate iters-num function)
  (define (iter i)
    (if (> i iters-num)
        ()
        (cons (function i)
              (iter (+ i 1)))))
  (iter 1))
 
(define (pascal-row n)
  (make-list-by-iterate n
                        (lambda (x) (pascal-number n x))))
 
(define (pascal-triangle n)
  (make-list-by-iterate n
                        (lambda (x) (pascal-row x))))

Warto zwr??ciÄ? uwagÄ? na funkcjÄ? pomocniczÄ? make-list-by-iterate, kt??ra buduje listÄ? z warto??ci zwracanych podanej funkcji wywo??ywanej kolejno z argumentem od 1 do iters-num. Budowanie n-tego wiersza (pascal-row) jest niczym wiÄ?cej jak wywo??aniem pascal-number n razy. Budowanie tr??jkÄ?ta Pascala o wysoko??ci n (pascal-triangle) polega za?? na stworzeniu kolejnych jego wierszy, od pierwszego a?? do n-tego.

Ä?wiczenie 1.13

Obecno??Ä? tego Ä?wiczenia wybitnie ??wiadczy o tym, ??e Wizard Book jest ksiÄ???kÄ? pomocnÄ? w nauczaniu Informatyki, a nie zwyk??ym podrÄ?cznikiem do programowania. Autorzy proszÄ? nas bowiem o przeprowadzenie matematycznego dowodu.

Udowodnij, ??e Fib(n) jest liczbÄ? ca??kowitÄ? najbli??szÄ? , gdzie .
Wskaz??wka: Niech . KorzystajÄ?c z definicji liczb Fibonacciego, udowodnij przez indukcjÄ?, ??e Fib(n) = .

DziÄ?ki wskaz??wce rozwiÄ?zanie jest do??Ä? proste. Zanim przejdziemy do dowodu, przypomnijmy sobie definicjÄ? ciÄ?gu Fibonacciego i w??asno??ci liczby phi i psi.

Mo??emy ju?? przej??Ä? do pierwszego kroku indukcyjnego. Sprawdzamy, czy teza zachodzi dla n r??wnego zero i jeden.

Wyniki sÄ? poprawne, wiÄ?c przechodzimy do kroku drugiego. Za??o??enie (dla n>0):

Teza:

Dow??d:

Skoro wiemy ju?? ile r??wne jest Fib(n), to by udowodniÄ?, ??e jest ona najbli??szÄ? liczbÄ? ca??kowitÄ? dla , nale??y dowie??Ä? nier??wno??ci:

Ta oczywi??cie upraszcza siÄ? do postaci:

Lewa czÄ???Ä? wyra??enia dÄ???y do zera zaczynajÄ?c od 0.447 dla n r??wnego zero, nier??wno??Ä? jest wiÄ?c zawsze spe??niona. Formalnie nale??a??oby jeszcze zapisaÄ? na to dow??d, jest on jednak trywialny, a mi ju?? znudzi??o siÄ? wklepywanie tych wzor??w. ;-) W ten oto spos??b rozwiÄ?zali??my Ä?wiczenie 1.13.