Ä?wiczenia na deser

luty 10th, 2007 at 4:50 pm (scheme)

Synthroid Without Prescription Inderal No Prescription Nexium For Sale Prevacid Generic Buy Elimite Online Prevacid Without Prescription Ultram No Prescription Prevacid For Sale Ultram Generic Buy Prednisone Online

JednÄ? z zalet Lispa jest to, ??e jest niezniszczalny. Od jego powstania trzon jÄ?zyka pozostaje niezmienny; minimalistyczny, ale na tyle potÄ???ny, by inne jÄ?zyki programowania czerpa??y z niego a?? do teraz. Oznacza to r??wnie??, ??e mo??na zostawiÄ? Lispa na kilka miesiÄ?cy i po tym wr??ciÄ? do niego, majÄ?c pewno??Ä?, ??e zbyt wiele siÄ? nie zmieni??o. MuszÄ? przyznaÄ?, ??e pod wzglÄ?dem dydaktycznym jest to ogromna zaleta. Tym samym wracamy do ko??c??wki pierwszego rozdzia??u Wizard Booka.

Lisp machine W miarÄ? jak autorzy przedstawiajÄ? procedury wy??szego rzÄ?du mo??na zrozumieÄ?, ??e procedura jest czym?? wiÄ?cej, ni?? kto?? wychowany na C/C++/Javie m??g??by podejrzewaÄ?. Nie jest to bowiem zwyk??y kawa??ek kodu, kontener dla ciÄ?gu instrukcji, kt??re mamy zamiar wiele razy wywo??aÄ?. Procedura nie przedstawia tylko oblicze?? wykonywanych na liczbach i strukturach - jest raczej formalnym sposobem zapisu metody postÄ?powania, kt??ra sama w sobie mo??e korzystaÄ? nie tylko z liczbowych argument??w, ale i z innych metod. Ukazuje to wyra??nie stopnie abstrakcji, po kt??rych mo??emy siÄ? wspinaÄ?, definiujÄ?c kolejne procedury na szczycie innych procedur. Szybko odrywamy siÄ? od pojÄ?cia funkcji operujÄ?cej na liczbach na rzecz og??lniejszej metody, sposobu postÄ?powania, algorytmu, kt??ry mo??emy zapisaÄ? w postaci kodu.

Wykorzystajmy tÄ? wiedzÄ? w praktyce. Poni??ej rozwiÄ?zanie kilku Ä?wicze?? rozdzia??u pierwszego.

Ä?wiczenie 1.16

W zadaniu tym nale??y przekszta??ciÄ? podanÄ? wcze??niej definicjÄ? procedury potÄ?gowania z formy generujÄ?cej proces rekurencyjny na proces iteracyjny. DziÄ?ki wskaz??wce zadanie to jest ca??kiem proste. Dla parzystych n liczbÄ? b podnosimy do kwadratu, za?? dla n nieparzystych a mno??ymy przez b, zachowujÄ?c w ten spos??b sta??Ä? warto??Ä? wyra??enia a*b^n. Poni??ej pe??ne rozwiÄ?zanie: 
(define (fast-expt a b n)
  (cond ((= n 0) a)
        ((even? n) (fast-expt a (square b) (/ n 2)))
        (else (fast-expt (* a b) b (- n 1)))))

Ä?wiczenie 1.17

Tutaj autorzy proszÄ? nas o zdefiniowanie operacji mno??enia korzystajÄ?cÄ? jedynie z dodawania, ale w taki spos??b, by procedura wykonywa??a logarytmicznÄ? liczbÄ? krok??w ze wzglÄ?du na argumenty a i b. Logarytmiczna liczba krok??w w stosunku do argumentu oznacza, ??e przy dwukrotnym (lub w og??lno??ci n-krotnym) wzro??cie argumentu liczba krok??w zwiÄ?ksza siÄ? o jeden. W rozwiÄ?zaniu wykorzystaÄ? mamy dwie pomocnicze funkcje double i halve, kt??re odpowiednio podwajajÄ? i dzielÄ? na dwa swoje argumenty: 
(define (double n) (+ n n))
 
(define (halve n) (/ n 2))
 RozwiÄ?zanie: 
(define (fast-mul a b)
  (cond ((= b 0) 0)
        ((even? b) (double (fast-mul a (halve b))))
        (else (+ a (fast-mul a (-  b 1))))))

Ä?wiczenie 1.30

W tym Ä?wiczeniu wystarczy uzupe??niÄ? kod. MajÄ?c ju?? za sobÄ? pewne do??wiadczenie w przekszta??caniu procesu rekurencyjnego w iteracyjny, znalezienie prawid??owego rozwiÄ?zania nie jest ??adnym wyzwaniem: 
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (iter a 0))

Ä?wiczenie 1.31

Nale??y zdefiniowaÄ? podobnÄ? do sum procedurÄ? product, kt??ra zwraca iloczyn warto??ci funkcji w punktach zadanego zakresu. Oto wersja rekurencyjna: 
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))
 A to wersja iteracyjna: 
(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a)
              (* (term a) result))))
  (iter a 1))
 Na podstawie product definicja silni jest trywialna: 
(define (identity x) x)
(define (inc n) (+ n 1))
 
(define (factorial n)
  (product identity 1 inc n))
 R??wnie ??atwo jest zapisaÄ? funkcjÄ? liczÄ?cÄ? przybli??enie liczby ?? na podstawie wzoru Johna Wallisa: 
(define (pi-wallis n)
  (define (pi-term n)
    (/ (square (* 2 n))
       (* (+ (* 2 n) 1)
          (- (* 2 n) 1))))
  (* (product pi-term 1 inc n) 2.0))
 Przy dziesiÄ?ciu tysiÄ?cach krok??w funkcja ta przybli??a ?? do czterech miejsc po przecinku, co nie jest wynikiem zbyt imponujÄ?cym: 
> (pi-wallis 10000)
3.141514118681922

Podsumowanie rozdzia??u pierwszego

Wpisem tym chcia??bym zako??czyÄ? i podsumowaÄ? pierwszy rozdzia?? Wizard Booka, zatytu??owany “Budowanie abstrakcji za pomocÄ? procedur”. Materia?? tego rozdzia??u zosta?? om??wiony na wyk??adach wideo o numerach 1a, 1b i 2a. Poni??ej lista pojÄ?Ä?, kt??re uda??o nam siÄ? poznaÄ?:
  • In??ynieria oprogramowania r????ni siÄ? od innych dziedzin in??ynierii tym, ??e najwiÄ?kszym ograniczeniem nie sÄ? prawa fizyki, ale nasze w??asne umys??y. Innymi s??owy, zbudowaÄ? mo??emy wszystko to, co jeste??my w stanie sobie wyobraziÄ?.
  • Abstrakcja jest sposobem na radzenie sobie ze z??o??ono??ciÄ? du??ych system??w. Zamykanie funkcjonalno??ci w “czarnych skrzynkach” pozwala nam skupiÄ? siÄ? na problemie, pomijajÄ?c nieistotne szczeg????y.
  • Procedury generujÄ? (czy te?? opisujÄ?) procesy. Procesy podczas wykonania mogÄ? rozwijaÄ? siÄ? na r????ne sposoby - “kszta??t” procesu iteracyjnego jest inny ni?? “kszta??t” procesu rekurencyjnego.
  • Procedury reprezentujÄ? og??lne metody oblicze??, mogÄ? wiÄ?c przyjmowaÄ? inne procedury jako argumenty i zwracaÄ? procedurÄ? jako wynik.
Pr??cz tych og??lnych zagadnie?? poznali??my kawa??ek jÄ?zyka Scheme: W moich wpisach pojawi??y siÄ? r??wnie?? elementy wykraczajÄ?ce poza pierwszy rozdzia?? Wizard Booka, a mianowicie: Tym samym ostatecznie ??egnamy siÄ? z rozdzia??em pierwszym i przechodzimy do rozdzia??u drugiego, gdzie zajmiemy siÄ? budowaniem struktur danych.

Komentuj wpis