Lehrzeit

Schule & Informatik

Kategorie: Klasse 12 (Seite 1 von 3)

Programmieraufgabe 90

Aktuell bin ich bei meiner Zwölften beim Thema „Formale Sprachen“. Bislang haben wir über Grammatiken gesprochen und werden kommende Stunde dann die EBNF einführen, um uns so die Darstellung der Produktionen zu erleichtern.

Um ein Bedürfnis nach erleichterter Schreibweise ein wenig zu motivieren, haben wir bislang die Produktionen in der Form

  1. <Variable1> -> <Variable2>a
  2. <Variable1> -> <Variable2>b
  3. <Variable2> -> a

aufgeschrieben und dann zusehends schwierigere Aufgaben formuliert. Angefangen hatten wir noch mit den Bezeichnungen der S- und U-Bahnen in München:

  1. <Start> -> S<Ziffer>
  2. <Start> -> U<Ziffer>
  3. <Ziffer> -> 1
  4. <Ziffer> -> 2
  5. <Ziffer> -> 3
  6. <Ziffer> -> 4
  7. <Ziffer> -> 5
  8. <Ziffer> -> 6
  9. <Ziffer> -> 7
  10. <Ziffer> -> 8
  11. <Ziffer> -> 9

Aber schon bei den KFZ-Kennzeichen wird es schwierig. Vor allem, weil dann doch viele unterschiedliche Lösungen von Produktionen vorhanden waren und nicht jedem immer klar war, warum seine Lösung denn nun richtig ist oder nicht.

Aufgabe

Schön wäre es daher gewesen, wenn es eine Möglichkeit gäbe, sozusagen alle erzeugbaren Wörter einer Grammatik ausgeben zu lassen.

Ein großes Problem sind allerdings die rekursiven Definitionen bei den Regeln. So werden Palindrome beispielweise wie folgt erzeugt:

  1. <Palindrom> -> ε|<Zahl>|0<Palindrom>0|1<Palindrom>1|2<Palindrom>2…|9<Palindrom>9
  2. <Zahl> -> 0|1|2|3|4|5|6|7|8|9

Die Rekursion in der Regel führt dabei zwangsläufig irgendwann zum Absturz StackOverflow des Programms.

Um dies zu verhindern, beschränke ich die Anzahl der Rekursionen händisch.

Bei den die Produktionen für KFZ-Kennzeichen mache ich es ähnlich:

  1. Landkreis -> Grossbuchstabe | Grossbuchstabe Grossbuchstabe | Grossbuchstabe Grossbuchstabe Grossbuchstabe

Und das Problem der ODER-Verknüpfung löse ich so, dass ich per Zufall eine der Möglichkeiten auswähle: JavaScript.

Welche bessere Möglichkeit gäbe es, um möglichst alle bzw. viele Wörter einer Grammatik zu erzeugen? Ich denke da vor allem noch an Bäume. Wobei ich beim Durchlauf-Algorithmus noch schwanke. Denn einfach alle Blätter ausgeben wäre nicht sinnvoll.

Informatikaufgabe 82

Vor kurzem erhielt ich per Email folgende Frage, die ich hier nur verkürzt und sinngemäß darstellen möchte:

Ich habe 53 Spieler, die paarweise gegeneinander spielen sollen. Nach Ihrer Internetseite sind das 1378 Paarungen, so dass am Ende jeder gegen jeden mal gespielt hat. Jetzt sollen an jedem Tag jeweils die Paarungen so gebildet werden, dass es zu keinen Dopplungen kommt.

Jetzt kenne ich aus der 11. Klasse Informatik nur eine mögliche Lösung für ein KO-Spielsystem, die ich zunächst als Antwort zurückschickte:

Sie mischen alle Teilnehmer zufällig (das ginge z.B. auch mit Excel und einer Liste). Dann ziehen Sie von vorne (Kopf der Warteschlange) immer zwei aufeinanderfolgende Karten. Das wäre das erste Paar. Dann die nächsten zwei etc. Der Gewinner einer Paarung wird jeweils wieder unter den hinten an die Warteschlange angehängt So reduzieren sich die Karten schrittweise bis ein Gewinner feststeht.

Was aber gemeint war, war ein sogenanntes Rundenturnier (Round-Robin). Da die Organisation dabei gar nicht so einfach ist (z.B. durch eine beschränkte Anzahl an Plätzen wie bei Tennisturnieren) kann eine Lösung relativ kompliziert werden. Zum Glück hat sich jemand schon einen Kopf gemacht und die Internetseite turniereditor.de geschaffen. Hier lassen sich schonmal solche Rundenturniere auswerten. Auch die Internetseite www.oxfordcroquet.com/manage/roundrobin/ ermöglicht eine solche Organisation. Aber wie programmiert man so etwas?

Hierzu bedient man sich des Scheduling-Algorithmus. Dieser läuft wie folgt ab: Angenommen alle Spielernamen stünden auf Karten. Lege alle Karten so in zwei Reihen, dass in der oberen und unteren Reihe genau gleich viele Karten liegen. Bei einer ungeraden Anzahl wird ein Joker ergänzt. Der entsprechende Spielpartner hätte dann quasi frei. Bei 10 Spielern (A bis J) ergäbe sich folgendes Bild:

A-B-C-D-E
F-G-H-I-J

Hiermit ergeben sich als erste Paarung A-F, B-G, C-H, D-I, E-J. Für die weiteren Paarungen bleibt A an der Position fest und alle anderen Karten werden im Uhrzeigersinn um 1 weiter geschoben

A-F-B-C-D
G-H-I-J-E

Die neuen Paarungen wären dann A-G, F-H, B-I, C-J und D-E. Das macht man solange bis die Ausgangssituation wieder hergestellt ist.

Damit wäre auch die Programmieraufgabe klar:

Programmieraufgabe

Implementiere den oben dargestellten Scheduling-Algorithmus für ein Round-Robin-System.

 

Programmieraufgabe 80

Zum Thema Semaphoren, Monitore und Threads kann man selbstverständlich auch schöne Aufgaben stellen. Deswegen mal wieder eine Aufgabe besonders weil es ja auch den ein oder anderen Faschingsmuffel gibt, der noch keine Vorwand hat sich zu verstecken.

Aufgabe

Schreibe unter Ausnutzung von Threads eine Biathlon-Simulation. Jeder Biathlet agiert als eigener Thread. Das Laufen auf der Strecke wird durch ein zufällig langes Warten des Threads simuliert. Das Schießen (liegend, stehend) kann entweder als zufällige Wartezeit simuliert werden oder man implementiert den Schießstand oder sogar die einzelnen Schießstände als Semaphore. Der Zieleinlauf muss aber als Monitor mit der Sempahore rang (beginnend bei 1) implementiert werden, um ein eindeutiges nacheinander Einlaufen ins Ziel zu gewährleisten.

Und wem das nicht reicht, der kann ja noch einen Staffellauf implementieren.

Ältere Beiträge

© 2018 Lehrzeit

Theme von Anders NorénHoch ↑