Zadania (Scheme)

  1. Jakie są wartości następujących wyrażeń?

    ==> 10 

    ==> (+ 5 3 4)

    ==> (- 9 1)

    ==> (/ 6 2)

    ==> (+ ( * 2 4) (- 4 6))

    ==> (let ((a 1) (b 2)) (+ a b (* a b)))

    ==> a

    ==> (define a 3)

    ==> (define b (+ a 1))

    ==> (+ a b (* a b))

    ==> (= a b)

    ==> (if (and (> b a) (< b (* a b))) b a)

    ==> (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25))
  2. Proszę napisać funkcje nwd a b oraz nww a b, których wartościami są największy wspólny dzielnik i najmniejsza wspólna wielokrotność.

  3. Proszę napisać funkcję (new.< x y), (new.> x y), (new.= x y), (new.<= x y), (new.>= x y) oraz (new.<> x y). Należy z wbudowanych funkcji używać wyłącznie funckcję < (oraz predykaty oczywiście).

  4. Proszę napisać funkcję (same-values? p1 p2 x y), której wartość jest #t, jeżeli (p1 x y) i (p2 x y) mają tą samą wartość i #f w przecziwnym przypadku.
    Przykłady: ==> (same-values? = new.= 3 1)
               #t
               ==> (same-values? < > 2 3)
               #f
    
  5. Proszę napisać funkcje (odd? n) oraz (even? n), które sprawdzają, czy liczba naturalna n jest nieparzysta albo parzysta. Należy używać wyłącznie funkcje #t, #f, zero? oraz "-1".

  6. Proszę napisać rekurencyjną oraz iteracyną funkcję (fib n), która obliczy n-tą liczbę Fibonacci.

  7. Proszę napisać funkcję (call f x), której wartość jest zastosowanie funkcji f z argumentem x.
    Przykłady: ==> (call square 5)
               25
               ==> (call odd? 8)
               #f
               ==> (call fib 3)
               8
    
    Jaką ma wartość wyrażenie (call 5 7)?

  8. Potęgowanie b^e można szybko wykonać używając b^e = (b^(e/2))^2. Proszę napisać rekurencyjną oraz iteracyjną funkcję (exp b e) na podstawie tej właściwości. Używając model środowiska, proszę pokazać, jak wyrażenie (exp 2 6) zostaje ewaluowane.

  9. Proszę napisać funkcję (sum-of-squares-of-maxima a b c), której wartość jest sumą kwadratów dwóch większych argumentów.
    Używając model środowiska, proszę pokazać jak wyrażenie (sum-of-squares-of-maxima 5 7 6) zostaje ewaluowane.

  10. Dlaczego wyrażenie if nie można sam definiować w następujący sposób?
    (define (new-if warunek alternatywa1 alternatywa2)
       (cond (warunek alternatywa1)
             (else    alternatywa2)))
    
  11. Proszę napisać funkcję (product term a next b) analogicznie do funkcji sum z wykładu. Proszę pokazywać, jak używając product można definiować funkcję silnia oraz przybliżać p na podstawie formuły   p/4 = 2 · 4 · 4 · 6 · 6 · 8 ··· / 3 · 3 · 5 · 5 · 7 · 7 ··· .

  12. Proszę napisać funkcję (accumulate combiner null-value term a next b), która jest uogólnieniem funkcji sum i prod. Argumenty term, next, a i b zachowują to same znaczenie niż w funkcjach sum i prod. combiner jest dwuargumentową funkcją, która opisuje, jak (term a) zostaje dodane do akkumulacji dalszych termów. null-value jest wartością inicjalną do używania w końcowym przypadku.
    Proszę pokazywać, jak można definiować funkcje sum i prod używając accumulate.

  13. Nawet funkcję accumulate można dalej uogólnić. Proszę napisać funkcję filter-accumulate, która ma dodatkowy argument pred. pred jest (jednoargumentowym) predykatem a filter-accumulate dodaje (term a) do wynika tylko, jeżeli a spełnie predykat pred.
    Używając filter-accumulate proszę obliczyć sumę kwadratów liczb pierwszych w interwale [a,b] oraz produkt wszystkich liczb naturalnych i mniejsze niż n, takie że nwd(i,n) = 1.

  14. Niech będzie dana następująca definicja funkcji comb.
    (define (comb f g)
       (lambda (x) (f (g x))))
    
    Używając model środowiska, proszę pokazywać jak wyrażenie ((comb square double) 5) zostajy ewaluowane.

  15. Proszę napisać funkcję (deriv f dx), którą wartość jest funkcją, która przybliża funkcję f' używając formułę
     Df(x) = (f(x+dx) - f(x)) / dx.
    
    Przykład:  ==> ((derive cube .001) 5)
               75.015
    
  16. Proszę zdefiniować funkcję (iter f n), której wartością jest funkcja fn.

  17. Proszę napisać następujące funkcje dla list:

    a) (append l m), która konkatenuje listy l i m.

    b) (reverse l), która obróci listę l.

    c) (last l), która znajduje ostatni element w liscie l.

    d) (delete x l), która skasuje element x z listy l.

  18. a) Proszę napisać funkcję (square-list l), której wartość jest listą kwadratów elementów listy l.

    b) Proszę napisać funkcję (mapf f l), której wartością jest lista wartości f(e) dla wszystkich elementów e w liscie l.

    c) Proszę napisać funkcję (filter pred l), której wartością jest lista wszystkich elementów w liscie l, które spełniają predykat pred.

  19. Proszę napisać funkcję (ewal wyrażenie wartości), która oblicy wynik dla wyrażeń boolowskich. wyrażenie jest listą, której pierwszym elementem jest "typ" wyrażenia, a następne
    elementy tej listy, to podwyrażenia; na przykład lista '(and x (not y)) reprezentuje wyrażenie x∧¬y. wartości jest listą, w której znadują się wartości zmiennych.
    Przykłady: ==> (define w '((x . #f) (y . #t) (z . #f)))
               w
               ==> (ewal '(and y (not x)) w)
               #t
               ==> (ewal '(and y (and (not x) z))) w)
               #f
               ==> (ewal '(and y 1) w)
               #t
    
  20. a) Proszę uzupełnić funkcję derive z wykładu.

    b) Proszę poszerzać funkcję derive tak, żeby też mogła traktować termy typu u^n (na podstawie d(u^n) / dx = n * u^(n-1) * du / dx ).

  21. Proszę zdefiniować arytmetykę liczb wymiernich na podstawie liczb całkowitych.

  22. Niech będą dane następujące definicje funkcji.
    (define m 1)             (define n 1)
    (define (p m)            (define (q n)
       (pp 5))                  (define (qq x)
    (define (pp x)                 (+ x n))
       (+ x m))                 (qq 5))
    
    Jakie są wartości wyrazień (p 11) i (q 11)? Proszę wytłumaczyć wyniki używając model środowiska.

  23. Proszę napisać funkcję (member2 x l), któ sprawdza, czy gdzieś w liscie l znajduje się x.
    Przykłady: ==> (member2 'a '(b (c a) b))
               #t
               ==> (member2 '(a) '(b (c (a) d) e))
               #t
               ==> (member2 '(a) '(b c a))
               #f
    
  24. a) Proszę napisać funkcje (intersection s1 s2) oraz (union s1 s2) dla zbiorów s1 i s2.

    b) Jak można ulepszyć funkcje, jeżeli zbiory są posortowane?

  25. Proszę uzupełnić arytmetykę liczb zespolonych z wykładu.

    a) używając metodę "manifest types".

    b) używając metodę "message passing".

    c) Niech będą dane następujące definicje
       (define z1 (make-rectangular -1 3)) 
       (define z2 (make-polar 2 -2)) 
    
    Proszę wytłumaczyć ewaluację wyrażenia (angle (+c z1 z2)) używając model środowiska.

  26. W Scheme też można pisać funkcje z dowolną ilością argumentów:
     (define (f x y z . l) (...))
    
    oznacza, że funkcja f ma conajmniej trzy argumenty (x,y i z). Jeżeli f dostaje więcej niż trzy argumenty, dodatkowe argumenty zostają zapisane do listy l .

    a) Proszę napisać funkcję plus, która podsumuje dowolną ilość liczb.

    b) Proszę napisać funkcję par dla dowolniej ilości (jednoargumentowych) funkcji fi. Wartość funkcji par jest (jednoargumentową) funkcją, która dla argumenta x obliczy listę wszystkich
        wartości fi(x).
      Przykłady: ==> ((par id square cube) 3)
                 (3 9 27) 
                 ==> ((par double double) 5)
                 (10 10)
    
  27. a) Proszę napisać funkcję (make-konto balance), która generuje nowe konto z balance złotymi. Na koncie mają być możliwie następujące operacje: Podjęcie, wpłacenie oraz
        informacje, ile jest na koncie.

    b) Proszę modifykować funkcję make-konto z cięci a), taka że ona generuje konta z hasłami, tzn. operacje zostają wykonywane tylko, jeżeli użytkownik używa prawdziwe hasło.
     Przykład: ==> (define konto (make-konto 100 'hasło))
               konto
               ==> ((konto 'hasło 'withdraw) 40)
               60
               ==> ((konto 'inne-hasło 'withdraw) 20)
               złe hasło
    
  28. Proszę napisać destruktywną wersję append! funkcji append. Jakie są wartości następujących wyrażeń?
    ==> (define x '(a b)) 
    ==> (define y '(c d))
    ==> (append x y)
    ==> (cdr x)
    ==> (append! x y)
    ==> (mcdr x)
  29. a) Niech zostają zaewaluowane następujące wyrażenia.
    ==> (define x (mcons 'a (mcons 'b '())))
    ==> (define z1 (mcons x x))
    ==> (define z2 (mcons (mcons 'a (mcons 'b '()))
                          (mcons (mcons 'a (mcons 'b '())) '())))
    ==> (set-mcar! (mcar z1) 'g)
    ==> (set-mcar! (mcar z2) 'g) 
    
    Jakie wartości mają z1 oraz t2?

    b) Proszę napisać funkcję (mlist l), która transformuje listę l do detruktywnej listy.

  30. Proszę uzupełnić definicję kolejek z wykładu.

  31. Proszę napisać funkcję (counting-version f), która ma jedonargumentową funkcję f jako argument. Wartość tej funkcji jest nową jednoargumentową funkcję, która liczy, ile razy
    funkcja f została używana.
     Przykład: ==> (define sq (counting-version square))
               sq
               ==> (sq 5)
               25
               ==> (sq 7)
               49
               ==> (sq 'ile)
               2
               ==> (sq 'reset)
               0
               ==> (sq 'ile)
               0
    
  32. Na wykładzie został podyskutowany simulator układów logicznych.

    a) Proszę napisać funkcję (or-gate o1 o2 output), która generuje bramkę or.

    b) Proszę napisać funkcję (full-adder a b c-in sum c-out), która generuje (pełny) sumator.

    c) Ripple-carry-adder, to układ, który sumuje dwie liczbe binarne an ... a1 i bn ... b1. Wynik sumacji, to n bitów sn ... s1 oraz jeden bit c (carry).
        Proszę napisać funkcję (ripple-carry-adder A B S c), która generuje takiego sumatora. Argumenty A, B i S są listami kablów ai, bi i si, a c kablem carry.
        Proszę wygenerować ripple-carry-adder dla n = 4 bity i z nim obliczyć 1011 + 0011 oraz 1011 + 0110.