Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Aufgabe 1 - Komplexität
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:algoks:loesungws09 [25.07.2012 15:00] – *Überschrift 6. Coons-Patches konsti4u | pruefungen:bachelor:algoks:loesungws09 [29.01.2014 20:51] – Dawodo | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | Link zum FSI-Thread: | ||
+ | [[https:// | ||
+ | |||
==== 1. Komplexität ==== | ==== 1. Komplexität ==== | ||
* O(n³) | * O(n³) | ||
Zeile 18: | Zeile 21: | ||
=== b) === | === b) === | ||
- | n n n j n | + | n n n j n |
=== c) === | === c) === | ||
- | n n n n j | + | n n n n j |
=== d) === | === d) === | ||
- | j j n j j | + | j j n j j |
Zeile 65: | Zeile 68: | ||
=== d) === | === d) === | ||
- | ... | + | Punkt P teilt Dreieck in drei Teil-Dreiecke. Das Verhältnis jedes Teil-Dreiecks (Punkt P und je zwei der anderen ursprünglichen Punkte) zum ganzen Dreieck ergibt jeweils eine baryzentrische Koordinate. |
=== e) === | === e) === | ||
- | [[http:// | + | Bild 1: Gerade durch T und die Mittelsenkrechte der Strecke RS |
+ | Bild 2: Gerade durch T und S | ||
Zeile 115: | Zeile 119: | ||
=== c) === | === c) === | ||
- | Für dünnbesetzte | + | Für dünnbesetzte |
Zeile 129: | Zeile 133: | ||
=== b) === | === b) === | ||
- | x = (3/2, 1, -4, 2)^T | + | x = (3/2, 1, -4, 2)^T |
==== 10. Aitken-Neville ==== | ==== 10. Aitken-Neville ==== | ||
=== a) === | === a) === | ||
- | < | + | < |
- | NewtonPolynom :: NewtonPolynom(const float *_x , const float *_y, const int _n ) | + | NewtonPolynom :: NewtonPolynom(const float *_x, const float *_y, const int _n) |
{ | { | ||
- | | + | n = _n; |
- | + | ||
- | x = new float[n]; | + | |
- | y = new float[n]; | + | |
- | a = new float[n]; | + | |
- | + | ||
- | for ( int i = 0; i < n; i++) { | + | |
- | x[i] = _x[i] ; | + | |
- | y[i] = _y[i] ; | + | |
- | } | + | |
- | + | ||
- | + | ||
- | //Erster Koeffizient | + | |
- | a[0] = y[0]; | + | |
- | + | ||
- | + | ||
- | for ( int k = 1; k < n; i++) | + | |
- | { | + | |
- | for (int i = 0; i < n-k+1; i++) | + | |
- | { | + | |
- | y[i] = (y[i] - y[i+1]) / (x[i] - x[i+k]) | + | |
- | } | + | |
- | + | ||
- | // | + | |
- | a[k] = y[0]; | + | |
- | } | + | |
+ | x = new float[n]; | ||
+ | y = new float[n]; | ||
+ | a = new float[n]; | ||
+ | |||
+ | for (int i = 0; i < n; i++) { | ||
+ | x[i] = _x[i] ; | ||
+ | y[i] = _y[i] ; | ||
+ | } | ||
+ | |||
+ | // Erster Koeffizient | ||
+ | a[0] = y[0]; | ||
+ | |||
+ | for (int row = 1; row < n; row++) | ||
+ | { | ||
+ | for (int col = 0; col < n-col; col++) | ||
+ | { | ||
+ | y[col] = (y[col+1] - y[col]) / (x[row+col] - x[col]); | ||
+ | } | ||
+ | |||
+ | // Übernehme Koeffizienten (der immer im höchsten Element ist) | ||
+ | a[row] = y[0]; | ||
+ | } | ||
} | } | ||
</ | </ | ||
=== b) === | === b) === | ||
- | < | + | < |
- | float NewtonPolynom:: | + | float NewtonPolynom:: |
{ | { | ||
- | | + | float result = a[n-1]; |
- | | + | |
- | for (int i = n-2; i > 0; i--) | + | for (int i = n-2; i >= 0; i--) |
- | { | + | { |
- | result = a[i] + (x - x[i])*result; | + | result = a[i] + (x0 - x[i]) * result; |
- | } | + | } |
- | | + | |
- | return result; | + | return result; |
} | } | ||
</ | </ | ||