Rekursive Prozeduren 2
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
[[Programmierparadigmen_-_Computerübungen|zur Übungsübersicht]]
<code id="4eb91dc040385" hidden>
(module compat mzscheme
(provide real-time
1+ 1-
>=? <=? >? <? =?
flush-output-port
gentemp
atom?
putprop getprop
new-cafe
define-structure)
(define 1+ add1)
(define 1- sub1)
(define =? =)
(define <? <)
(define >? >)
(define <=? <)
(define >=? >)
(define atom? (lambda (v) (not (pair? v))))
(define gentemp gensym)
(define flush-output-port flush-output)
(define real-time current-milliseconds)
(define table (make-hash-table))
(define getprop
(case-lambda
[(k prop) (getprop k prop #f)]
[(k prop def)
(let ([al (hash-table-get table k (lambda () #f))])
(if al
(let ([v (assq prop al)])
(if v
(unbox (cdr v))
def))
def))]))
(define putprop
(lambda (k prop nv)
(let ([al (hash-table-get table k (lambda () '()))])
(let ([v (assq prop al)])
(if v
(set-box! (cdr v) nv)
(hash-table-put! table k (cons (cons prop (box nv)) al)))))))
;; Chez's new-cafe
(define new-cafe
(letrec ([nc
(case-lambda
[() (nc (current-eval))]
[(eval)
(let/ec escape
(let ([orig-exit (exit-handler)]
[orig-eval (current-eval)])
(dynamic-wind
(lambda ()
(current-eval eval)
(exit-handler
(lambda (v) (escape v))))
read-eval-print-loop
(lambda ()
(current-eval orig-eval)
(exit-handler orig-exit)))))])])
nc))
(define-syntax define-structure
(lambda (stx)
(syntax-case stx ()
[(_ (sname field ...))
(syntax (define-structure (sname field ...) ()))]
[(_ (sname field ...) ([init-field init] ...))
(andmap identifier? (syntax->list
(syntax (sname field ... init-field ...))))
(let ([name (symbol->string (syntax-e (syntax sname)))]
[fields (map symbol->string
(map syntax-e
(syntax->list (syntax (field ...)))))]
[init-fields (map symbol->string
(map syntax-e
(syntax->list (syntax (init-field ...)))))]
[+ (lambda args
(datum->syntax-object
(syntax sname)
(string->symbol (apply string-append args))
(syntax sname)))])
(with-syntax ([struct: (+ "struct:" name)]
[make- (+ "make-" name)]
[? (+ name "?")]
[(gs ...)
(apply
append
(map (lambda (f) (list (+ name "-" f)
(+ "set-" name "-" f "!")))
(append fields init-fields)))])
(syntax
(define-values (struct: make- ? gs ...)
(let ()
(define-struct sname (field ... init-field ...))
(values struct:
(let ([make- (lambda (field ...)
(make- field ...
init ...))])
make-)
? gs ...))))))]))))
</code>
==Fakultät==
Schreiben Sie eine rekursive Prozedur <tt>fak</tt>, die eine Zahl n als Argument erwartet und deren Fakultät n! als Ergebnis liefert.
<code id="4ae713bf976a6">;Ihre Fakultätsprozedur fak</code>
<run id="4ae713bf9addf">(fak 5)</run>
<check>(and (= 1 (fak 0)) (= 120 (fak 5)))</check>
==Fibonacci==
Schreiben Sie eine rekursive Prozedur <tt>fib</tt>, die die n-te Fibonacci-Zahl als Ergebnis liefert.
'''Hinweis:''' Die n-te Fibonacci-Zahl ergibt sich aus der Summe ihrer beiden Vorgänger. Die 0-te und 1-te Fibonacci-Zahl ist jeweils 1.
<code id="4ae713bf97e05">;Ihre Fibonacci-Prozedur fib</code>
<run id="4ae713bf9b5b6">(fib 5)</run>
===Fibonacci Liste===
Schreiben Sie eine rekursive Prozedur <tt>fibonacci_list</tt>, die eine Liste mit den ersten n Fibonaccizahlen zurückgibt. Beachten Sie, dass <tt>(fib 0)</tt> die erste Fibonacci-Zahl in der Liste liefert.
'''Hinweis:''' Verwenden Sie zur Lösung dieser Aufgabe Ihre Prozedur <tt>fib</tt> aus der vorherigen Aufgabe! <br/>
Sollte die entstehende Liste absteigend sortiert sein, so kann dies mittels <tt>reverse</tt> behoben werden.
<code id="4ae713bf985d6">;Ihre Prozedur fibonacci_list</code>
<code id="4ae713bf98dcb" hidden>
(require (lib "compat.ss"))
(define listvergleich
(lambda(ls1 l2s)
(equal? (sort < ls1) (sort < ls2))))
</code>
<run id="4ae713bf9bd97">(fibonacci_list 5)</run>
<check>(listvergleich '(1 1 2 3 5 8 13 21 34 55 89 144) (fibonacci_list 12))</check>
==Ascending List==
Schreiben Sie eine Prozedur <tt>ascending</tt>, die eine Liste nimmt und <tt>#t</tt> zurückgibt, falls die Listenelemente aufsteigend geordnet sind, ansonsten <tt>#f</tt>.
'''Hinweis:''' Beachten Sie das Resultat für die leere Liste ’().
'''Aufrufbeispiele:'''
{|
|-
|<tt>
> (ascending '(1 2 4 7))
#t
> (ascending '(1 3 4 5 2 6))
#f
> (ascending '())
#t
</tt>
|}
<code id="4ae713bf9957e">;Ihre ascending-Prozedur</code>
<run id="4ae713bf9c4f5">(ascending '(1 2 8 34 89 999))</run>
<check>
(and (ascending '()) (ascending '(1 5 7 9)) (not (ascending '(1 3 4 2 8))))
</check>
==Längenbestimmung==
===Listenlänge===
Schreiben Sie eine Prozedur <tt>my-length</tt>, die eine Liste als Argument nimmt und die Anzahl der Elemente in der 1. Ebene ausgibt. Die eingebaute Prozedur <tt>length</tt> darf dabei nicht verwendet werden!
Aufrufbeispiele:
{|
|-
|<tt>
> (my-length ’(1 2 3 4 5))
5
> (my-length ’(1 2 3 4 5 (6 7) (8 (9 10 (11))))
7
</tt>
|}
<code id="4ae713bf99e70">;Ihre Prozedur my-length</code>
<run id="4ae713bf9cc3a">(my-length '(1 2 (3 (4 5 6)) (7 2) 8))</run>
<check>(and (= (my-length '(1 2 4)) 3) (= (my-length '(1 (1 2) (2 3) 5)) 4) (= (my-length '()) 0))</check>
===Tiefenlänge===
Schreiben Sie eine weitere Prozedur <tt>deep-length</tt>, die ebenfalls eine Liste als Argument nimmt, jedoch die Anzahl ''aller'' Elemente in ''sämtlichen'' Teillisten ausgibt.
'''Hinweis''': Verwenden Sie Ihre Prozedur <tt>mylength</tt> und arbeiten Sie an deren Programmcode, um <tt>deep-length</tt> herzustellen.
'''Aufrufbeispiele''':
{|
|<tt>
> (deep-length ’(1 2 3 4 5))
5
> (deep-length ’(1 2 3 4 5 (6 7) (8 (9 10 (11))))
11
</tt>
|}
<code id="4ae713bf9a617">;Ihre Prozedur deep-length</code>
<run id="4ae713bf9d40e">(deep-length '(1 (2 3) (3 (5 7))))</run>
<check>(and (= (deep-length '()) 0) (= (deep-length '(1 2 3 4 5)) 5) (= (deep-length '(1 2 (3 4 (5 6)) 7 8)) 8))</check>
[[Programmierparadigmen_-_Computerübungen|zur Übungsübersicht]]