Passend zum Nikolaustag eine Programmieraufgabe für die Elftklässler in Bayern:
Aufgabe
Programmiere für den Nikolaus eine Verwaltung seiner Geschenke mit Hilfe des Kompositum-Musters. Dabei soll von jedem Geschenk der Empfänger-Name und das Geschenk als String gespeichert werden:
Geschenk:={name:String, titel:String}
Konkret wäre es zum Beispiel: g1={“Tim”,”Buntstifte”}.
Die Geschenke wiederum sollen unter einer Familie zusammengefasst werden. D.h. jedes Familienobjekt hat den Familiennamen als Attribut (String) und eine Liste der Geschenke. Als Objektdiagramm sieht das dann ungefähr so aus:
Die Aufgabe kann man natürlich auch splitten. Eine Gruppe macht die Familienstruktur, eine andere die Geschenkeliste.
Schööne Aufgabe. Und dazu dann eine Suchmethode String geschenkNennen(String familie, String vorname). Iterativ (vermutlich immer der erste Schülergedanke) oder rekursiv? Als Vorbereitung des Baums: Findet der Rechner da Sachen schneller als wenn die Information in einer einfachen Liste wäre, oder gleich schnell?
(Und danke für die UOGB-Erinnerung im anderen Eintrag, das wusste ich noch gar nicht.)
Was schneller ist… Ich denke, dass eine Liste langsamer ist. Also eine Liste, in der die Geschenke einfach so hintereinandergehängt werden. Denn im Worst-Case hat eine Suche in einer unsortierten Liste die Komplexität O(n), da im schlimmsten Fall ja jedes Element getestet werden muss. Auf der anderen Seite ist, wenn n näherungsweise m*4 mit mO(m) und meine Struktur besser.
Vielleicht sollte man das Thema Komplexität besser vom Ende der 12. Klasse weiter nach vorne ziehen, wo es mehr Sinn macht. Denn wie motiviere ich sonst so etwas wie Bäume, wenn nicht über die Komplexität.
Für das Konzert muss du dich aber wahrscheinlich beeilen. Nicht, dass es schon ausverkauft ist. Vielleicht sieht man sich ja da mal.
Karten habe ich gleich heute morgen bestellt. Wir könnten uns ja auch an der LMU sehen, wo du beim TdI einen Workshop… nein?
Unsortierte Liste: ja, stimmt, weil deine Struktur ja schon teilsortiert ist. Man könnte alle Varianten vergleichen llassen: Deine Struktur, vollsortiert; deine Struktur, teilsortiert; einfache Liste sortiert und unsortiert – um herauszufinden, dass man nur wirklich weiter kommt, wenn man zum Suchbaum greift.