Arbeitsblatt: Algorithmen und Problemlösen

Material-Details

Anhand eines Alltagsalgorithmus "Radwechsel" wird die Erarbeitung eines Algorithmus einschließlich Verfeinerung aufgezeigt. Verzweigungen und Schleifen werden einbezogen sowie die Umsetzung in JAVA (einschließlich Struktogrammdarstellung).
Informatik
Programmieren
11. Schuljahr
7 Seiten

Statistik

6809
4262
24
08.05.2007

Autor/in

BenutzerInnen-Konto gelöscht (Spitzname)
Land:
Registriert vor 2006

Downloads Arbeitsblätter / Lösungen / Zusatzmaterial

Die Download-Funktion steht nur registrierten, eingeloggten Benutzern/Benutzerinnen zur Verfügung.

Textauszüge aus dem Inhalt:

Algorithmen und Problemlösen (JAVA) Algorithmen und Problemlösen Automatisierte Datenverarbeitungsanlagen oder Computer können nur solche Aufgaben lösen, bei denen sich das Lösungsverfahren als Algorithmus angeben lässt. Algorithmen können mit Hilfe einer Programmiersprache computergerecht formuliert werden. Der Bearbeitung eines Problems durch einen Computer muss eine Zergliederung des Problems in seine Einzelschritte und eine Analyse der logischen Zusammenhänge vorangehen, es muss ein Algorithmus entwickelt werden. Was ist ein Algorithmus? Es keine allgemein verbindliche Definition dieses Begriffes. Eine einfache Beschreibung dieses Begriffes kann so aussehen: Einen Plan zum Lösen eines Problems mit Hilfe einer endlichen Folge eindeutiger und ausführbarer Schritte nennen wir Algorithmus. Wir wollen uns dies an einem Alltagsproblem klar machen: Ein Radwechsel beim Auto. Dieser Vorgang lässt sich durch folgende Schritte beschreiben: Hebe den Wagen mit einem Wagenheber an Schraube die Radmuttern ab Nimm das Rad herunter Setze das Reserverad auf Schraube die Radmuttern fest Senke den Wagen ab Man kann diesen Algorithmus noch wesentlich verfeinern, d.h. die einzelnen Schritte noch weiter in Teilschritte zerlegen (im Sinne des TOP-DOWN-Verfahrens). So könnte man beispielsweise angeben, dass das Werkzeug aus dem Kofferraum zu holen ist, wie der Wagenheber anzusetzen ist, dass die Radkappen (falls vorhanden) vor dem Abschrauben der Muttern zu entfernen sind usw. Wir wollen jedoch hier auf diese Einzelheiten verzichten. Zur übersichtlichen Darstellung komplizierter Algorithmen verwendet man graphische Hilfsmittel wie z.B. Struktogramme. Bei dieser Darstellungsform werden die einzelnen Anweisungen (oder zu Anweisungsblöcken zusammengefasste Anweisungen) in rechteckige Kästen geschrieben. Das Hintereinanderfügen der Rechtecke lässt sofort erkennen, dass die einzelnen Anweisungen hintereinander ausgeführt werden (Sequenz). Hat man ein nun ein erstes grobes Struktogramm erstellt, so versucht man es zu verbessern bzw. zu verfeinern. So ist zum Beispiel in dem Algorithmus für den Radwechsel vergessen worden zu prüfen, ob das Reserverad in Ordnung ist. Ist es platt, so wird man keinen Radwechsel vornehmen können, sondern stattdessen eine Werkstatt anrufen müssen. Eine solche Entscheidung muss in einem Struktogramm optisch besonders gekennzeichnet werden. man spricht von einem Entscheidungsfeld und gibt den zwei Altnernativfeldern die Bezeichnungen „dann und „sonst. Hier könnte auch die Begriffe „then und „else oder „ja und „nein verwendet werden. Mit einem Entscheidungsfeld sieht der Algorithmus dann folgendermaßen aus: -1Lind 2006 Algorithmen und Problemlösen (JAVA) Auch dieser Algorithmus lässt sich noch weiter verfeinern. So besteht die Anweisung „Schraube die Muttern ab in Wirklichkeit aus einer mehrfachen Widerholung der gleichen Tätigkeit, nämlich dem Abschrauben einer Mutter. Um Schreibarbeit einzusparen, verwendet man im Struktogramm das Symbol für die „do-while-Schleife. Bei diesem Schleifentyp wird der Schleifenkörper zunächst bedingungslos einmal abgearbeitet und am Ende wird überprüft, ob eine weitere Wiederholung des Schleifenkörpers erfolgen soll. Somit ergibt sich das folgende Struktogramm: Übungsaufgaben 1. Ein Puzzle, das aus vielen Teilen (n) besteht, soll so zusammengesetzt werden, dass am Ende ein geschlossenes Bild entsteht. Entwickeln Sie dazu einen geeigneten Algorithmus. 2. Entwerfen Sie einen Algorithmus für die Steuerung einer Ampelanlage an einer Kreuzung. Hier kreuzt die Nebenstraße die Hauptstraße A. Normalerweise soll grünes Licht haben. Wenn sich aber auf -2Lind 2006 Algorithmen und Problemlösen (JAVA) ein Fahrzeug der Kreuzung nähert, schaltet es einen Kontakt ein. Dadurch soll am Ende einer Zeiteinheit (z.B. 60 Sekunden Wartezeit) die Straße genau für eine halbe Zeiteinheit freigegeben werden. Kontrollstrukturen und Struktogramme Bei den meisten Algorithmen kommt es vor, dass man an manchen Stellen den weiteren Programmablauf von bestimmten Bedingungen abhängig macht. So darf man z.B. keine Wurzel aus einer Zahl ziehen, wenn diese einen negativen Wert besitzt. Ebenso kommt es vor, dass bestimmte Teile eines Algorithmus mehrfach durchlaufen werden, bis z.B. ein gewünschter Zustand erreicht ist. Zum Lösen solcher Probleme verwendet man Verzweigungen und Schleifen. Im Folgenden werden die Struktogramme sowie die entsprechenden Pascal- bzw. Delphi-Anweisungen dargestellt. Sequenz Werden bestimmte Schritte nacheinander bearbeitet, so spricht man von einer Sequenz. Programme, die nur Sequenzen enthalten, nennt man lineare Programme. Programmverzweigungen Einseitige Auswahl if () Anweisung; Zweiseitige Auswahl if () Anweisung 1; else Anweisung 2; Mehrfachauswahl switch () case Anweisung break; case Anweisung break; case Anweisung break; case Anweisung break; default: Anweisung; 1; 2; 3; N; -3Lind 2006 Algorithmen und Problemlösen (JAVA) Bemerkungen In der if-Struktur wird eine logische Bedingung abgefragt. Das sind Terme, die nur die Werte true (wahr) oder false (falsch) annehmen können. In der switch-Struktur wird eine Schaltervariable als Entscheidungskriterium herangezogen. Es muß sich dabei um eine Variable vom sklaren Typ handeln. D.h., die Wertemenge des Datentyps muss endlich sein und es muss zu jedem Wert einen Vorgänger bzw. einen Nachfolger geben, wie z.B. bei den Datentypen integer, char, byte usw. Bei allen Strukturen wird jeweils eine Anweisung ausgeführt. Möchte man mehrere Anweisungen ausführen, kann man diese mit „ und „ zu einer Anweisung „klammern. -4Lind 2006 Algorithmen und Problemlösen (JAVA) Programm-Schleifen DO- WHILE Schleife (fußgesteuerte Schleife) do Anweisung; while (); Der Schleifenkörper wird in jedem Fall mindestens einmal durchlaufen auch wenn die Wiederholungsbedingung von Anfang an falsch ist. Bei mehreren Anweisungen sind wie üblich Klammern ({ }) zu setzen. WHILE Schleife (kopfgesteuerte Schleife) while () Anweisung; Bei mehreren Anweisungen sind wie üblich Klammern ({ }) zu setzen. Der Eintritt in die Schleife erfolgt nur, wenn die wahr ist und wird auch nur solange ausgeführt. FOR Schleife for (Initialisierung; Wiederholungsbedingung; Inkrement) Die for-Schleife wird im Allgemeinen dann eingesetzt, wenn die Anzahl der Schleifendurchläufe bekannt ist. Die Schleifenvariable (Initialisierung) muss vom skalaren Datentyp sein (mit eindeutigem Vorgänger und Nachfolger wie z.B. die ganzen Zahlen). Für die for-Schleife gibt es kein eigenes Struktogrammsymbol. Da dieser Schleifentyp der while-Schleife entspricht, verwendet man auch deren Symbol. Beispiel: for (int i1; i