Lektion 6 Algorithmen

Lektion 6 Algorithmen Titelbild

Lektion 6

Algorithmen

Lernziele
  • Du kannst Arrays benutzen
  • Du kannst deine eigenen Funktionen schreiben
  • Du weißt, was ein Algorithmus ist
  • Du weißt wie du einen Sortier-Algorithmus schreiben kannst

Also dann aber mal los!

Variablen sind toll. Das kann schon mal so gesagt werden. Wir müssen zwar immer darauf achten, was für ein Typ sie haben, aber sonst sind sehr gut in ihrer Sache, Dinge einfach zu speichern. Doch manchmal reicht das nicht.

Mit einem Array haben wir die Möglichkeiten, mehrere Werte auf einmal zu speichern.

int meineZahlen[] = {1,3,4};

Damit wir auch auf jeden Wert zugreifen können, bekommt jeder Wert eine Indexnummer. Diese Nummerierung geht von links nach rechts und fängt bei 0 an! Das heißt, mit dem folgenden Befehl können wir einfach die 3 ausgeben:

Serial.println(meineZahlen[1]);

Wenn wir am Anfang noch nicht wissen, welche Zahlen wir speichern wollen, können wir das auch einfach lassen:

int meineZahlen[3];
meineZahlen[0] = 1;
Serial.println(meineZahlen[0]);

Es sollte bei dir jetzt wieder 0 ausgegeben werden. Hier handelt es sich wieder um ein Beispiel, welches so natürlich nicht direkt in einem Arduino Programm funktioniert. In den [] können wir über das Angeben der Indexzahl die einzelnen Werte abrufen. Wenn du das Array am Anfang ohne Werte initialisierst, wie in Zeile 1, musst du dem Programm noch die maximale Anzahl der Werte übergeben. Das machst du mit den eckigen Klammern. Natürlich kannst du auch die anderen Datentypen benutzen, bei denen gilt das Gleiche!

Aber wofür brauchen wir Arrays? Hier gibt es ein kleines Beispiel!

345.png
Anschlüsse am Arduino Anschlüsse LEDs
13 Langes Bein LED1
12 Langes Bein LED2
11 Langes Bein LED3
10 Langes Bein LED4
9 Langes Bein LED5
int leds[5] = {13,12,11,10,9};

void setup(){
  for(int i = 0; i<=4;i++){
     pinMode(leds[i], OUTPUT); 
  }
}

void loop(){
  for(int i = 0; i<=4;i++){
     digitalWrite(leds[i], HIGH); 
     delay(200);
  }
  for(int i = 4; i>=0;i--){
     digitalWrite(leds[i], LOW); 
     delay(200);
  }
}

In der ersten Zeile werden die I/O Pins, an denen die LEDs angeschlossen sind, definiert. In der setup()-Funktion wird der Pinmode von allen I/O Pins festgelegt. Mit der for()-Schleife und dem Array geht das sehr einfach. Wir müssen der for()-Schleife nur sagen, bis zu welcher Zahl diese zählen soll. Da es insgesamt fünf I/O Pins in der Liste gibt, wir aber schon bei 0 anfangen zu zählen, geben wir als Startwert 0 an und als Bedingung, dass die Schleife solange weiter läuft, bis sie bei 4 angekommen ist.

In Zeile 10 mache wir das Gleiche mit der 2. for()-Schleife, nur dass diesmal die LEDs angeschaltet werden. In Zeile 14 werden dann nach und nach die einzelnen LEDs wieder ausgeschaltet, indem diesmal der Startwert bei 4 liegt. Dann fängt das ganze wieder von vorne an.

Die erste eigene Funktion

Wir haben schon viel über Funktion geredet und vor allem schon diverse Funktionen eingesetzt. Deswegen ist es doch mal an der Zeit, dass du anfangst, deine eigene Funktion zu schreiben. Wir haben da mal ein kleines Schema vorbereitet:

354.png

Zuerst muss der Typ der Funktion definiert werden, denn wirklich alles hat einen Datentyp. Aber für Funktionen gibt es eine Ausnahme. Mit void meineFunktion(){ kann eine Funktion erstellt werden, die keinen Rückgabewert hat. Nach dem Erstellen des Datentyps muss noch ein Name gewählt werden. Wenn wir das geschafft haben, gibt es noch die Möglichkeiten, dass bestimmte Werte übergeben werden müssen und auch bei diesen Werten muss der Datentyp übergeben werden. Danach sind die ganzen Formalitäten erledigt und es gibt endlich mehr Freiraum. Zwischen den geschweiften Klammern {} findet dann die Logik der Funktion statt. Die letzte und wichtige Besonderheit ist, dass wir mit return 6; einen Wert oder eine Variable zurückgeben können. Wir müssen nur darauf achten, dass diese auch den gleichen Datentyp hat, wie am Anfang definiert wurde. Also los, auf ein kleines Programm als Beispiel. Diesmal müsst ihr nichts an den Arduino anschließen.

void setup(){
  Serial.begin(9600);
}

 void hello(String name){
   Serial.print("Moin Moin ");
   Serial.print(name);
   Serial.println(" Wie geht es dir?");
 }

void loop() {
 String benutzer = "JP-Krake";
 hello(benutzer);
 delay(1000);
}

In Zeile 5 definieren wir die erstellte Funktion. Da sie nichts zurück gibt, wird der void ausgegeben. Die Funktion hat den Namen hello und bekommt nur einen Wert übergeben, einen String, der im restlichen Programm als name referenziert ist. In Zeile 6-8 läuft das Herzstück des Programmes und es wird einfach nur eine Botschaft ausgeben.

In Zeile 13 wird endlich die Funktion hello() aufgerufen und der Wert benutzer übergeben. Damit alles nicht zu schnell läuft gibt es in Zeile 14 noch Pause von einer SEkunde.

Falls du noch nicht überzeugt bist, haben wir hier noch vier gute Gründe für Funktionen:

  • Funktionen helfen, dass Programme organisiert sind.
  • Eine Funktion hat eigentlich immer eine bestimmte Aufgabe. Diese eine Funktion muss nur einmal entwickelt werden. Dadurch sinken Entwicklungskosten und die Sicherheit steigt.
  • Durch die wiederholte Benutzen von Programmcode werden die Programme kleiner und sind leichter zu pflegen.
  • Funktionen können viel einfacher in anderen Programmen benutzt werden. Dadurch werden Programme modularer und für außenstehende einfacher zu benutzen.

Als Algorithmus wird eine genau definierte Handlungsvorschrift zur Lösung eines Problems verstanden. In unser heutigen Zeit nutzen wir Algorithmen meist, um verschiedenste Probleme unseres Alltags von Maschinen lösen zu lassen. Da Maschinen, so wie dein Computer eine ist, nicht selbstständig denken können, muss ein Algorithmus so genau formuliert sein, dass es beim Abarbeiten zu keinen Missverständnissen kommen kann.

Ein Beispiel, das oft dazu herhalten muss zu klären, wie ein Algorithmus funktioniert, ist folgendes: Wir geben einem Roboter die Aufgabe, uns einen Stapel Pfannkuchen zu backen. Da der Roboter ganz schön blöd ist, müssen wir natürlich erst einmal erklären, wie man Pfannkuchen backt. Der Vorteil an der ganzen Sache ist, haben wir dem Roboter einmal verständlich erklärt, wie man Pfannkuchen herstellt, ohne die ganze Küche in die Luft zu jagen, müssen wir es ihm nie mehr erklären und wir können uns auf einen Überfluss an Pfannkuchen für unser restliches Leben einstellen.

Der Haken an der ganzen Sache ist allerdings, dass es nicht ganz so leicht ist, wie vielleicht gedacht, so ein komplexes Kochrezept mit Anweisungen unmissverständlich zu formulieren.

Bei der Formulierung und der Anwendbarkeit eines Algorithmus muss man einige Regeln betrachten.

Endlichkeit: Ein Algorithmus besteht aus endlich vielen Anweisungen. Er muss also irgendwann zu Ende gehen und seine Aufgabe erfüllt haben. Eindeutigkeit: Mit jeder Anweisung eines Algorithmus ist auch die nachfolgende Anweisung festgelegt. Das bedeutet, ein Algorithmus arbeitet seine Handlungsanweisungen nicht willkürlich ab, sondern muss nach jedem Schritt genau wissen, welcher Schritt als nächstes kommt. (Ausführbarkeit) Allgemeingültigkeit: Ein Algorithmus muss auf alle Aufgaben des gleichen Typus anwendbar sein.

Beispiele und gegen Beispiele für Algorithmen: Reparieren eines kaputten Motors Für dieses Beispiel ist es möglich, einen Algorithmus zu schreiben. Der Algorithmus checkt alle Teile eines Motors elektronisch durch, lokalisiert die kaputte Komponente und je nachdem in welchem Jahr wir leben, kann der ausführende Roboter das Teil auch gleich noch auswechseln.

Schreiben eines Romans Hierfür gibt es keinen Algorithmus. Die Prinzipien der Allgemeingültigkeit und Eindeutigkeit werden verletzt.

Beispiel Algorithmus

Jetzt gibt es viele Algorithmen, von der Google Suche bis hin zum Algorithmus, welcher dir vorschlägt, welche anderen Filme/Eissorten dir eventuell noch gefallen könnten. Aber so ein Suchalgorithmus zu erstellen ist ein wenig kompliziert, deswegen wollen wir erst einmal einen Sortieralgorithmus erstellen. Der Algorithmus bekommt ein Array mit einzelnen Zahlen. Diese sollen der Größe nach geordnet werden. Ganz Links soll also die niedrigste Zahl und ganz rechts die höchste Zahl stehen.

Bevor wir anfangen, näher darauf einzugehen, welche Möglichkeiten es gibt, bist du dran. Wie würdest du es versuchen? Das Programm dafür müsste ungefähr so aussehen:

int zahlen[13] = {13, 2, 9, 10, 6, 11, 7, 0, 3, 4, 5, 1, 8}; 
void setup(){
  Serial.begin(9600);
}

void sortieren(int a[], int anzahlWerte) {
  //Dein Sortier Alorithmus
}

void loop() {
  sortieren(zahlen,13);
  Serial.print("Sortierte Liste: ");
  for(int i=0; i<13; i++) {
    Serial.print(zahlen[i]); 
    Serial.print(",");
  }
  delay(10000);
}

Auflösung

Eine Möglichkeit wäre der sogenannte Bubble Sort Algorithmus!

int zahlen[13] = {13, 2, 9, 10, 6, 11, 7, 0, 3, 4, 5, 1, 8}; 

void setup(){
  Serial.begin(9600);
}

void zahlenAnzeigen(){
  for(int i=0; i<13; i++) {
    Serial.print(zahlen[i]); 
    Serial.print(",");
  }
  delay(600);
  Serial.println();
}

void loop() {

  sortieren(zahlen,13);
  Serial.print("Sortierte Liste: ");
  zahlenAnzeigen();
  delay(10000);
}
void sortieren(int a[], int anzahlWerte) {
  for(int i=0; i<(anzahlWerte-1); i++) {
    for(int o=0; o<(anzahlWerte-(i+1)); o++) {
      if(a[o] > a[o+1]) {
        int t = a[o];
        a[o] = a[o+1];
        a[o+1] = t;
      }
      zahlenAnzeigen();
    }
  }
}

Wir haben hier nicht nur diesen Sortier-Algorithmus eingebaut, sondern auch noch gleich eine zweite Funktion, mit der die einzelnen Veränderungen in der Liste gleich dargestellt wird. Das hilft vor allem beim Verständnis.

Aber jetzt zum Sortier-Algorithmus. Wichtig ist, dass wir nicht nur eine Liste mit Zahlen haben, sondern auch wissen, wie groß diese ist. Dafür wird ein zweiter Wert übergeben. In der Funktion gibt es zwei for()-Schleifen, die erste wiederholt sich so häufig, wie es Werte in der Liste gibt. Das Grundprinzip des Bubble Sort Algorithmus ist, dass von vorn nach hinten durchgegangen wird und es dabei immer einen Vergleich gibt, welche Zahl größer ist. Das heißt, ganz am Anfang wird die Zahl an Position 1 mit der an Position 2 verglichen. Die größere Zahl wird dann weiter nach rechts geschoben. Danach wird Position 2 mit Position 3 verglichen und wieder wird die größere Zahl nach rechts verschoben. Am Ende ist der Wert, welcher in Position in 13 ist, der größte Wert. Danach geht es wieder von vorn los, der Unterschied liegt jetzt aber in der zweiten for()-Schleife. for(int o=0; o<(anzahlWerte-(i+1)); o++) { o fängt wieder bei 0 an, aber die Bedingung geht nur bis o<(anzahlWerte-(i+1)) bei einem Anfangswert von 13 geht es dann in der zweiten "Runde" nur bis 11. Mehr ist aber auch gar nicht nötig, denn am Ende der ersten Runde ist in der 13. Position schon die größte Zahl. Das heißt, jede Runde werden die Zahlen der Größe nach aufgeteilt.

  1. Erstelle eine Liste mit 5 Namen
  2. Wie ist die grundlegende Struktur eines Arrays?
  3. Ist der vorgestllte Bubble Sort Algorithmus wirklich ein Algorithmus?
  4. Nach welchen Aspekten würdest du klassifizieren, wie gut ein Sortier-Algorithmus ist?
  5. Wir würdest du einen Rückgeld-Algorithmus bauen, der versucht, möglichst wenig Münzen/Scheine zurückzugeben? Schreibe zuerst einen Ablaufplan auf und dann versuche selbst einen zu programmieren.

Noch Fragen oder Feedback?

Bevor du eine Frage stellen kannst musst du dich zuerst Anmelden oder Regestrieren!