Funkcionálne programovanie cvičenie 3

Created: 2009-10-07 - 19:46

;n! a fibonacciho postupnost interativne...
;faktorial:

(define (faktorial n)
  (define (f n s)
    (if (= n 0)
        s
        (f (- n 1) (* n s))))
  (f n 1))

;fibonacci

(define (fibonacci n)
  (define (f n a b)
    (if (= n 0)
        a
        (f (- n 1) b (+ a b))))
  (f n 0 1))

;plus
;
; x + 0 = x
; x + (n + 1) = (x + n) + 1
; rekurzivne:
(define (plus x y)
  (if (= x 0)
      y
      (add1 (plus (sub1 x) y))))
; iterativna:
(define (plus-i x y)
  (define (p x y)
    (if (= x 0)
        y
        (p (sub1 x) (add1 y) )))
  (p x y))
; cize, kazda prim. rekurzivna funkcia sa da zapisat iterativne
;

; podobne krat:
(define (krat x y)
  (define (k x y s)
    (if (= x 0)
        s
        (k (sub1 x) y (plus-i y s))))
  (k x y 0))
; priamo iterativne:
(define (krat-i x y)
  (define (k x s y z)
    (if (= x 0)
        s
        (if (= z 0)
           (k (sub1 x) s y y)
           (k x (add1 s) y (sub1 z)))))
  (k x 0 y y))

;mocnina:
(define (mocnina x y)
  (if (= y 0)
      1
      (* x (mocnina x (- y 1)))))

;iterativne:
(define (mocnina-i x y)
  (define (f x y m)
    (if (= y 0)
        m
        (f x (- y 1) (* x m))))
  (f x y 1))

;mocnina inak - rekurzivne ale s log. zlozitostou
(define (fast-exp x n)
  (define (square x) (* x x))
  (cond ((= n 0) 1)
        ((even? n) (square (fast-exp x (/ n 2))))
        (else (* x (fast-exp x (- n 1))))))

;ak chceme porovnavat jednotlive casy behu aplikacii spravime si na to procedurku:
(define (cas procedura . argumenty)
  (define zaciatok (current-process-milliseconds))
  (define a (apply procedura argumenty))
  (define doba (- (current-process-milliseconds)
                  zaciatok))
  (display (list 'vysledok = a' doba_trvania doba)))

;klasicky problem rozmenenia bankovky na drobne...
; mame nominalne hodnoty 1,2,5,10,20,50c, 1,2 eur ...
; p ( a , k ) / kde a je suma a k je pocet nominalnych hodnot minci
; odvodime si vzorec:
;
;                  p ( a , k ) = p ( a , k-1 ) + p ( a - d_k, k )
; a = 0            p ( a , k ) = 1
; a < 0            p ( a , k ) = 0
; k = 0, a != 0    p ( a , k ) = 0

(define (pocet_zmine suma)
  (p suma 8))
(define (p a k)
  (cond ((= a 0) 1)
        ((< a 0) 0)
        ((= k 0) 0)
        (else (+ (p a (- k 1))
                 (p (- a (nominal k)) k)))))
(define (nominal k)
  (cond ((= k 1) 2)
        ((= k 2) 1)
        ((= k 3) 0.5)
        ((= k 4) 0.2)
        ((= k 5) 0.1)
        ((= k 6) 0.05)))

;na domacu: fast-exponent iterativne spravit!!!