Fibonnaci, Bäume und Quadrate
Kategorie Allgemein Scheme
Jo, was hat das alles miteinander zu tun?
Eigentlich geht es nur um die Implementierung zweier Prozeduren:
a) Die Summe der Quadrate aller Zahlen, welche in einem Baum gespeichert sind und ungerade sind.
b) Eine Liste alle Fibonacci Zahlen (bis zu einem gegebenen n), welche gerade sind
Falls einen das nicht interessiert, einfach aufhören zu lesen
Jo, was hat das alles miteinander zu tun?
Eigentlich geht es nur um die Implementierung zweier Prozeduren:
a) Die Summe der Quadrate aller Zahlen, welche in einem Baum gespeichert sind und ungerade sind.
b) Eine Liste alle Fibonacci Zahlen (bis zu einem gegebenen n), welche gerade sind
Falls einen das nicht interessiert, einfach aufhören zu lesen
Die Algorithmen können ungefähr so aussehen
->
a) Summer der Quadrate der ungeraden Zahlen in einem Baum
- Laufe durch alle Blätter des Baumes
- wähle nur die ungeraden Zahlen aus
- bilde das Quadrat der Zahlen
- bilde die Summe der Quadrate
und b)
- Gehe alle Zahlen von 0 bis n durch
- berechne die Fibonnaci's für jede Zahl
- wähle die Zahlen aus, welche gerade sind
- bilde die Ergebnis Liste aus den Fibonacci's
Egal in welcher Sprache man es implementiert, es wird wohl mehr oder weniger wie folgt aussehen->
(define (sum-odd-square tree)
(cond
((null? tree)
0
)
((not (pair? tree))
(if (odd? tree) (square tree) 0)
)
(else
(+
(sum-odd-square (car tree))
(sum-odd-square (cdr tree))
)
)
)
)
(define (equal-fibs n)
(define (next k)
(if (> k n)
nil
(let ((f (fib k)))
(if (equal? f)
(cons f (next (+ k 1)))
(next (+ k 1))
)
)
)
)
(next 0)
)
Wie man relativ schnell sieht, haben die beiden Prozeduren eigentlich nicht viel gemeinsam, oder?
Dann bis heute abend, da werde ich zeigen, dass man die beiden Prozeduren, in ein gemeinsames Korsett stecken kann
Gruß JJR
a) Summer der Quadrate der ungeraden Zahlen in einem Baum
- Laufe durch alle Blätter des Baumes
- wähle nur die ungeraden Zahlen aus
- bilde das Quadrat der Zahlen
- bilde die Summe der Quadrate
und b)
- Gehe alle Zahlen von 0 bis n durch
- berechne die Fibonnaci's für jede Zahl
- wähle die Zahlen aus, welche gerade sind
- bilde die Ergebnis Liste aus den Fibonacci's
Egal in welcher Sprache man es implementiert, es wird wohl mehr oder weniger wie folgt aussehen->
(define (sum-odd-square tree)
(cond
((null? tree)
0
)
((not (pair? tree))
(if (odd? tree) (square tree) 0)
)
(else
(+
(sum-odd-square (car tree))
(sum-odd-square (cdr tree))
)
)
)
)
(define (equal-fibs n)
(define (next k)
(if (> k n)
nil
(let ((f (fib k)))
(if (equal? f)
(cons f (next (+ k 1)))
(next (+ k 1))
)
)
)
)
(next 0)
)
Wie man relativ schnell sieht, haben die beiden Prozeduren eigentlich nicht viel gemeinsam, oder?
Dann bis heute abend, da werde ich zeigen, dass man die beiden Prozeduren, in ein gemeinsames Korsett stecken kann
Gruß JJR
| Permalink | 
