Algorithmen
(EN google-translate)
(PL google-translate)
- Algorithmen sind schrittweise Anleitungen, wie von einem Ausgangspunkt beginnend ein bestimmtes Ergebnis erzielt werden kann.
- Ich stehe beispielsweise vor dem Automaten am Bahnhof und möchte einen Schokoriegel.
- Der Algorithmus lautet dann:
|
- Für Schokoriegel entscheiden,
- Preis ablesen und entsprechendes Kleingeld einwerfen,
- Nummer ablesen und diese eintippen.
|
Primzahlen finden: Das Sieb des Erastosthenes
- Das Konzept "Algorithmus" ist seit der Antike bekannt.
- Beispielsweise gibt es einen antiken Algorithmus alle Primzahlen in einem Intervall 2..n zufinden, das Sieb des Eratosthenes:
|
- Nimm im geordneten Intervall die erste Zahl als Primzahl p.
- Streiche alle darauffolgenden ganzzahligen Vielfachen k*p von p.
- Gehe zurück zu 1.
|
- Übrig bleiben alle Primzahlen in dem gegebenen Intervall.
- Beispiel dazu (Die Streichungen erfolgen durch Null setzen!):
|
2 3 4 5 6 7 8 9 10 11 12 13 14
0 3 0 5 0 7 0 9 0 11 0 13 0 => 2
0 0 0 5 0 7 0 0 0 11 0 13 0 => 3
0 0 0 0 0 7 0 0 0 11 0 13 0 => 5
0 0 0 0 0 0 0 0 0 11 0 13 0 => 7
0 0 0 0 0 0 0 0 0 0 0 13 0 => 11
0 0 0 0 0 0 0 0 0 0 0 0 0 => 13
Code 0-1: Beispiel zum antiken Algorithmus zur Primzahlensuche in einem Intervall 2..n mit n=14.
Das können sowohl bestimmte Darstellungsmethoden sein,
als auch die Einführung in bestimmte Entwicklucngswerkzeuge und
schließlich die Beschreibung möglicher Praktiken, die die Erfolgsaussichten
bei der Entwicklung von Software erhöhen.
Terminieren eines Algorithmus'
- Endet ein Algorithmus nach endlichen Schritten, sagt man, dass er terminiert.
- Um benutzbare Computerprogramme zu schreiben, ist es wichtig, sich Klarheit darüber zu verschaffen, ob ein Algorithmus nach einer vertretbaren Zeit seine Arbeit mit einem positiven Ergebnis beendet.
- Im Fall des Siebs des Erastosthenes sollte eine Anweisung hierzu ergänzt werden, beispielsweise diese:
|
- Beende die Suche, wenn alle Array-Elemente Null geworden sind.
|
#include <iostream>
using namespace std;
#define N 1000 //Höchste Zahl im zu untersuchenden Intervall.
int main(void)
{
//int array[] = {2,3,4,5,6,7,8,9,10,11,12};
int array[N-1];
int anzahl = sizeof(array)/sizeof(int);
for(int i=0;i<anzahl;i++)
array[i]=2+i;
for(int i=0;i<anzahl;i++)
{
if(array[i]!=0)
{
//Erstes nicht durchgestrichenes Element ausgeben
cout<<array[i]<<endl;
//Alle nachfolgenden ganzen Vielfachen der aktuell gefundenen Zahl löschen:
for(int k=i+1;k<anzahl;k++)
{
//Wenn die Zahl bei array[k] ganzzahliges Vielfaches der aktuell gefundenen ist,
//dann setze auch diese auf Null:
if(array[k]%array[i]==0)
{
array[k]=0;
}
}
}
}
return 0;
}
Code 0-2: Beispielimplementierung zum Sieb des Erastosthenes.
Zahlen der Größe nach sortieren: Bubble-Sort
- Ein häufig auftretendes Problem in der Informatik besteht darin, Ordnung in Daten zu bringen.
- Beispielsweise kann gefordert sein, Zahlen in einem Array der Größe nach zu sortieren.
- Um Zahlen sortiert in aufsteigender Reihenfolge zu erhalten, kann der folgende Algorithmus (Bubble-Sort) verwendet werden:
|
- Gehe alle benachbarten Paare a und b in dem zu sortierenden Array in natürlicher Reihenfolge durch und vertausche sie, falls gilt a>b.
- Führen die Anweisung bei 1. sol lange wiederholt aus, bis kein Paar a>b mehr gefunden wird.
|
- Anweisung zwei dient zur Terminierung des Algorithmus'
- Hier ein Beispiel zur Anwendung:
|
1. Durchlauf:
2 5 3 7 1 9 8
2 3 5 7 1 9 8
2 3 5 1 7 9 8
2 3 5 1 7 8 9
2. Durchlauf:
2 3 1 5 7 8 9
3. Durchlauf:
2 1 3 5 7 8 9
4. Durchlauf:
1 2 3 5 7 8 9
5. Durchlauf:
Terminiert, weil kein Fall von a>b mehr gefunden wird.
Code 0-3: Beispiel zu Bubble-Sort
Da bei Anwendung dieses Algorithmus' die kleinen Zahlen wie Luftblasen im Wasser langsam "nach oben", bzw. nach links wandern,
hat sich der Name "Bubble-Sort" für diesen Algorithmus etabliert.
- Es existieren eine Vielzahl an Sortieralgorithmen.
- Ein wichtiges Maß zu ihrer Beurteilung ist, wie die Anzahl der notwendigen Sortierschritte s im Mittel von der Anzahl der zu sortierenden Zahlen abhängt.
- Es existieren Algorithmen, die zwar sehr leicht zu verstehen sind, aber sehr ineffizient sind, wie Bubble-Sort und im Gegenteil Algorithmen, die schwerer zu verstehen und zu implementieren sind, aber wesentlich effizienter sind.
|
#include <iostream>
using namespace std;
int main(void)
{
int arrayalt [] = {5,2,3,7,1,9,8};
int anzahlalt = sizeof(arrayalt)/sizeof(int); //Bestimmung der Anzahl der Array-Elemente
cout<<"Array alt: ";
for(int k=0;k<anzahlalt;k++)
{
cout<<" "<<arrayalt[k];
}
cout<<endl;
bool gefunden = true;
while(gefunden)
{
gefunden = false;
for(int i=0;i<anzahlalt-1;i++)
{
if(arrayalt [i]>arrayalt [i+1])
{
int h = arrayalt [i];
arrayalt [i]=arrayalt [i+1];
arrayalt [i+1]=h;
gefunden=true;
}
}
}
cout<<"Array neu: ";
for(int l=0;l<anzahlalt;l++)
{
cout<<" "<<arrayalt[l];
}
cout<<endl;
return 0;
}
Code 0-4: Beispielimplementierung zu Bubble-Sort.