PasteRack.org
Paste # 69166
2016-12-09 11:17:08

Fork as a new paste.

Paste viewed 55 times.


Embed:

  1. #lang racket
  2.  
  3. ;; Aufgabe 1
  4.  
  5. ; Die ausgefuellte Tabelle sieht so aus:
  6.  
  7. ; name       |   lineare   | Baum | geschachtelt | direkt | indirekt
  8. ;------------|-------------|------|--------------|--------|----------
  9. ; kopfstueck |     ja      | nein |     nein     |   ja   |   nein
  10. ; endstueck  |     ja      | nein |     nein     |   ja   |   nein
  11. ; merge      | ja (binaer) | nein |     nein     |   ja   |   nein
  12. ; merge-sort |    nein     |  ja  |    (nein)    |   ja   |   nein
  13.  
  14. ; Kopfstueck:
  15. ; Im Rumpf der Funktion Kopfstueck steht lediglich ein Funktionsaufruf, und zwar ruft sie sich selbst auf.
  16. ; D.h. die Funktion ist direkt, linear und nicht geschachtelt (sonst muessten wir mindestens zwei Aufrufe haben).
  17. ; Das schliesst aus, das die Funktion baumartig und indirekt sein kann.
  18.  
  19. ; endstueck:
  20. ; Im Rumpf der Funktion endstueck steht lediglich ein Funktionsaufruf, und zwar ruft sie sich selbst auf.
  21. ; D.h. die Funktion ist direkt, linear und nicht geschachtelt (sonst muessten wir mindestens zwei Aufrufe haben).
  22. ; Das schliesst aus, das die Funktion baumartig und indirekt sein kann.
  23.  
  24. ; merge:
  25. ; Im Rumpf der Funktion merge stehen genau zwei Funktionsaufrufe, beide Male ruft sie sich selbst auf.
  26. ; Allerdings sind diese Aufrufe durch eine If-Bedingung so voneinander getrennt, dass immer nur genau einer von beiden aufgerufen wird.
  27. ; D.h. die Funktion ist direkt, linear (binear) und nicht geschachtelt (sonst muessten die zwei Aufrufe ineinander stehen).
  28. ; Das schliesst aus, das die Funktion baumartig und indirekt sein kann.
  29.  
  30. ; merge-sort:
  31. ; Im Rumpf der Funktion merge stehen genau drei Funktionsaufrufe, zwei Mal ruft sie sich selbst auf, ein Mal merge.
  32. ; Die beiden selbstaufrufe stehen paralel, d.h. sie werden immer beide aufgerufen. Beide Aufrufe sind parameter des merge-Aufrufes.
  33. ; D.h. die Funktion ist direkt, aber nicht linear (sie ruft sich in jedem Schritt ja zweimal selbst auf) sondern baumartig.
  34. ; Da merge, merge-sort nicht wieder aufruft, liegt auch keine indirekte Rekursion vor. Der direkte Aufruf passiert durch vorgezogenen auswertung im Rumpf der merge-sort Funktion.
  35. ; Ob die Funktion geschachtel ist, haengt von der definition ab. Wenn man streng ist, heisst geschachtelt, dass ein rekursiver Aufruf mit einem rekursiven Aufruf als Parameter aufgerufen wird ( f(x) = f( f(x - 1) ).
  36. ; Lockerere Definitionen sehen das in der Aufgabe vorliegende schon als geschachtelt an.
  37.  
  38. ;; Aufgabe 2
  39. (require 2htdp/image)
  40. (require lang/posn)
  41. (require 2htdp/universe)
  42.  
  43. (define (eqtriangle-height sidelength)
  44.   (sqrt (- (sqr sidelength) (sqr (/ sidelength 2)))))
  45. ; (eqtriangle-height 300)
  46.  
  47. (define (_ss sideLength x y image)
  48.   (let ([halfSideLength (/ sideLength 2)])
  49.     (place-image
  50.      (isosceles-triangle halfSideLength 60 "solid" "red")
  51.      (+ x halfSideLength)
  52.      (+ y (/ (eqtriangle-height sideLength) 4))
  53.      image)))
  54.  
  55. (define (addToPosn pos x y)
  56.   (make-posn (+ (posn-x pos) x) (+ (posn-y pos) y)))
  57.  
  58. (define (placeRedOnes sideLength x y image)
  59.   (if (< sideLength 10)
  60.       image
  61.       (let* ([halfSideLength (/ sideLength 2)]
  62.              [quarterSideLength (/ sideLength 4)]
  63.              [halfHeight (/ (eqtriangle-height sideLength) 2)]
  64.              [eighthHeight (/ halfHeight 4)]
  65.              [block1 (make-posn x y)]
  66.              [block2 (make-posn (+ x halfSideLength) y)]
  67.              [block3 (make-posn (+ x quarterSideLength) (+ y halfHeight))]
  68.              [pos1   (addToPosn block1 quarterSideLength eighthHeight)]
  69.              [pos2   (addToPosn block2 quarterSideLength eighthHeight)]
  70.              [pos3   (addToPosn block3 quarterSideLength eighthHeight)]
  71.              [redTriangle (isosceles-triangle quarterSideLength 60 "solid" "red")]
  72.              [newImage (place-images
  73.                         (list redTriangle redTriangle redTriangle)
  74.                         (list pos1
  75.                               pos2
  76.                               pos3)
  77.                         image)])
  78.         (placeRedOnes halfSideLength (posn-x block1) (posn-y block1)
  79.                       (placeRedOnes halfSideLength (posn-x block2) (posn-y block2)
  80.                                     (placeRedOnes halfSideLength (posn-x block3) (posn-y block3) newImage)))
  81.         )))
  82.  
  83. (define (ss sideLength)
  84.   (let* ([halfSideLength (/ sideLength 2)]
  85.          [BlackTriangle (isosceles-triangle sideLength 300 "solid" "black")]
  86.          [redTriangle (isosceles-triangle halfSideLength 60 "solid" "red")]
  87.          [baseImage (place-image
  88.                      redTriangle
  89.                      halfSideLength
  90.                      (/ (eqtriangle-height sideLength) 4)
  91.                      BlackTriangle)])
  92.     (placeRedOnes sideLength 0 0 baseImage)))
  93. (ss 300)

=>