#### 230 lines 4.1 KiB Scheme Raw Permalink Blame History

 ```#lang scheme ``` ``` ``` ``` ``` ```;; 1.9 ``` ``` ``` ```;; 1. primer: rekurziven ``` ```;; (+ 4 5) = inc((inc(inc(inc(5)))) = inc((inc(inc(6))) = inc((inc(7)) = inc(8) = 9 ``` ```;; 2. primer: iterativen ``` ```;; (+ 4 5): ``` ```;; (+ 3 6) ``` ```;; (+ 2 7) ``` ```;; (+ 1 8) ``` ```;; (+ 0 9) ``` ```;; 9 ``` ``` ``` ``` ``` ```;; 1.10 ``` ```;; Ackermannova funkcija ``` ```;; https://en.wikipedia.org/wiki/Ackermann_function - tukaj malo drugacna definicija, mislim, da se indeksiranje premakne za 3 ``` ``` ``` ```( define (A x y) ``` ```( cond ((= y 0 ) 0 ) ``` ```(( = x 0 ) ( * 2 y)) ``` ```((= y 1 ) 2 ) ``` ```( else (A ( - x 1 ) ``` ```( A x ( - y 1 ) ) ) ) ) ) ``` ``` ``` ```(A 1 10 ) ``` ```(A 2 4) ``` ```(A 3 3) ``` ``` ``` ```;; (f n) = 2*n ``` ```;; (g n) = 2^n ``` ```;; (h n) = ``` ``` ``` ```;;;; iz knjige ``` ```;;;; ``` ```(define (fib n) ``` ```( cond (( = n 0 ) 0) ``` ```(( = n 1) 1 ) ``` ```( else ( + ( fib ( - n 1 ) ) ``` ```( fib ( - n 2 ) ) ) ) ) ) ``` ``` ``` ```(fib 10) ``` ```;;;; ``` ```;;;; ``` ``` ``` ```;; 1.11 ``` ``` ``` ```;; rekurzivno ``` ```(define (f-rec n) ``` ```( cond (( < n 3 ) n) ``` ```( else ( + (f-rec ( - n 1 )) (* 2 (f-rec (- n 2))) (* 3 (f-rec (- n 3))))))) ``` ``` ``` ```(f-rec 6) ``` ``` ``` ``` ``` ```;;;; iz knjige ``` ```;;;; ``` ```( define (fib2 n) ``` ```( fib-iter 1 0 n) ) ``` ``` ``` ```( define ( fib-iter a b count ) ``` ```( if (= count 0 ) ``` ```b ``` ```( fib-iter (+ a b) a ( - count 1 ) ) ) ) ``` ``` ``` ```(fib2 10) ``` ```;;;; ``` ```;;;; ``` ``` ``` ```;; iterativno ``` ```( define (f2 n) ``` ```( f-iter n (if (< n 2) n 2)) ) ``` ``` ``` ```( define ( f-iter max-count sum) ``` ```( if (< max-count 3 ) ``` ```max-count ``` ```(+ (f-iter (- max-count 1) sum) (* 2 (f-iter (- max-count 2) sum )) (* 3 (f-iter (- max-count 3) sum ))))) ``` ``` ``` ```(f2 6) ``` ``` ``` ``` ``` ```;; 1.12 ``` ```(define (pascal r c) ``` ``` (if (or (= r 0) (= c 1) (= c r)) ``` ``` 1 ``` ``` (+ (pascal (- r 1) c) (pascal (- r 1) (- c 1))))) ``` ``` ``` ```(pascal 5 3) ``` ``` ``` ```;; 1.13 na papirju ``` ``` ``` ```;; 1.14 na papirju ``` ``` ``` ``` ``` ```;;;; iz knjige ``` ```;;;; ``` ```( define ( count-change amount ) ``` ```( cc amount 5 ) ) ``` ``` ``` ```( define ( cc amount kinds-of-coins ) ``` ```( cond (( = amount 0) 1 ) ``` ```(( or (< amount 0 ) ( = kinds-of-coins 0 ) ) 0 ) ``` ```( else (+ ( cc amount ``` ```( - kinds-of-coins 1 ) ) ``` ```( cc ( - amount ``` ```( first-denomination kinds-of-coins ) ) ``` ```kinds-of-coins ) ) ) ) ) ``` ```(define ( first-denomination kinds-of-coins) ``` ```( cond (( = kinds-of-coins 1 ) 1) ``` ```(( = kinds-of-coins 2 ) 5) ``` ```(( = kinds-of-coins 3) 10 ) ``` ```(( = kinds-of-coins 4) 25 ) ``` ```(( = kinds-of-coins 5 ) 50) ) ) ``` ``` ``` ```( count-change 11) ``` ```;;;; ``` ```;;;; ``` ``` ``` ``` ``` ```;;;; iz knjige ``` ```;;;; ``` ```(define (square x) (* x x)) ``` ``` ``` ```( define ( even? n) ``` ```(= (remainder n 2 ) 0 ) ) ``` ``` ``` ```( define ( fast-expt b n) ``` ```( cond ( (= n 0 ) 1 ) ``` ```( ( even? n ) ( square ( fast-expt b ( / n 2 ) ) ) ) ``` ```( else ( * b ( fast-expt b ( - n 1 ) ) ) ) ) ) ``` ``` ``` ```(fast-expt 2 5) ``` ```;;;; ``` ```;;;; ``` ``` ``` ```;; 1.15 ``` ```;; a) 5 ``` ```;; b) O(log n) (?) ``` ``` ``` ```;; 1.16 ``` ```( define ( fast-exp-iter n b a ) ``` ```( if (= n 0 ) ``` ```a ``` ```(if (even? n) (fast-exp-iter ( / n 2 ) (square b) a ) ( * b ( fast-exp-iter ( - n 1 ) (* a b) a ) ) ) ) ) ``` ``` ``` ```(fast-exp-iter 10 2 1 ) ``` ``` ``` ```;; 1.17 ``` ``` ``` ```;;;; iz knjige ``` ```;;;; ``` ```(define (mult a b) ``` ```(if (= b 0) ``` ```0 ``` ```(+ a (mult a (- b 1 ) ) ) ) ) ``` ``` ``` ```(mult 3 4) ``` ```;;;; ``` ```;;;; ``` ``` ``` ```;; naloga ``` ```(define (double x) (+ x x)) ``` ```(define (halve x) (/ x 2)) ;; a bi to moralo biti kako drugace; zakaj uporabljam deljenje pri implementaciji mnozenja s sestevanjem ``` ``` ``` ```( define ( fast-mult a b) ``` ```( cond ( (= b 0 ) 0 ) ``` ```( ( even? b ) ( double ( fast-mult a (halve b) ) ) ) ``` ```( else ( + a ( fast-mult a ( - b 1 ) ) ) ) ) ) ``` ``` ``` ```(fast-mult 8 7) ``` ``` ``` ```;; 1.18 ``` ``` ``` ```( define ( fast-mult-iter b a c) ``` ```( if (= b 0 ) ``` ```0 ``` ```(if (even? b) (fast-mult-iter (halve b) (double a) c ) ( + a ( fast-mult-iter ( - b 1 ) a c ) ) ) ) ) ``` ``` ``` ```(fast-mult-iter 18 10 0 ) ``` ``` ``` ```;; 1.21 ``` ``` ``` ```;;;; iz knjige ``` ```;;;; ``` ```( define ( smallest-divisor n) ``` ```( find-divisor n 2 ) ) ``` ```( define (find-divisor n test-divisor) ``` ```( cond (( > ( square test-divisor) n) n) ``` ```(( divides? test-divisor n) test-divisor) ``` ```(else ( find-divisor n (+ test-divisor 1 ) ) ) ) ) ``` ```( define (divides? a b ) ``` ```(= (remainder b a) 0 ) ) ``` ``` ``` ```(smallest-divisor 19999) ``` ``` ``` ```( define (prime? n) ``` ```(= n ( smallest-divisor n) ) ) ``` ```;;;; ``` ```;;;; ``` ``` ``` ``` ``` ``` ``` ```;; 1.22 ``` ``` ``` ```(define (runtime) (current-milliseconds)) ;; brez tega error: runtime: unbound identifier in: runtime ``` ``` ``` ```;;;; iz knjige ``` ```;;;; ``` ```(define (timed-prime-test n) ``` ```(newline) ``` ```(display n) ``` ```(start-prime-test n (runtime))) ``` ```(define (start-prime-test n start-time) ``` ```(if (prime? n) ``` ```(report-prime (- (runtime) start-time)) -1)) ``` ```(define (report-prime elapsed-time) ``` ```(display "***" ) ``` ```(display elapsed-time)) ``` ```;;;; ``` ```;;;; ``` ``` ``` ```(timed-prime-test 87178291199) ;; 35742549198872617291353508656626642567 ``` ``` ``` ```;; https://en.wikipedia.org/wiki/List_of_prime_numbers ``` ``` ``` ``` ``` ```;; 1.26 ``` `;; ker se s klicanjem (/ exp 2) v navadnem mnozenju parameter exp ne razpolovi v naslednjem koraku ?`