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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:algoks:loesungws09 [25.07.2012 15:00] – *Überschrift 6. Coons-Patches konsti4upruefungen:bachelor:algoks:loesungws09 [29.01.2014 20:51] – Dawodo
Zeile 1: Zeile 1:
 +Link zum FSI-Thread:
 +[[https://fsi.informatik.uni-erlangen.de/forum/thread/7529-Klausur-vom-Februar-2010-Loesungsversuch]]
 +
 ==== 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://img6.imagebanana.com/img/jyltkz6k/5e.jpg]]+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 matrizen besonders gut geeignet+Für dünnbesetzte Matrizen besonders gut geeignet.
  
  
Zeile 129: Zeile 133:
  
 === b) === === b) ===
-x = (3/2, 1, -4, 2)^T +x = (3/2, 1, -4, 2)^T
  
  
Zeile 135: Zeile 139:
 === a) === === a) ===
 <code> <code>
-NewtonPolynom :: NewtonPolynom(const float *_x , const float *_y, const int _n )+NewtonPolynom :: NewtonPolynom(const float *_x, const float *_y, const int _n)
 { {
-    n = _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])            +
-        }            +
-        +
-        //Übernehme Koeffizienten (der immer im höchsten Element ist) +
-        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];
 + }
 } }
 </code> </code>
Zeile 169: Zeile 170:
 === b) === === b) ===
 <code> <code>
-float NewtonPolynom::operator()( const float x0 ) const+float NewtonPolynom::operator()(const float x0) const
 { {
-    float result = a[n-1]; + 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;
 } }
 </code> </code>