# Aufgaben Programmieren
[toc]
## einfache Aufgaben
**Aufgabe 1**
Berechnen Sie die Anzahl der Stellen einer gegebenen integer-Zahl. Eine Logarithmus- oder Exponentialfunktion steht dazu jedoch nicht zu Verfügung.
**Aufgabe 2**
Ermitteln Sie die Anzahl der Einsen in der Binärdarstellung einer gegebenen ganzen Zahl n.
**Aufgabe 3**
Eine gegebene Zeichenkette soll gespiegelt werden: Beispiel -> leipsieB
Tun Sie dies zuerst in einem Feld, dann rekursiv.
**Aufgabe 4**
Eine Folge von ganzen Zahlen soll eingelesen und in der Form wieder ausgegeben werden, dass jeweils drei Zahlenpaare nebeneinander in einer Zeile stehen. Nach jeweils zwei Zeilen soll eine Leerzeile gedruckt werden.
Beispiel:
```
1 2 3 5 7 11
13 17 19 23 29 31
37 41 43
```
**Aufgabe 5**
Eine endliche Folge von Ziffern, die durch Null abgeschlossen ist, soll einglesen werden und in der Form wieder ausgegeben werden, dass eine Folge aufeinanderfolgender gleicher Zahlen duch deren Anzahl, einen Multiplikationsstern und ihren Wert ersetzt wird.
Beispiel:
Die Eingabefolge `7 7 7 3 5 5 5 5 6 4 3 3 0`
liefert die Ausgabe `3*7 3 4*5 6 4 2*3 0`.
**Aufgabe 6**
Gegeben sei eine endliche Folge von n ganzen Zahlen (n>1). Lesen Sie diese Folge ein und bestimmen Sie, ob die Folge monoton steigend, fallend oder ungeordnet ist. Geben Sie das Ergebnis als Text aus.
Hinweis: Sie können davon ausgehen, dass nicht alle Elemente der Folge gleich sind.
**Aufgabe 7**
Gegeben sei eine endliche Folge von n ganzen Zahlen (n>1). Lesen Sie diese Folge ein und zerlegen Sie die Folge in monotone Teilfolgen. Drucken Sie die Teilfolgen aus. Bei jeder Zustandsänderung der Folge (steigend - fallend) ist eine neue Zeile zu beginnen.
Hinweis: Sie können davon ausgehen, dass die Zeilenlänge in einem Zustand nicht überschritten wird.
Beispiel:
Die Eingangsfolge `1 1 2 4 7 3 2 2 1 6 5 4 1 4 6`
führt zu den Ausgaben
```
1 1 2 4 7
3 2 2 1
6 5 4 1
4 6
```
**Aufgabe 8**
Gegeben ist eine mit 0 abgeschlossene Ziffernfolge. Ersetzen Sie alle vollständigen, monoton steigenden Intervalle (Intervalle aufeinanderfolgender Ziffern) mit einer Länge >3 durch Intervallbeginn - Intervallende.
Beispiel:
Die Ziffernfolge `23471113456782456340`
wird zu `23471113-82456340`.
**Aufgabe 9**
Überlegen Sie sich mindestens zwei verschiedene Verfahren, eine gegebene ASCII-Datei zu verschlüsseln. Die Originaldatei und die verschlüsselte Datei sollen jeweils nur aus Zahlen, Groß- und Kleinbuchstaben sowie Leerzeichen bestehen.
**Aufgabe 10**
In der Folge der natürlichen Zahlen von 1 bis 99 sollen alle jene Zahlen durch einen Stern * ersetzt werden, die entweder durch 7 teilbar sind oder deren Quersumme gleich 7 ist.
**Aufgabe 11**
Man bestimme alle dreistelligen Zahlen, die durch alle ihre Ziffern teilbar sind.
Beispiel:
Die Zahl 126 ist zum Beispiel duch 1, durch 2 und durch 6 teilbar. Zahlen, die die Ziffer 0 enthalten, sollen nicht berücksichtigt werden.
**Aufgabe 12**
Entwickeln Sie einen Algorithmus, welcher rekursiv die Quersumme einer natürlichen Zahl berechnet.
**Aufgabe 13**
Gegeben sei eine Folge von n ganzen Zahlen in einem Array. Gesucht ist die maximale Summe aller Elemente in einer Teilfolge aufeinanderfolgender Zahlen.
Beispiel:
Die Eingangsfolge `12 -34 56 -5 -6 78`
liefert beispielsweise die Summen `56-5-6+78=123`.
**Aufgabe 14**
Geben Sie einen Algorithmus an, der bestimmt, ob eine gegebene Zahl eine Primzahl ist.
## Felder und Matrizen
**Aufgabe 1**
Seien A und B untere n x n Dreiecksmatrizen, d. h., alle Elemente oberhalb der Hauptdiagonalen sind Null.
`A [i,j] = B [i,j] = 0 <=> i < j, 1 < i,j < n`
Beschreiben Sie, wie Sie die Matrizen A und B in einem Array C minimaler Größe speichern können. Welche Größe hat C?
Schreiben Sie zwei Funktionen
`Function A (C: MinArrayTyp; i, j: integer) : integer;`
`Function B (C: MinArrayTyp; i, j: integer) : integer;`
die die entsprechenden in C gespeicherten Matrixelemente zurückgeben.
**Aufgabe 2**
Geben Sie analog zu Aufgabe 1 einen Algorithmus an, um die belegten Elemente einer n x n Dreiecksmatrix M (alle Elemente unterhalb der Hauptdiagonale sind Null, alle anderen Elemente sind positive ganze Zahlen) eindeutig in einem eindimensionalen Feld A zu speichern. Wie lang muß das Feld A sein?
Entwickeln Sie eine Funktion
`GetElement(A:EindimFeld; i,j:integer) : integer;`
die den Wert des ursprünglichen Elementes M [i; j] aus dem Feld A wieder zurückliefert.
**Aufgabe 3**
Gegeben sei eine quadratische Matrix. Die Summe der Elemente einer Zeile (Spalte) sei `z [i] (s [j] )`.
1. Ermitteln Sie die Zeile m mit maximalem z i.
2. Tauschen Sie in der Matrix die Zeile m mit der Spalte m aus. Beschreiben Sie Ihre Lösung mit einem Algorithmus.
**Aufgabe 4**
Ein Matrixelement s heißt Senke, wenn alle (maximal 8) angrenzenden Elemente g [k] größer als s sind. Ermitteln Sie alle Senken einer gegebenen beliebigen n x m Matrix, mit n, m >= 2.
1. Geben Sie die tiefste Senke (maximaler Abstand zu einem Nachbarelement g [k] an.
**Aufgabe 5**
Das Spiel Selektion soll das Prinzip der natürlichen Auslese demonstrieren. Es werden folgende Hilfsmittel benötigt:
1. Ein quadratisches Spielbrett mit 6 x 6 Feldern,
2. jeweils ein Würfel zur Ermittlung einer zufälligen Zeile und Spalte auf dem Spielbrett und
3. jeweils 36 Steine in einer der vier verschiedenen Farben (rot, blau, gelb,schwarz), insgesamt also 144 Steine.
Zu Beginn des Spieles werden auf dem Spielfeld völlig willkürlich jeweils 9 Steine aller 4 Farben angeordnet, so dass das
Spielfeld vollständig mit Steinen bedeckt ist. Danach folgt der erste Schritt, der, wie alle folgenden, aus zweimaligem würfeln mit den beiden Würfeln besteht. So werden beim ersten Wurf die Koordinaten eines Spielfeldes ermittelt. Der auf diesem Feld befindliche Stein wird entfernt, die Farbe an dieser Stelle also vernichtet. Im zweiten Wurf werden die Koordinaten eines weiteren Feldes ermittelt. Sollte sich zufällig das leere Spielfeld ergeben, wird der 2. Wurf wiederholt. Auf dem erwürfelten Spielfeld befindet sich eine bestimmte Farbe. Sie wird auf dem Feld belassen, die gleiche Farbe aber auf das leergewordene Spielfeld gesetzt. Dies wird solange wiederholt, bis nur noch Spielsteine genau einer Farbe auf dem Spielbrett sind.
- Versuchen Sie dieses Spiel zuerst auf einem Blatt Papier zu spielen. Wann haben sie aufgehört, weiter zu würfeln?
- Schreiben Sie danach ein Computerprogramm, das dieses Spiel alleine durchführen kann und den Spielverlauf grafisch darstellt.
- Erweitern Sie Ihr Programm derart, dass es für beliebige n x m Spielbretter verwendbar ist.
**Aufgabe 6**
Die Spalten und Zeilen eines n $\Theta$ m Arrays a seien jeweils aufsteigend sortiert, es gelte also
a [i,j] < a [i,j+1] <> i = 1, …, n und j = 1, …, m-1
a [i,j] < a [i+1,j] <> i = 1, …, n-1 und j = 1, …, m
Entwerfen Sie einen Algorithmus, der feststellt, ob eine gegebene Zahl x in a abgespeichert ist.
Der Algorithmus soll mit möglichst wenigen Vergleichsoperationen auskommen.
**Aufgabe 7**
In einem Text T aus t Zeichen sollen Muster der Form 'xxxxxxxx' gesucht werden, also n-fache Wiederholungen desselben Zeichens Z in t (hier: Z ='x' und n = 8). Schreiben Sie einen Algorithmus, der für gegebene T, t, n, Z als Resultat die Position (1, …, t) des ersten Auftretens des Musters liefert. Wenn das Muster nicht in T enthalten ist, soll der Algorithmus 0 als Ergebnis liefern. Auch dieser Algorithmus soll möglichst wenig Vergleichsoperationen ausführen.
**Aufgabe 8**
Simulieren Sie eine an den Banden eines Billardtisches abprallende Billardkugel. Die Bewegung soll ohne Reibung ablaufen, die Kugel habe also zu allen Zeiten die gleiche Geschwindigkeit. Auf den Tisch sei eine m x n Matrix projiziert. Die Kugel soll sich nur auf Geraden bewegen, die parallel zu den beiden Hauptdiagonalen der Matrix sind. Die Kugel wird also an den Banden im rechten Winkel reflektiert. Stellen Sie zu allen Zeitpunkten, an denen die Kugel genau in der Mitte eines Feldes der Matrix liegt, den Billardtisch (symbolisiert durch die m x n Matrix) grafisch dar. Der Punkt an dem die Kugel zu Beginn der Simulation ist, soll frei wählbar sein. Zu diesem Zeitpunkt soll sich die Kugel in nordöstlicher Richtung bewegen. Geben Sie einen Algorithmus an, der eine solche Simulation realisiert. Die Simulation soll beendet werden, wenn die Kugel sich wieder am Startpunkt befindet. Wieviele Simulationsschritte wurden ausgeführt?
## Grammatik - Syntax
**Aufgabe 1**
Geben Sie eine Grammatik (in Backus-Naur-Form) an, die es ermöglicht, Datumsangaben der Art "15. 9. 1994" aufzuschreiben. Es sollen keine führenden Nullen ausgegeben werden.
**Aufgabe 2**
Verändern Sie die Grammatik aus Aufgabe 1 so, dass die unterschiedlichen Längen der einzelnen Monate berücksichtigt werden. Die veränderte Länge des Monats Februar in einem Schaltjahr muss nicht beachtet werden.",
**Aufgabe 3**
Geben Sie eine kontextfreie Grammatik zur Beschreibung aller Zeichenfolgen mit nicht mehr als zwei aufeinanderfolgenden Einsen an.
**Aufgabe 4**
Aus den Zahlen 0, 1, …, 9 und den Zeichen +, -, *, (, ) lassen sich vollständig geklammerte dyadische Ausdrücke - formal: ( Operand Operator Operand )) - bilden.
Geben Sie eine kontextfreie Grammatik an, mit denen korrekte Ausdrücke dieser Art erzeugt werden können.
:::spoiler Lösung
```
Ausdruck = "(", Operand, Operator, Operand, ")";
Operand = Ausdruck | Zahl;
Operator = "+" | "-" | "*";
Zahl = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
```
```plantuml
@startebnf
Ausdruck = "(", Operand, Operator, Operand, ")";
Operand = Ausdruck | Zahl;
Operator = "+" | "-" | "*";
Zahl = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
@endebnf
```
:::
## Datenbank - Datenmodell
:::spoiler
---
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 1: Berechnen Sie die Anzahl der Stellen einer gegebenen integer-Zahl. Eine Logarithmus- oder Exponentialfunktion".
" steht dazu jedoch nicht zu Verf�gung.",
"Programm"=>"PAS05_05");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 2: Ermitteln Sie die Anzahl der Einsen in der Bin�rdarstellung einer gegebenen ganzen Zahl n.",
"Programm"=>"PAS05_06");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 3: Eine gegebene Zeichenkette soll gespiegelt werden.<br>(Beispiel -> leipsieB) Tun Sie dies zuerst in einem Feld,".
" dann rekursiv.",
"Programm"=> "AUP_3_03");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 4: Eine Folge von ganzen Zahlen soll eingelesen und in der Form wieder ausgegeben werden, da� jeweils drei Zahlenpaare".
" nebeneinander in einer Zeile stehen.".
" Nach jeweils zwei Zeilen soll eine Leerzeile gedruckt werden.<br>Beispiel:<pre>".
" 1 2 3 5 7 11<br>".
" 13 17 19 23 29 31<br>".
" 37 41 43</pre>",
"Programm"=> "AUP_3_04");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 5: Eine endliche Folge von Ziffern, die durch Null abgeschlossen ist, soll einglesen werden und in der Form ".
" wieder ausgegeben werden, da� eine Folge aufeinanderfolgender gleicher Zahlen duch deren Anzahl, einen Multiplikationsstern ".
"und ihren Wert ersetzt wird.<br>".
"Beispiel: Die Eingabefolge 7 7 7 3 5 5 5 5 6 4 3 3 0 liefert die Ausgabe 3*7 3 4*5 6 4 2*3 0",
"Programm"=> "PAS05_13");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 6: Gegeben sei eine endliche Folge von n ganzen Zahlen (n>1). Lesen Sie diese Folge ein und bestimmen Sie, ob die Folge".
" monoton steigend, fallend oder ungeordnet ist. Geben Sie das Ergebnis als Text aus.<br>Hinweis: Sie k�nnen davon ausgehen, da� ".
"nicht alle Elemente der Folge gleich sind.",
"Programm"=> "AUP_3_06");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 7: Gegeben sei eine endliche Folge von n ganzen Zahlen (n>1). Lesen Sie diese Folge ein und zerlegen Sie die Folge ".
"in monotone Teilfolgen. Drucken Sie die Teilfolgen aus. Bei jeder Zustands�nderung der Folge (steigend - fallend) ist eine".
" neue Zeile zu beginnen.<br> Hinweis: Sie k�nnen davon ausgehen, da� die Zeilenl�nge in einem Zustand nicht �berschritten wird.<br>".
"Beispiel: <br>Die Eingangsfolge 1 1 2 4 7 3 2 2 1 6 5 4 1 4 6 f�hrt zu den Ausgaben<br><pre>".
"1 1 2 4 7<br>3 2 2 1<br>6 5 4 1<br>4 6",
"Programm"=> "AUP_3_07");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 8: Gegeben ist eine mit 0 abgeschlossene Ziffernfolge. Ersetzen Sie alle vollst�ndigen, monoton steigenden Intervalle".
" (Intervalle aufeinanderfolgender Ziffern) mit einer L�nge >3 durch".
"Intervallbeginn - Intervallende.<br>Beispiel: <br>Die Ziffernfolge 23471113456782456340 wird zu 23471113-82456340.",
"Programm"=> "AUP_3_08");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 9: �berlegen Sie sich mindestens zwei verschiedene Verfahren, eine gegebene ASCII-Datei zu verschl�sseln. ".
" Die Originaldatei und die verschl�sselte Datei sollen jeweils nur aus Zahlen, Gro�- und Kleinbuchstaben sowie Leerzeichen bestehen.",
"Programm"=> "AUP_3_09");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 10: In der Folge der nat�rlichen Zahlen von 1 bis 99 sollen alle jene Zahlen durch einen Stern () ersetzt werden, die".
" entweder durch 7 teilbar sind oder deren Quersumme gleich 7 ist.",
"Programm"=> "AUP_3_10");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 11: Man bestimme alle dreistelligen Zahlen, die durch alle ihre Ziffern teilbar sind. Die Zahl 126 ist zu Beispiel duch".
" 1, durch 2 und durch 6 teilbar. Zahlen, die die Ziffer 0 enthalten, sollen nicht ber�cksichtigt werden.",
"Programm"=> "AUP_3_11");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 12: Entwickeln Sie einen Algorithmus, welcher rekursiv die Quersumme einer nat�rlichen Zahl berechnet.",
"Programm"=> "AUP_3_12");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 13: Gegeben sei eine Folge von n ganzen Zahlen in einem Array. Gesucht ist die maximale Summe aller Elemente in einer".
" Teilfolge aufeinanderfolgender Zahlen.<br>".
"Die Eingangsfolge 12 -34 56 -5 -6 78 liefert beispielsweise die Summe 56-5-6+78=123.",
"Programm"=> "AUP_3_13");
$aufg[]= array( "Nr" => "einfache Aufgaben",
"Aufgabe" => "Aufgabe 14: Geben Sie einen Algorithmus an, der bestimmt, ob eine gegebene Zahl eine Primzahl ist.",
"Programm"=> "AUP_3_14");
$aufg[]= array( "Nr" => "Felder und Matrizen",
"Aufgabe" => "Aufgabe 1: Seien A und B untere n x n Dreiecksmatrizen, d.h., alle Elemente oberhalb der Hauptdiagonalen sind Null.<br>".
"A [i,j] = B [i,j] = 0 <=> i < j, 1 < i,j < n <br>".
"Beschreiben Sie, wie Sie die Matrizen A und B in einem Array C minimaler Gr��e speichern k�nnen. Welche Gr��e hat C?<br>".
"Schreiben Sie zwei Funktionen<br><br>".
"Function A (C:MinArrayTyp; i,j:integer) : integer;<br>".
"Function B (C:MinArrayTyp; i,j:integer) : integer;<br><br>".
"die die entsprechenden in C gespeicherten Matrixelemente zur�ckgeben.",
"Programm"=> "AUP_4_01");
---
$aufg[]= array( "Nr" => "Felder und Matrizen",
"Aufgabe" => "Aufgabe 2: Geben Sie analog zu Aufgabe 1 einen Algorithmus an, um die belegten Elemente einer n x n Dreiecksmatrix M".
" (alle Elemente unterhalb der Hauptdiagonale sind Null, alle anderen Elemente sind positive ganze Zahlen) eindeutig".
" in einem eindimensionalen Feld A zu speichern. Wie lang mu� das Feld A sein?<br>".
"Entwickeln Sie auch eine Funktion GetElement(A:EindimFeld; i,j:integer) : integer,<br>".
"die den Wert des urspr�nglichen Elementes M [i; j] aus dem Feld A wieder Zur�ckliefert.",
"Programm"=> "AUP_4_02");
$aufg[]= array( "Nr" => "Felder und Matrizen",
"Aufgabe" => "Aufgabe 3: Gegeben sei eine quadratische Matrix. Die Summe der Elemente einer Zeile (Spalte) sei z [i] (s [j] ).".
" Ermitteln Sie die Zeile m mit maximalemz i . Tauschen Sie in der Matrix die Zeile m mit der Spalte m aus. ".
"Beschreiben Sie Ihre L�sung mit einem Algorithmus.",
"Programm"=> "AUP_4_03");
$aufg[]= array( "Nr" => "Felder und Matrizen",
"Aufgabe" => "Aufgabe 4: Ein Matrixelement s hei�t Senke, wenn alle (maximal 8) angrenzenden Elemente g [k] gr��er als s sind.".
" Ermitteln Sie alle Senken einer gegebenen beliebigen n x m Matrix, mit n, m <u>></u> 2.<br> Geben Sie die tiefste".
" Senke (maximaler Abstand zu einem Nachbarelement g [k] ) an.",
"Programm"=> "AUP_4_04");
$aufg[]= array( "Nr" => "Felder und Matrizen",
"Aufgabe" => "Aufgabe 5: Das Spiel Selektion soll das Prinzip der nat�rlichen Auslese demonstrieren. Es werden folgende Hilfsmittel".
" ben�tigt:<br><br>".
"1. Ein quadratisches Spielbrett mit 6 x 6 Feldern,<br><br>".
"2. jeweils ein W�rfel zur Ermittlung einer zuf�lligen Zeile und Spalte auf dem Spielbrett und<br><br>".
"3. jeweils 36 Steine in einer der vier verschiedenen Farben (rot, blau, gelb,schwarz), insgesamt also 144 Steine.<br><br>".
"Zu Beginn des Spieles werden auf dem Spielfeld v�llig willk�rlich jeweils 9 Steine aller 4 Farben angeordnet, so da� das".
" Spielfeld vollst�ndig mit Steinen bedeckt ist. Danach folgt der erste Schritt, der, wie alle folgenden, aus zweimaligem".
" w�rfeln mit den beiden W�rfeln besteht. So werden beim ersten Wurf die Koordinaten eines Spielfeldes ermittelt. Der auf".
" diesem Feld befindliche Stein wird entfernt, die Farbe an dieser Stelle also vernichtet. Im zweiten Wurf werden die Koordinaten".
" eines weiteren Feldes ermittelt. Sollte sich zuf� allig das leere Spielfeld ergeben, wird der 2. Wurf wiederholt. Auf dem ".
" erw�rfelten Spielfeld befindet sich eine bestimmte Farbe. Sie wird auf dem Feld belassen, die gleiche Farbe aber auf das ".
"leergewordene Spielfeld gesetzt. Dies wird solange wiederholt, bis nur noch Spielsteine genau einer Farbe auf dem Spielbrett sind.".
" Versuchen Sie dieses Spiel zuerst auf einem Blatt Papier zu spielen. Wann haben sie aufgeh�rt, weiter zu w�rfeln? <br>".
"Schreiben Sie danach ein Computerprogramm, das dieses Spiel alleine durchf�hren kann und den Spielverlauf grafisch darstellt.".
" Erweitern Sie Ihr Programm derart, da� es f�r beliebige n x m Spielbretter verwendbar ist.",
"Programm"=> "AUP_4_05");
$aufg[]= array( "Nr" => "Felder und Matrizen",
"Aufgabe" => "Aufgabe 6: Die Spalten und Zeilen eines n \Theta m Arrays a seien jeweils aufsteigend sortiert, es gelte also<br><br>".
"a [i,j] <u><</u> a [i,j+1] <==> i = 1, ..., n und j = 1, ..., m-1<br><br>".
"a [i,j] <u><</u> a [i+1,j] <==> i = 1, ..., n-1 und j = 1, ..., m<br><br>".
"Entwerfen Sie einen Algorithmus, der feststellt, ob eine gegebene Zahl x in a abgespeichert ist.<br>".
"Der Algorithmus soll mit m�glichst wenigen Vergleichsoperationen auskommen.",
"Programm"=> "AUP_4_06");
$aufg[]= array( "Nr" => "Felder und Matrizen",
"Aufgabe" => "Aufgabe 7: In einem Text T aus t Zeichen sollen Muster der Form 'xxxxxxxx' gesucht werden, also n�fache Wiederholungen desselben ".
" Zeichens Z in t (hier: Z ='x' und n = 8). Schreiben Sie einen Algorithmus, der f�r gegebene T, t, n, Z als Resultat die Position".
" (1, ..., t) des ersten Auftretens des Musters liefert. Wenn das Muster nicht in T enthalten ist, soll der Algorithmus 0 ".
"als Ergebnis liefern. Auch dieser Algorithmus soll m� oglichst wenig Vergleichsoperationen ausf�hren.",
"Programm"=> "AUP_4_07");
$aufg[]= array( "Nr" => "Felder und Matrizen",
"Aufgabe" => "Aufgabe 8. Simulieren Sie eine an den Banden eines Billardtisches abprallende Billardkugel. Die Bewegung soll ohne Reibung ablaufen, ".
"die Kugel habe also zu allen Zeiten die gleiche Geschwindigkeit. Auf den Tisch sei eine m x n Matrix projiziert. Die Kugel soll ".
"sich nur auf Geraden bewegen, die parallel zu den beiden Hauptdiagonalen der Matrix sind. Die Kugel wird also an den Banden ".
" im rechten Winkel reflektiert. Stellen Sie zu allen Zeitpunkten, an denen die Kugel genau in der Mitte eines Feldes der Matrix liegt,".
" den Billardtisch (symbolisiert durch die m x n Matrix) grafisch dar. Der Punkt an dem die Kugel zu Beginn der Simulation ist, soll ".
"frei w�hlbar sein. Zu diesem Zeitpunkt soll sich die Kugel in nord�stlicher Richtung bewegen. Geben Sie einen Algorithmus an, ".
"der eine solche Simulation realisiert. Die Simulation soll beendet werden, wenn die Kugel sich wieder am Startpunkt befindet. ".
"Wieviele Simulationsschritte wurden ausgef�hrt?",
"Programm"=> "AUP_4_08");
$aufg[]= array( "Nr" => "Grammatik - Syntax",
"Aufgabe" => "Aufgabe 1: Geben Sie eine Grammatik (in Backus-Naur-Form) an, die es erm�glicht, Datumsangaben der Art 15. 9. 1994 aufzuschreiben.".
" Es sollen keine f�hrenden Nullen ausgegeben werden.",
"Programm"=> "AUP_1_01.TXT");
$aufg[]= array( "Nr" => "Grammatik - Syntax",
"Aufgabe" => "Aufgabe 2: Ver�ndern Sie die Grammatik aus Aufgabe 1 so, da� die unterschiedlichen L�ngen der einzelnen Monate ber�cksichtigt werden. ".
"Die ver�nderte L�nge des Monats Februar in einem Schaltjahr mu� nicht beachtet werden.",
"Programm"=> "AUP_1_02.TXT");
$aufg[]= array( "Nr" => "Grammatik - Syntax",
"Aufgabe" => " Aufgabe 5: Geben Sie eine kontextfreie Grammatik zur Beschreibung aller Zeichenfolgen mit nicht mehr als zwei aufeinanderfolgenden Einsen an.",
"Programm"=> "AUP_1_05.TXT");
$aufg[]= array( "Nr" => "Grammatik - Syntax",
"Aufgabe" => "Aufgabe 6: Aus den Zahlen 0,1,...,9 und den Zeichen +, -, *, (, ) lassen sich vollst�ndig geklammerte dyadische Ausdr�cke (formal:".
" ( Operand Operator Operand )) bilden. Geben Sie eine kontextfreie Grammatik an, mit denen korrekte Ausdr�cke dieser Art erzeugt werden k�nnen.",
"Programm"=> "");
$aufg[]= array( "Nr" => "Grammatik - Syntax",
"Aufgabe" => "Aufgabe 7: Mit nur drei verschiedenen ASCII-Zeichen lassen sich einfache Bergpanoramen zeichen, z.B.<br>".
"<pre> __ /\__<br>".
" __/ \/ \ bzw.: /__/__\//\__\\___<br>".
" / \___</pre>".
"Geben Sie die Syntax solcher Sequenzen (von links nach rechts, in der vereinfachten Form) durch Syntaxdiagramme an, wobei Sie die ".
"Zeilenwechsel ignorieren k�nnen. Anfang und Ende sollen jedoch gleich hoch liegen und nicht h�her als irgendein anderer Punkt des Bildes.",
"Programm"=> "AUP_1_07.GIF");
$aufg[]= array( "Nr" => "Grammatik - Syntax",
"Aufgabe" => "Aufgabe 8: Die folgende kontextfreie Grammatik G=(V,T,P,S) definiert einen kleinen Auszug der deutschen Sprache:<br>".
"V= {Satz, Subjekt, Pr�dikat, Objekt, Artikel, Substantiv}<br>".
"T= {'Die ', 'die ', 'Maus ', 'Katze ', 'jagt ', 'bei�t ', ' '}<br>".
"P= {<pre>".
" Satz - 'Die', Substantiv Pr�dikat Objekt .,<br>".
" Subjekt - Artikel Substantiv,<br>".
" Pr�dikat - jagt,<br>".
" Pr�dikat - bei�t,<br>".
" Artikel - die,<br>".
" Objekt - Artikel Substantiv,<br>".
" Substantiv - Maus,<br>".
" Substantiv - Katze<br> }</pre>".
"S= {Satz}<br>".
"Geben Sie an, welche S�tze auf Grund dieser Grammatik gebildet werden k�nnen. Warum ist es praktisch unm�glich, mit einer solchen Grammatik G ".
"die gesamte deutsche Sprache zu beschreiben? Ist es wenigstens theoretisch m�glich?",
"Programm"=> "");
/*Aufgabe 3.
In einem alten Zauberbuch wurde die folgende Grammatik zur Erzeugung von magischen Zauberformeln gefunden. Alle Zauberspr�che in diesem Buch bestehen aus dem durch die Grammatik erzeugten Wort ,,H E X E``.
Spruch= {V,T,P,S}
S= { HEXE }
T= {abra, sim, som, sum, ca, da, bra,
la, sa, so, dum, sam, dim, dam}
V= {H, E, X}
P= {
H = abra | sim | sam | som | sum | X
E = ca | da | bra | la | sa | so | dum | E E | X
X = sim | sam | sum | la | dim | dam | dum | E
}
Stammen die Zauberspr�che
,,abracadabrasimsaladim``,
,,sumsumdumdumlalaladimdumdumdum``,
,,ladimbrasodumba`` und
,,abrabradumsaladumsomsimca``
aus dem Zauberbuch? Wieviele Zauberspr�che mit minimaler Buchstabenanzahl gibt es? Welcher der Zauberspr�che mit gr��tm�glicher Anzahl an verschiedenen Silben hat die kleinstm�gliche Bustabenanzahl?
Aufgabe 4.
F�r die formale Sprache ,,Strichoperation`` sei das Alphabet
g�ltig. Die zul�ssigen W�rter seien die, welche im Zahlensystem ,,zur Basis 1`` eine korrekte Addition darstellen.
Geben Sie eine kontextfreie Grammatik zur Erzeugung solcher W�rter an.
*/
Algorithmen und Programmierung - Aufgaben</th><tr><td>";
Sign in with Wallet
Connect another wallet