7. Bundeswettbewerb Informatik

30.09.1988

Die jungen Informatik-Fans sind aufgefordert, sich am diesjährigen Bundeswettbewerb für Informatik zu beteiligen. Teilnehmer müssen sich das Original-Aufgabenblatt bei "Bundeswettbewerb Informatik GMD - Schloß Birlinghoven, 5205 Sankt Augustin 1", besorgen. Es werden nur Einsendungen mit dem Begleitformular des Original-Aufgabenblattes akzeptiert. Teilnehmen können Jugendliche, die nach dem 28. November 1966 geboren wurden. Sie dürfen jedoch nicht schon Im Sommersemester 88, studiert oder vor dem 1. September 1988 ihre Ausbildung abgeschlossen und einen Beruf ergriffen haben. Ausländische Jugendliche können teilnehmen, wenn sie vom 1. September bis 28. November 1988 ihren Wohnsitz in der Bundesrepublik haben; Einsendeschluß ist der 28. November 1988. Die Redaktion der COMPUTERWOCHE wünscht viel Erfolg!

Aufgabe 1: Computer-Komposition

Sue Dama ist berühmt für ihre anspruchsvollen Kompositionen. Sie benutzt immer nur die fünf Tonstufen C, D, F, G und A. Zunächst gibt sie sich ein Thema aus n gleichlangen Tönen vor. Jede Tonstufe kann dabei mehrfach, einfach oder gar nicht vorkommen. Ein Thema für n = 4 ist zum Beispiel: "AGCA".

Weiter denkt sie sich eine Abbildungsregel zwischen den Tonstufen aus, deren Anwendung auf das Thema automatisch eine Variation ergibt. Die Abbildungsregel "C -> F, D -> D, F -> D, G -> C, A -> G" ergibt für das Beispielthema die Variation: "GCFG".

Jetzt wählt sie noch eine Satzform, die aus einer beliebigen Aneinanderreihung von Thema und Variation besteht. Für die Satzform "Thema-Variation-Variation-Thema" sieht der erste Satz ihrer Komposition im Beispiel nun so aus: "AGCA GCFG GCFG AGCA"

Den zweiten Satz komponiert Sue Dama, indem sie den ganzen ersten Satz als Thema nimmt, und die Abbildungsregel und die Satzform darauf wiederholt. Für das Beispiel lautet der zweite Satz damit:

"AGCAGCFGGCFGAGCA

GCFGCFDCCFDCGCFG

GCFGCFDCCFDCGCFG

AGCAGCFGGCFGAGCA"

Weil der zweite Satz viel mehr Töne hat als der erste, spielt ihn Sue Dama um einen Prestofaktor schneller. Ist der Prestofaktor etwa gleich 2.0, dann dauern alle Töne nur halb so lang wie im vorhergehenden Satz.

Der dritte, noch schnellere Satz ergibt sich aus dem zweiten, ebenso wie der zweite aus dem ersten Satz. Der vierte Satz ergibt sich analog aus dem dritten und so weiter.

Aufgabe:

Schreibe ein Programm, das im Stil von Sue Dama komponiert, wenn man ihm ein Thema, eine Abbildungsregel, eine Satzform, die Anzahl der gewünschten Sätze, die Tondauer im ersten Satz und einen Prestofaktor eingibt.

Schicke uns mindestens fünf Kompositionen mit mehreren Sätzen. Eines der Beispiele sei das folgende: Thema "AGCA", Abbildungsregel "C -> F, D -> D, F -> D,

G -> C, A -> G", Satzform "Thema-Variation-Variation-Thema", vier Sätze, Tondauer im ersten Satz vier Zeiteinheiten. Prestofaktor 1. 7.

Aufgabe 2:

Fauler Kompromiß

In der Politik fertigt man nach zähen Verhandlungen, die nicht zu einer Übereinstimmung der beiden Parteien geführt haben, oft ein Schlußkommuniqué an, in dem immerhin möglichst viele gemeinsame Positionen dargelegt werden. Um nicht auch noch über das Schlußkommuniqué lange verhandeln zu müssen, sollte man verabreden, daß zunächst jede Partei einen Textvorschlag macht. Als Schlußkommuniqué wird dann der längste Text gewählt, der als Teil beider Textvorschläge auftritt. Dabei werden der Einfachheit halber nur ganze Wörter und Satzzeichen betrachtet, nicht aber einzelne Buchstaben.

Beispiel: Schluß-Kommuniqué aus den Textvorschlägen: "Die Einkommen der Landwirte sind Abgeordneten ein Buch mit sieben Siegen; um dem abzuhelfen, müssen dringend alle Subventionsgesetze verbessert werden". und

"Die Steuern auf Vermögen und Einkommen sollten nach Meinung der Abgeordneten nachdrücklicher erhoben werden. Dazu müssen die Kontrollbefugnisse der Finanzbehörden dringend verbessert werden." Lösung: "Die Einkommen der Abgeordneten müssen dringend verbessert werden."

Aufgabe:

Schreibe ein Programm, das nach Eingabe von zwei beliebig langen Textvorschlägen, ein solches Schlußkommuniqué ermittelt.

Schicke uns mindestens fünf Paare von Textvorschlägen und die dazugehörigen Schlußkommuniqué.

Enes der Textpaare sei:

"Viele landwirtschaftliche Familienbetriebe kämpfen um ihre Existenz. Der deutsche Bauernverband hat den Bundeskanzler sehr bestimmt aufgefordert, die Europäische Gemeinschaft auf höchster Ebene zu veranlassen, die diesbezüglichen Richtlinien den Notwendigkeiten der landwirtschaftlichen Politik der Bundesregierung anzugleichen." und

"Der Agrarausschuß der EG berücksichtigt bisher deutsche Belange nach Auffassung aller landwirtschaftlichen Organisationen nur unzureichend. Daher sollen Bundeskanzler und Landwirtschaftsminister behutsam aber bestimmt die Abänderung einiger Richtlinien für Agrarpreise im Sinne der Politik der Bundesregierung bewirken. Viele landwirtschaftliche Betriebe leben von ihrer Substanz. Einige Familienbetriebe kämpfen bereits verzweifelt um ihre Existenz."

Aufgabe 3:

Erbteilung auf Birlinghoven

Die Baronin von Birlinghoven hat ihren beiden Töchtern eine Truhe voller Goldmünzen hinterlassen. Ihr Testament bestimmt, daß das Gold einem benachbarten Kloster zukommt, falls es den Töchtern nicht gelingt, den Inhalt der Truhe wertmäßig genau in zwei Hälften untereinander aufzuteilen. Die Goldmünzen haben nur ganzzahlige Werte. Beispiel:

Eine Truhe Goldmünzen mit den Werten 1, 9, 5, 3, 8 Taler könnten die Töchter in die Hälften 1, 9, 3 Taler und 5, 8 Taler teilen.

Eine Truhe Goldmünzen mit den Werten 1, 9, 7, 3, 8 Taler fiele an das Kloster, weil die Aufteilung nicht möglich ist.

Aufgabe:

Schreibe ein Programm, das bei Eingabe einer Folge ganzer Zahlen für die in der Truhe vorkommenden Werte die beiden Erbteile genau aufzählt, andernfalls das Erbe dem Kloster zuspricht, wenn eine Aufteilung nicht möglich ist.

Schicke uns mindestens fünf Beispiele mit verschiedenen Truheninhalten. Der Inhalt einer Truhe sei: 15, 27, 39, 7, 23, 56,13, 39, 22, 5, 42, 34 Taler.

Aufgabe 4:

Gruppendynamik

Stehparties erfreuen sich nicht zuletzt deswegen steigender Beliebtheit, weil man mit seinem Glas in der Hand im Raum umherwandern kann, bis man ein angenehmes Plätzchen gefunden hat. Wolfi beispielsweise versucht stets, bis auf drei Schritte an Sabine heranzukommen; sich noch weiter anzunähern wäre für ihn gesellschaftlich nicht akzeptabel. Sabine dagegen bleibt möglichst weit von Wolfi entfernt, allerdings nicht weiter als 15 Schritte, damit er sie noch sehen kann. So gibt es für jeden Gast eine Wunschentfernung zu jedem anderen Gast.

Ein Partygast ist wunschlos glücklich, wenn er sich zu allen anderen Gästen in seiner Wunschentfernung befindet. Je stärker die tatsächlichen Entfernungen von der Wunschentfernung abweichen, desto weniger glücklich ist er. Das kollektive Partyglück ergibt sich als Durchschnitt des Glücks aller Gäste.

Solange noch Gäste glücklicher werden können, ist Bewegung in der Party. Dann wandert nämlich jeder in die Richtung, die sein Glück am meisten steigert. Nimm an, daß der rechteckige Raum in 20 x 40 quadratische Felder eingeteilt ist, und daß jeder Partygast mit einem Schritt von dem Feld, in dem er sich gerade befindet, in eines der acht benachbarten Felder gelangen kann. Es können natürlich nur freie Felder betreten werden. Nimm weiter über den Verlauf der Party an, daß in einer Runde reihum jeder der Gäste einen Schritt machen oder auch stehenbleiben darf.

Nach jeder Runde wird das kollektive Glück berechnet, wobei alle Entfernungen in Schritten ausgedrückt werden. Die Party ist zu Ende wenn alle Gäste stehengeblieben sind.

Aufgabe:

Schreibe ein Programm, das nach Eingabe der Anzahl der Partygäste, der zugehörigen Wunschentfernungen in Schritten sowie einer Anfangsaufstellung der Gäste die Bewegung in der Party am Bildschirm zeigt. Es soll protokollieren, wie sich das kollektive Glück im Verlauf der Party entwickelt. Schicke uns die Protokolle von mindestens fünf verschiedenen Parties.

Aufgabe 5:

Mendels Land

In Mendels Land gibt es eine fantastische Vielfalt von Schmetterlingen. Man sieht welche mit roten, schwarz gepunkteten Flügeln und gekrümmten Fühlern, andere sind schwarzgelb gestreift und haben gerade Fühler und so weiter.

Bei längerer Beobachtung können wir drei Typen von Merkmalen unterscheiden:

1. Musterung: uni, schwarz gepunktet oder schwarz gestreift.

2. Flügelfarbe: rot, gelb, grün oder blau.

3. Fühlerform: gerade oder gekrümmt.

Es stellt sich heraus, daß jeder Schmetterling, pro Merkmalstyp ein dominantes Merkmal (das sieht man) und ein weiteres rezessives Merkmal (das sieht man nicht oder es ist gleich dem ersten) in sich trägt. Es gelten folgende Dominanzregeln:

uni: dominiert schwarz gepunktet und schwarz gestreift,

schwarz gepunktet: dominiert schwarz gestreift,

rot: dominiert grün und blau,

gelb: dominiert rot und blau,

grün: dominiert gelb und blau,

gerade: dominiert gekrümmt.

Ein Schmetterlingsei erbt für jeden Merkmalstyp von beiden Eltern zufällig je eines von deren zwei Merkmalen. Die in dieser neuen Kombination dominanten Merkmale bestimmen dann das Aussehen des späteren neuen Schmetterlings. Zum Beispiel:

Mutter: sichtbar: uni - rot - gerade

nicht sichtbar: schwarz gestreift - blau - gekrümmt

Vater: sichtbar: uni - grün - gerade

nicht sichtbar: schwarz gepunktet - grün - gekrümmt

Kind: zufällig von Mutter: schwarz gestreift - blau - gekrümmt

zufällig von Vater: uni - grün - gekrümmt

sichtbar: uni - grün - gekrümmt

Aufgabe:

Schreibe ein Programm, das bei Eingabe der dominanten Merkmale zweier Eltern und der gewünschten Kinderzahl entsprechend viele Kinder "mendelt" und beschreibt. Die rezessiven Merkmale der Eltern werden vom Programm zufällig, aber unter Beachtung der Dominanzregeln hinzugefügt.

Schicke uns mindestens, fünf Beispiele von verschiedenen Elternpaaren mit ihrer Nachkommenschaft.