Lehrzeit – Seite 84 – Schule & Informatik

Informatikaufgabe 50

Das erste Jubiläum! 50 Aufgaben sind es nun schon und es ist keine Ende in Sicht.

Basis der heutigen Aufgabe ist die freie Software Lilipond. Lilipond ist eine Software oder besser Compiler, der eine Textdatei in Noten umwandelt.

Eine weitere Basis der Aufgabe ist die Kanon in D-Dur von Pachebel:

Diese Formel C, Am, F, G ist eine der meistverwendeten Formeln im Pop.

Warum das so ist? Ich versuchs mal so zu erklären:

In der Formel sind die Akkorde der wichtigsten Kadenz (1,4,5) enthalten: Tonika (1), Subdomimante (4), Dominante (5) und die Mollparallele (6 Moll). In diesen vier Akkorden sind alle Töne der Tonart enthalten. Dabei genügen meist die 3 Hauptakkorden (T, SD, D). In obigem Beispiel C, Am, F, G ist C die Tonika, Am die Mollparalle, F die Dominante und G die Subdominante. Drückt man es in Tonstufen aus, so lautet die Formel: I – IV – V – VIm.

Weiter bleiben bei den Akkordwechsel viele Töne liegen. Der C-Akkord besteht aus den Tönen C-E-G. Am besteht aus A-C-E. C-E bleiben also. Wechselt man von Am auf F (F-A-C) so bleiben A-C erhalten.

Und hier noch ein paar Beispiele:

Und auf der Ukulele wird es dann noch mal einfacher, da ja nur 4 Saiten vorhanden sind. Im folgenden Beispiel ist allerdings nicht C-Dur die zugrundeliegende Tonleiter, sondern F-Dur (in engl. Schreibweise gibt es keine H, sondern nur B und Bb. Bb entspricht dabei unserem B): F-G-A-Bb-C-D-E-F. Zusammen mit der Formel I – IV – V – VIm von oben erhält man die Akkordfolge: F – Bb – C – Dm oder auch F – C – Dm – Bb wie in dem Video.

Und zu guter letzt

Die Formel 1-4-5, in C-Dur also C-F-G, eventuell mit der Mollparallelen Am am Ende ist also die Basis für viele Stücke. Lässt man jetzt die Mollparallel Am weg und nimmt statt 4, also F, die 2 in der Moll-Variante, so erhält man die Jazz Standardformel 2-5-1: Dm-G-C.

Man kann statt C-F-G auch C-Dm-G nehmen oder sogar zu C-Am-Dm-G erweitern. Man erhält die 16-25 Formel.

Aufgabe
Schreibe ein Programm, das auf Basis der Pechebel-Formel C, Am, F, G und den Grundtönen der C-Dur-Tonleitern ein einfaches Lied in der Sprache von Lilipond in eine Datei schreibt.
Beachte dabei, dass das Lied vielleicht am besten mit dem C-Akkord anfängt und aufhört.
Teste dann deine Datei in Lilipond und, wenn möglich, spiele das Stück. Leider gibt es kein freies Programm, das diese Art der Musik-Information direkt in hörbare Musik umsetzt. Tux-Guitar kann zwar Lilipond-Datei erzeugen, aber nicht importieren.

Informatikaufgabe 49 – Turnierplanung

Die heutige Aufgabe stammt von einem Schüler meiner aktuellen elften Klasse. Da mir bei der Diskussion mit dem Schüler mehrere Lösungen eingefallen sind, möchte ich hier ein paar Lösungen präsentieren.

Aufgabe
In einem Turnier sollen n Spieler gegeneinander antreten. Dabei soll jeder gegen jeden spielen, wer am Schluss am meisten Punkte hat, gewinnt.
a) Wie viele Spiele gibt es?
b1) Implementiere eine Lösung nur mit Hilfe von eindimensionalen Feldern.
b2) Implementiere eine Lösung auf Basis von Graphen.
b3) Wie ließe sich das Problem mit Excel oä. lösen

Die Frage b3) kommt urspünglich von meinem Schüler, daher habe ich sie mit aufgelistet. Allerdings fällt mir nur eine Lösung mit Hilfe von VBA ein, daher kann man auch gleich einen allgemeinen Ansatz versuchen. Jetzt aber zu ein paar Erklärungen:

zu a): Ein rein kombinatorisches Problem aus der Mathematik. Jeder der n Spieler spielt gegen einen der n-1 anderen Spieler. Dabei gibt es keine Unterscheidung, ab Spieler A gegen B oder B gegen A spielt: n*(n-1)/2

zu b1) Die Spielernamen A, B, C, … seien in einem Feld (Array) gegeben:

spieler = [A,B,C,D,E]

Mit Hilfe des Feldes spieler wird ein zweites Array mit Paarungen gebildet:

paarungen = [(A,B), (A,C), (A,D), (A,E), 
             (B,C), (B,D), (B,E), 
             (C,D), (C,E), 
             (D,E)]

Das Feld paarungen wird durch einen beliebigen Algorithmus gemischt.

paarungen = [(B,E), (A,C), (A,E), (A,D), 
             (B,C), (B,D), (A,B), 
             (C,D), (D,E), 
             (C,E)]

Dann kann von vorne (oder auch hinten) beginnend eine Paarung aus dem Array entfernt werden. D.h. die erste Partie wäre: (B,E), dann (A,C) . E kann erstmal nicht spielen. Im nächsten Durchgang kommt dann (A,E) dran und dann kommt das Problem bei dieser Lösung: Die Partie (A,D) muss übergangen werden, da a ja schon belegt ist. Als nächstes wäre damit (B,C) dran. Das geht dann immer so weiter.

zu b2) Fasst man das ganze als Graph (unser aktuelles Thema, daher bin ich wohl auch erst mal auf diese Lösungen gekommen) auf, so gehen von Spieler A vier Kanten zu den Spielern B, C, D, E. Von B gehen Kanten zu C, D, E. Eine Kante zu A braucht man nicht mehr, da diese Kante ja von A aus gezogen wurde.

Um nun das Spiel zu organisieren, wählt man bei A eine belibiege Kante, zum Beispiel die zu B. Dann müssen alle anderen Kanten, die von A oder B ausgehen als blockiert gemerkt werden, da dies andere mögliche Partien sind, die sich aber im Moment nicht realisieren lassen (s. Problem bei b1) ). Man könnte aber auch die Knoten A und B als schon benutzt markieren. Der nächste freie Knoten wäre dann C, der seinen Partner in D findet. Beide werden wieder markiert. E muss dann am Schluss noch warten.

Sind alle Spiele beendet, werde die Kanten, die die gemachten Spiele symbolisieren gelöscht.

Binärbaum 2

In den Ferien habe ich die Zeit gefunden, meine Implementierung eines binären Suchbaums mi grafischer Ausgabe mal ein bisschen zu optimieren. In meiner ersten Lösung gefiel mir nicht, dass der Baum, auch wenn er sehr leer ist, teilweise recht breit wurde.

Um das nun in den Griff zu bekommen, habe ich unterschiedliche Ansätze überdacht.

IDEE: Der Baum wird von den Blättern aus aufgebaut und zwar beginnend bei den “tiefsten”. Dabei muss man wissen, wie viele Blätter es gibt, entsprechend habe ich die maximale Breite des Baums. Dann beginnt man mit den tiefsten, also den Blättern, die am Weitesten von der Wurzel entfernt sind und geht dann ebenenweise nach oben durch.
KRITIK: Dieses ebenenweise Durchlaufen – entspricht einer Breitensuche – von unten machte mir aber am meisten Probleme. Auch, weil ich keine weiteren Detailinformationen über die Knoten, wie Ebenentiefe, speichern wollte.
IDEE: Ich betrachte die Knoten als elektrische Ladung, die sich abstoßen. Jeder Knoten würde sich dann “selbstständig” eine energetisch günstige Position suchen.
KRITIK: Ich müsste die Knoten in Threads packen, die sich wie die Partikel in einer Physik-Engine slebstständig und permanent anpassen. Das war mir dann doch zu viele des guten.
und realisierte IDEE: Nur echte, innere Blätter mit zwei Kindern benötigen Platz. Alle Anderen hängen senkrecht untereinander. Ich schaue also, ob ich beim Zeichnen in einem inneren Knoten bin. Wenn ja, dann schau ich, wie viele weitere innere Knoten in den beiden Teilbäumen noch kommen. Kommt keiner, so brauchen die beiden Kinder nicht besonders weit auseinanderhängen. Andernfalls hängt die Weite der aktuellen Kinder von der Anzahl der in den beiden Teilbäumen vorkommenden inneren Knoten ab.
KRITIK: Das Ganze funktioniert zu 95% gut. Nur bei sehr merkwürdigen Bäumen kann es mal zu Problemen kommen und die Knoten stehen über- und durcheinander (Knoten 37 beachten!).

Wer sonst noch eine schöne Implementierung oder Idee hat. Immer her damit. Es sollte allerdings so sein, dass ich das im Rahmen des Schulunterrichts von und mit den Schülern umsetzen lassen kann.

Nachträgliche Ergänzung: Quellcode: binarbaum7_grafik2.