Lehrzeit

Schule & Informatik

Monat: Februar 2013 (Seite 1 von 3)

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.

  1. 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.
  2. 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.
  3. 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.

Die Persönlichkeit macht den Unterschied

Gestern gab es noch einen interessanten Artikel in der SZ – über Lehrer. Und das einzige Ziel des Artikels war es, den Lehrer einmal so richtig zu loben.Eine stichwortartige Zusammenfassung:

  • Klassengröße spielt keine Rolle
  • Medien spielen kaum eine Rolle
  • In den Ministerien und Universitäten sitzen entweder nur Theoretiker oder Personen, die sich an ihr eigenes Unterrichten nicht mehr erinnern können.
  • Den „alt“-eingesessenen Professoren fällt damit nichts mehr ein.
  • Und die Ministerien greifen das auf und verpacken das in pseudopädagogische Worthülsen (Auszug):

    Wichtig ist demzufolge die „Schaffung einer positiven Lernkultur“, wobei man als Pädagoge die „resourcenorientierte Beratung auf systemisch-lösungsorientierter Basis“ und das „bedarfsorientierte Training nach dem Mini-Max-Prinzip“ genauso wenig aus dem Blick verlieren soll wie die „Vermittlung lernstilorientierter Strategien“, wobei da wiederum insbesondere „metakognitive Kontrollstrategien“ sowie „motivational-volitionale Stützstrategien“ von Bedeutung zu sein scheinen.

  • Koreanische Ansätze sind auch keine Lösung – zu viele Selbstmorde.
  • Finnische Ansätze sind auch keine Lösung – zu viel Schule, das wäre bei uns nicht finanzierbar.
  • Schüler als Person wahr und ernst zu nehmen, ist wichtig.
  • Gespräche mit Eltern sind schwierig, da diese die Schule oft nur als Dienstleister sehen.

Das einzig wirkliche Problem aller Lehrer und das sich wirklich alle Lehrer wünschen, ist: Zeit!

  • Zeit zum Vorbereiten des Unterrichts und damit weniger sinnlose Verwaltung.
  • Zeit im Unterricht durch Fokussierung auf Kerninhalte.
  • Zeit, um auf Schüler besser eingehen zu können.
  • Zeit für Gespräche mit Eltern
Ältere Beiträge

© 2017 Lehrzeit

Theme von Anders NorénHoch ↑