Matematycznie

May 13th, 2006 at 12:13 am (scheme, algorytmy)

Dzisiaj same konkrety - rozwiązania dla ćwiczeń kończących rozdział 1.2.2.

Ć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:

f(n)=n dla n<3 i f(n) = f(n-1)+2f(n-2)+3f(n-3) dla n>=3

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ą (phi^n)/sqrt(5), gdzie phi = (1 + sqrt(5))/2.
Wskazówka: Niech psi = (1 - sqrt(5))/2. Korzystając z definicji liczb Fibonacciego, udowodnij przez indukcję, że Fib(n) = (phi^n - psi^n)/sqrt(5).

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.

Fib(n) = Fib(n-1) + Fib(n-2)
phi^2 = phi + 1
psi^2 = psi + 1

Możemy już przejść do pierwszego kroku indukcyjnego. Sprawdzamy, czy teza zachodzi dla n równego zero i jeden.

Fib(0)

Fib(1)

Wyniki są poprawne, więc przechodzimy do kroku drugiego. Założenie (dla n>0):

Fib(n-1)=(phi^(n-1) - psi^(n-1))/sqrt(5)
Fib(n)=(phi^n - psi^n)/sqrt(5)

Teza:

Fib(n)=(phi^(n+1) - psi^(n+1))/sqrt(5)

Dowód:

Fib(n+1)=Fib(n)+Fib(n-1)
(phi^n - psi^n)/sqrt(5) + (phi^(n-1) - psi^(n-1))/sqrt(5)
(phi^n + phi^(n-1) - psi^n - psi^(n-1))/sqrt(5)
((phi^(n-1))(phi+1) - (psi^(n-1))(psi+1))/sqrt(5)
(phi^(n+1) - psi^(n+1))/sqrt(5)

Skoro wiemy już ile równe jest Fib(n), to by udowodnić, że jest ona najbliższą liczbą całkowitą dla (phi^n)/sqrt(5), należy dowieść nierówności:

|Fib(n)-(phi^n/sqrt(5))| <= 1/2

Ta oczywiście upraszcza się do postaci:

|(phi^n - psi^n)/sqrt(5) - (phi^n/sqrt(5))| <= 1/2
|(- psi^n)/sqrt(5)| <= 1/2

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.

Komentuj wpis