Grundlagen der Informatik (Alex Rempel)


Download 160.2 Kb.

Sana22.03.2017
Hajmi160.2 Kb.

Grundlagen der Informatik (Alex Rempel)

1

Grundlagen der Informatik



10. Funktionen und Arrays

Mathematische Funktionen

char Arrays

Suchen


Sortieren

Grundlagen der Informatik (Alex Rempel)

2

Grundlagen der Informatik



Mathematische Funktionen

Winkel zwischen 2 Vektoren berechnen



Formel:


Vektoren:

Benötigte Funktionen/Informationen:



Skalarprodukt

Betrag bzw. Länge des Vektors



Arkuskosinus

Kreiszahl für Winkelrechnung



Beispiel:

cos= x , y/



x





y



x= x

1

,... , x



n



y= y

1

,... , y

n



x , y



x

arccos x



Pi

x=1,0 , y=0,1

cos= x , y/



x





y

=



0/1=0, arccos0=1.57079633=Pi / 2=90°

Grundlagen der Informatik (Alex Rempel)

3

Grundlagen der Informatik



Mathematische Funktionen

Winkel zwischen 2 Vektoren berechnen



Skalarprodukt:



x , y= for i ∈1..n



x



i



y



i

#include


 

#include


 

using


 

namespace

 std;

double

 scalarProduct(

const

 

double

 dX[], 

const

 

double

 dY[], 

const

 

int

 iLen)

{

double

 d = 0.0;

for

 (

int

 i=0; i < iLen; ++i) d += dX[i] * dY[i];

return

 d;

}

void


 main()

{

double



 d3VecX[] = {-13.4, 8.0, 0.0}, d3VecY[] = {26.8, 0.0, 99.2};

int


 iLen = 3, iOut = 10;

for


 (

int


 i=0; i < iLen; ++i)

cout << setw(iOut) << d3VecX[i] << setw(iOut) << d3VecY[i] << endl;

cout << 

"Scalar = "

 << scalarProduct(d3VecX,d3VecY,iLen) << endl;

}

     -13.4      26.8



         8         0

         0      99.2

Scalar = -359.12

Grundlagen der Informatik (Alex Rempel)

4

Grundlagen der Informatik



Mathematische Funktionen

Betrag bzw. Länge des Vektors



Betrag:




x

=





for i∈1..n



x

i

2



=



x , x

#include

 

#include


 

#include


 

using


 

namespace

 std;

double


 scalarProduct(

const


 

double


 dX[], 

const


 

double


 dY[], 

const


 

int


 iLen);

double


 vectorLength(

const


 

double


 dX[], 

const


 

int


 iLen)

{

return



 sqrt( scalarProduct(dX,dX,iLen) );

}

void



 main()

{

double



 d3VecX[] = {-13.4, 8.0, 0.0}, d3VecY[] = {26.8, 0.0, 99.2};

int


 iLen = 3, iOut = 10;

for


 (

int


 i=0; i < iLen; ++i)

cout << setw(iOut) << d3VecX[i] << setw(iOut) << d3VecY[i] << endl;

cout << 

"Length(x) = "

 << vectorLength(d3VecX,iLen) << endl;

cout << 


"Length(y) = "

 << vectorLength(d3VecY,iLen) << endl;

}

     -13.4      26.8

         8         0

         0      99.2

Length(x) = 15.6064

Length(y) = 102.756


Grundlagen der Informatik (Alex Rempel)

5

Grundlagen der Informatik



Mathematische Funktionen

Arkuskosinus und Winkelberechnung



Arkkosinus: -1.0..1.0 (Umkehrung von Kosinus)

Winkelberechnung: 2*Pi = 360° (Einheitskreis)



#define

 _USE_MATH_DEFINES

#include


 

#include


 

#include


 

using


 

namespace

 std;

double


 arccosAsRadians(

double


 dFrom) { 

return


 acos(dFrom); }

double


 getDegrees(

double


 dRadians) { 

return


 (dRadians*180.0)/M_PI; }

void


 main()

{

double



 dFrom1 = 1.0, dFrom2 = -1.0;

cout << 


"arccos("

 << dFrom1 << 

") = "

 << arccosAsRadians(dFrom1)



<< 

" rad = "

 << getDegrees(arccosAsRadians(dFrom1)) << 

" deg"


 << endl;

cout << 


"arccos("

 << dFrom2 << 

") = "

 << arccosAsRadians(dFrom2)



<< 

" rad = "

 << getDegrees(arccosAsRadians(dFrom2)) << 

" deg"


 << endl;

}

arccos(1) = 0 rad = 0 deg



arccos(-1) = 3.14159 rad = 180 deg

Grundlagen der Informatik (Alex Rempel)

6

Grundlagen der Informatik



Mathematische Funktionen

Winkelberechnung zwischen 2 Vektoren



cos= x , y/



x





y



#include

 

using

 

namespace



 std;

double


 scalarProduct(

const


 

double


 dX[], 

const


 

double


 dY[], 

const


 

int


 iLen);

double


 vectorLength(

const


 

double


 dX[], 

const


 

int


 iLen);

double


 arccosAsRadians(

double


 dFrom);

double


 getDegrees(

double


 dRadians);

double

 angleBetween(

const

 

double

 dX[], 

const

 

double

 dY[], 

const

 

int

 iLen)

{

return

 getDegrees(arccosAsRadians(

scalarProduct(dX,dY,iLen)/

(vectorLength(dX,iLen) * vectorLength(dY,iLen))

));

}

void


 main()

{

double



 d3VecX[] = {-13.4, 8.0, 0.0}, d3VecY[] = {26.8, 0.0, 99.2};

int


 iLen = 3, iOut = 10;

for


 (

int


 i=0; i < iLen; ++i)

cout << setw(iOut) << d3VecX[i] << setw(iOut) << d3VecY[i] << endl;

// calculate and output vector angles

cout << 


"Angle = "

 << angleBetween(d3VecX,d3VecY,3) << 

" deg"

 << endl;



}

     -13.4      26.8

         8         0

         0      99.2

Angle = 102.94 deg

Sind in einer anderen Datei



Grundlagen der Informatik (Alex Rempel)

7

Grundlagen der Informatik



Mathematische Funktionen

Winkelberechnung zwischen 2 Vektoren



cos= x , y/



x





y





#include

 



using

 

namespace

 std;

double

 angleBetween(

const

 

double

 dX[], 

const

 

double

 dY[], 

const

 

int

 iLen);

void

 printVectorAngleCalculation(

const

 

double

 dX[], 

const

 

double

 dY[], 

const

 

int

 iLen)

{

cout << 

"X = |"

;

for

 (

int

 i=0; i < iLen; ++i) cout << dX[i] << 

"|"

;

cout << 

", Y = |"

;

for

 (

int

 i=0; i < iLen; ++i) cout << dY[i] << 

"|"

;

cout << 

"\n\tAngle = "

 << angleBetween(dX,dY,iLen) << endl;

}

void

 main()

{

double

 d2VecX[] = {1.0, 0.0}, d2VecY[] = {0.0, -1.0};

double

 d3VecX[] = {13.4, 8.0, 0.0}, d3VecY[] = {26.8, 0.0, 99.2};

// calculate and output vector angles

cout << 

"...2D with 2D..."

 << endl;

printVectorAngleCalculation(d2VecX,d2VecY,2);

cout << endl << 

"...3D with 3D..."

 << endl;

printVectorAngleCalculation(d3VecX,d3VecY,3);

cout << endl << 

"...vector with self..."

 << endl;

printVectorAngleCalculation(d2VecX,d2VecX,2);

cout << endl << 

"...2D with 3D..."

 << endl;

printVectorAngleCalculation(d2VecX,d3VecX,2);

}

...2D with 2D...

X = |1|0|, Y = |0|-1|

Angle = 90

...3D with 3D...

X = |13.4|8|0|, Y = |26.8|0|99.2|

Angle = 77.0596

...vector with self...

X = |1|0|, Y = |1|0|

Angle = 0

...2D with 3D

X = |1|0|, Y = |13.4|8|

Angle = 30.8378

Grundlagen der Informatik (Alex Rempel)

8

Grundlagen der Informatik



Mathematische Funktionen

Polynome berechnen



Polynomformel: 

Hörnerschema: 



Algorithmus:



p x=a

0

x

0



a



1

x

1



a

2

x

2



...a



n

x

n

p x=a

n

xa

n−1



xa



n−2



x...a

0

p=a

n

,

ppxa

i

, for i=n−1..0

#include


 

using


 

namespace

 std;

double


 calcPolynom(

double


 a[], 

int


 iLen, 

double


 x) {

if

 (iLen <= 0) 



return

 0;


double

 p = a[iLen-1];

for

 (

int



 n=iLen-2; n >= 0; --n) p = p*x + a[n];

return


 p;

}

void



 main() {

double


 polynom[] = {-7,1,3}; 

// p(x) = 3x²+x-7 = -7 + 1*x + 3*x²

cout << 

"Polynom(0)="

 << calcPolynom(polynom,3,0) << endl;

cout << 


"Polynom(-1)="

 << calcPolynom(polynom,3,-1) << endl;

cout << 

"Polynom(1)="

 << calcPolynom(polynom,3,1) << endl;

}

Polynom(0)=-7



Polynom(-1)=-5

Polynom(1)=-3

Grundlagen der Informatik (Alex Rempel)

9

Grundlagen der Informatik



char Arrays

Ganze Zahlen aus einem Text erkennen



#include

 

using

 

namespace



 std;

int


 i_from_c(

const


 

char


 cText[], 

int


 iLen = 0) {

if

 (iLen <= 0) iLen = strlen(cText);



int

 i = 0, iSign = 1;

for

 (

int



 j=0; j < iLen; ++j)

if

 (cText[j] >= 



'0'

 && cText[j] <= 

'9'

)

i = 10*i + cText[j]-



'0'

;

else



 

if

 (cText[j] == 



'-'

 && i == 0)

iSign = -iSign;

else


break

;

return



 i*iSign;

}

void



 main() {

cout << 


"-340 = "

 << i_from_c(

"-340"

) << 


" = "

 << atoi(

"-340"

) << endl;



cout << 

"6224 = "

 << i_from_c(

"6224"


) << 

" = "


 << atoi(

"6224"


) << endl;

cout << 


"3-42 = "

 << i_from_c(

"3-42"

) << 


" = "

 << atoi(

"3-42"

) << endl;



cout << 

"0-42 = "

 << i_from_c(

"0-42"


) << 

" = "


 << atoi(

"0-42"


) << endl;

}

-340 = -340 = -340



6224 = 6224 = 6224

3-42 = 3 = 3

0-42 = -42 = 0

Bereits vorhandene

Funktion

Bereits vorhandene

Funktionen


Grundlagen der Informatik (Alex Rempel)

10

Grundlagen der Informatik



Suchen

Suche eines Elements im Array



Gegeben: Array mit Elementen und Element zum Suchen

Resultat: der Index des zu suchenden Elements



der einzige Index falls das Element nur ein Mal vorkommt

der erste Index falls das Element mehrfach vorkommt



Index '-1' falls das Element gar nicht im Array vorkommt

Algorithmen



Je nach Elementtyp, Arraytyp und Eigenschaften des Arrays 

(sortiert, einzigartige Elemente etc.) unterschiedlich


Grundlagen der Informatik (Alex Rempel)

11

Grundlagen der Informatik



Suchen

Testplan (unabhängig vom Verfahren)



Fall Beschreibung

Eingabedaten (Suchelement, Arraygröße, Array) Ergebnis



Sonderfälle

1

Leeres Aray



3, 0, {}

-1

Grenzfälle

2

1 Element, Suche OK 3, 1, {3}



0

3

1 Element, Suche !OK 3, 1, {5}



-1

Normalfälle

4

Suche !OK



9, 7, {3 5 4 7 4 8 2}

-1

5



Suche OK, Beginn

3, ||, ||

0

6

Suche OK, Mitte



7, ||, ||

3

7



Suche OK, Ende

2, ||, ||

6

8

Suche OK, Mehrfach



4, ||, ||

2


Grundlagen der Informatik (Alex Rempel)

12

Grundlagen der Informatik



Suchen

Struktogramm (sequentielle Suche)



searchSequence(element,array,length)

i = 0..(length-1)

return -1

array[i] equals element?

return i

;

yes



no

Grundlagen der Informatik (Alex Rempel)

13

Grundlagen der Informatik



Suchen

Sequentielle Suche



#include

 

#include

 

using

 

namespace



 std;

int


 searchSequence(

int


 ii[], 

int


 iLen, 

int


 iElement) {

for


 (

int


 i=0; i < iLen; ++i)

if

 (iElement == ii[i])



return

 i;


return

 -1;


}

void


 main() {

int


 iElements[] = { 3, 5, 4, 7, 4, 8, 2 };

int


 iLen = 

sizeof


(iElements)/

sizeof


(

int


);

for


 (

int


 i=0; i < iLen; ++i) cout << setw(5) << iElements[i];

cout << endl;

cout << 

"4.Case (9)="

 << searchSequence(iElements,iLen,9) << endl;

cout << 


"5.Case (3)="

 << searchSequence(iElements,iLen,3) << endl;

cout << 

"6.Case (7)="

 << searchSequence(iElements,iLen,7) << endl;

cout << 


"7.Case (2)="

 << searchSequence(iElements,iLen,2) << endl;

cout << 

"8.Case (4)="

 << searchSequence(iElements,iLen,4) << endl;

}

  3  5  4  7  4  8  2



4.Case (9)=-1

5.Case (3)=0

6.Case (7)=3

7.Case (2)=6

8.Case (4)=2

Grundlagen der Informatik (Alex Rempel)

14

Grundlagen der Informatik



Suchen

Sequentielle Suche



Mehrfaches Suchen mit einem Startindex

#include

 

#include

 

using

 

namespace



 std;

int


 searchSequence(

int


 ii[], 

int


 iLen, 

int


 iElement

int

 iStart = 0) {

for


 (

int


 i=iStart; i < iLen; ++i)

if

 (iElement == ii[i])



return

 i;


return

 -1;


}

void


 main() {

int


 iElements[] = { 3, 5, 4, 7, 4, 8, 2 };

int


 iLen = 

sizeof


(iElements)/

sizeof


(

int


);

for


 (

int


 i=0; i < iLen; ++i) cout << setw(3) << iElements[i];

cout << endl;

int

 iIndex = searchSequence(iElements,iLen,4);



cout << 

"Search(4)="

 << iIndex << endl;

cout << 


"Search next(4)="

 << searchSequence(iElements,iLen,4,iIndex+1) << endl;

}

  3  5  4  7  4  8  2

Search(4)=2

Search next(4)=4


Grundlagen der Informatik (Alex Rempel)

15

Grundlagen der Informatik



Suchen

Sequentielle Suche (typlos mit Templates)



#include

 

#include

 

using

 

namespace



 std;

template

 <

class

 ANYTYPE>

int


 searchSequence(ANYTYPE elements[], 

int


 iLen, ANYTYPE element, 

int


 iStart = 0) {

for


 (

int


 i=iStart; i < iLen; ++i)

if

 (element == elements[i])



return

 i;


return

 -1;


}

void


 main() {

int


 iElements[7] = { 3, 5, 4, 7, 4, 8, 2 };

double


 dElements[4] = { 0.0, 0.3, 0.5, -345.0 };

bool


 bElements[5] = { 

true


true


true


false


true


 };

cout << 


"Search(8)="

 << searchSequence(iElements,7,8) << endl;

cout << 

"Search(0.5)="

 << searchSequence(dElements,4,0.5) << endl;

cout << 


"Search(false)="

 << searchSequence(bElements,5,

false

) << endl;



}

Search(8)=5

Search(0.5)=2

Search(false)=3

Grundlagen der Informatik (Alex Rempel)

16

Grundlagen der Informatik



Suchen

Binäre Suche



Voraussetzung: sortiertes Array

Algorithmus:



Vergleiche Suchelement mit mittlerem Element

Wenn gefunden, gebe Index zurück



Wenn mittleres Element größer beziehungsweise kleiner als 

Suchelement wiederhole mit linker beziehungsweise rechter Hälfte

Wenn Hälfte aus 0 Elementen besteht gebe -1 zurück



Beispiel: suche 3 in {1, 2, 3, 4}

Mittleres Element ist 2, 2<3, suche in {3, 4}



Mittleres Element ist 3, 3==3, gebe Index 2 zurück



Grundlagen der Informatik (Alex Rempel)

17

Grundlagen der Informatik



Suchen

Binäre Suche (rekursive Lösung)



#include

 

#include

 

using

 

namespace



 std;

int


 searchBinary(

int


 ii[], 

int


 iElement, 

int


 iFromIncl, 

int


 iToExcl) {

if

 (iFromIncl < iToExcl) {



int

 iMid = (iFromIncl+iToExcl)/2;

if

 (iElement == ii[iMid])



return

 iMid;


else

 

if



 (ii[iMid] > iElement)

return


 searchBinary(ii,iElement,0,iMid);

else


return

 searchBinary(ii,iElement,iMid+1,iToExcl);

}

return


 -1;

}

void



 main() {

int


 iElements[] = { 1,2,3 };

int


 iLen = 

sizeof


(iElements)/

sizeof


(

int


);

cout << 


"Search(0)="

 << searchBinary(iElements,0,0,iLen) << endl;

cout << 

"Search(1)="

 << searchBinary(iElements,1,0,iLen) << endl;

cout << 


"Search(2)="

 << searchBinary(iElements,2,0,iLen) << endl;

cout << 

"Search(3)="

 << searchBinary(iElements,3,0,iLen) << endl;

cout << 


"Search(4)="

 << searchBinary(iElements,4,0,iLen) << endl;

}

Search(0)=-1

Search(1)=0

Search(2)=1

Search(3)=2

Search(4)=-1


Grundlagen der Informatik (Alex Rempel)

18

Grundlagen der Informatik



Suchen

Binäre Suche (Lösung mit einer Schleife)



#include

 

#include

 

using

 

namespace



 std;

int


 searchBinary(

int


 ii[], 

int


 iLen, 

int


 iElement) {

int


 iFrom = 0, iTo = iLen;

while


 (iFrom < iTo) {

int


 iMid = (iFrom+iTo)/2;

if

 (ii[iMid] == iElement)



return

 iMid;


else

 

if



 (ii[iMid] > iElement) iTo = iMid;

else


iFrom = iMid+1;

}

return



 -1;

}

void



 main() {

int


 iElements[] = { 1,2,3 };

int


 iLen = 

sizeof


(iElements)/

sizeof


(

int


);

cout << 


"Search(0)="

 << searchBinary(iElements,iLen,0) << endl;

cout << 

"Search(1)="

 << searchBinary(iElements,iLen,1) << endl;

cout << 


"Search(2)="

 << searchBinary(iElements,iLen,2) << endl;

cout << 

"Search(3)="

 << searchBinary(iElements,iLen,3) << endl;

cout << 


"Search(4)="

 << searchBinary(iElements,iLen,4) << endl;

}

Search(0)=-1

Search(1)=0

Search(2)=1

Search(3)=2

Search(4)=-1


Grundlagen der Informatik (Alex Rempel)

19

Grundlagen der Informatik



Suchen

Vergleichen von Suchalgorithmen



Komplexitätstheorie (worst/best/average case)

Kriterium hier: mittlere Vergleichsanzahl



Vorgabe: n=1024 Elemente

Sequentielle Suche, Vergleiche = 



Binäre Suche, Vergleiche

log


2



n=log

2



1024=10



n/2=1024/2=512

Grundlagen der Informatik (Alex Rempel)

20

Grundlagen der Informatik



Sortieren

Sortieren aller Elemente im Array



Gegeben: Array mit Elementen

Resultat: das Array ist sortiert



Algorithmen

Bubblesort (Paare vertauschen)



Sortieren durch Auswahl (tausche Maximum mit letztem)

Quicksort (rekursiv, teile Array und bearbeite die Teile)



Grundlagen der Informatik (Alex Rempel)

21

Grundlagen der Informatik



Sortieren

Sortieren durch Auswahl



Algorithmus

Suche das größte Element von n Elementen im Array



Vertausche das größte Element mit dem letzten

Wiederhole mit n=n-1



Benötigte Funktionen

Suche Index des größten Elements im Array



Vertausche 2 Elemente im Array

Führe 'Suche und vertausche solange unsortiert' aus



Grundlagen der Informatik (Alex Rempel)

22

Grundlagen der Informatik



Sortieren

Sortieren durch Auswahl



#include

 

using

 

namespace



 std;

void


 swap(

int


 ii[], 

int


 i, 

int


 j) {

int


 a=ii[i]; ii[i]=ii[j]; ii[j]=a;};

int


 getMaxId(

int


 ii[], 

int


 iLen) {

if

 (iLen <= 0) 



return

 -1;


int

 iMaxId = 0;

for

 (

int



 i=0; i < iLen; ++i)

if

 (ii[i] > ii[iMaxId]) iMaxId = i;



return

 iMaxId;


}

void


 sortMax(

int


 ii[], 

int


 iLen) {

for


 (

int


 i = iLen; i > 1; --i)

swap( ii, getMaxId(ii,i), i-1);

}

void


 main() {

int


 iElements[10] = { 5,8,32,5,6,7,3,35,3,9 };

sortMax(iElements,10);

for

 (

int



 i=0; i < 10; ++i)

cout << iElements[i] << 

"  "

;

cout << endl;



}

3  3  5  5  6  7  8  9  32  35

2 Elemente im

Array tauschen

Index des größten

Elements im

Array finden

Von hinten nach

vorne im Array

jeweils das größte

Element mit letztem

vertauschen


Grundlagen der Informatik (Alex Rempel)

23

Grundlagen der Informatik



Sortieren

Quicksort



Algorithmus

Pivot-Element auswählen (normalerweise mittleres)



Klassen bilden: kleiner als Pivot, größer als Pivot

Für beide Klassen dasselbe ausführen



Benötigte Funktionen

Vertausche 2 Elemente im Array



Teile und herrsche (rekursiv)



Grundlagen der Informatik (Alex Rempel)

24

Grundlagen der Informatik



Sortieren

Quicksort



#include

 

using

 

namespace



 std;

void


 swap(

int


 ii[], 

int


 i, 

int


 j) {

int


 a=ii[i]; ii[i]=ii[j]; ii[j]=a;};

void


 sortQuick(

int


 ii[], 

int


 iFrom, 

int


 iTo) {

int


 iMidElement = ii[(iTo+iFrom)/2]; 

// pivot element

int

 i = iFrom, j = iTo;



do

 { 


// create classes: 'lower than' and 'higher than' pivot

while


 (ii[i] < iMidElement && i < iTo) ++i;

while


 (ii[j] > iMidElement && j > iFrom) --j;

if

 (i <= j)



swap(ii,i++,j--); 

// caution: post-operator i++,j-- !

while


 (i <= j);

if

 (i < iTo) sortQuick(ii,i,iTo);



// do same for 'lower class'

if

 (j > iFrom) sortQuick(ii,iFrom,j);



// do same for 'higher class'

}

void



 main() {

int


 iElements[10] = { 5,8,32,5,6,7,3,35,3,9 };

sortQuick(iElements,0,9);

for

 (

int



 i=0; i < 10; ++i)

cout << iElements[i] << 

"  "

;

cout << endl;



}

3  3  5  5  6  7  8  9  32  35

Grundlagen der Informatik (Alex Rempel)

25

Grundlagen der Informatik



Sortieren

Sortieralgorithmen: Kriterien und Laufzeiten



Kriterien:

mittlere Anzahl der Vergleiche



mittlere Anzahl der Vertauschungen



Algorithmen

Vergleiche Vertauschungen

Bubblesort



n²/2

¾*n²


Sortieren durch Auswahl

n²/2

n



Quicksort

2n*ln(n)


n*ln(n)

Document Outline

  • Folie 1
  • Folie 2
  • Folie 3
  • Folie 4
  • Folie 5
  • Folie 6
  • Folie 7
  • Folie 8
  • Folie 9
  • Folie 10
  • Folie 11
  • Folie 12
  • Folie 13
  • Folie 14
  • Folie 15
  • Folie 16
  • Folie 17
  • Folie 18
  • Folie 19
  • Folie 20
  • Folie 21
  • Folie 22
  • Folie 23
  • Folie 24
  • Folie 25


Do'stlaringiz bilan baham:


Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2017
ma'muriyatiga murojaat qiling