Java-Programmieraufgaben - RekursionSchwierigkeit 1
Implementieren Sie einen Taschenrechner, der arithmetische Ausdrücke gegeben als Zeichenketten einliesst (als Parameter im Konstruktor) und mit einer Objektmethode den zugehörigen Wert ausrechnet und zurückgibt. Der Taschenrechner soll nur ganzzahlige int-Werte von 0 bis 9 mit sowie + oder - als Operatoren verstehen. Ausdrücke können geklammert werden. Leerzeichen sollen überlesen werden. Das Einlesen soll mit rekursivem Abstieg implementiert werden.
Die Syntax sei wie folgt als EBNF definiert (ohne Definition der Leerzeichen)
ausdruck = term, [ "+" | "-" , term ] ;
term = "(", term, ")"
| "0" | "1" | ... | "9" ;
Gültige Zeichenketten sind also: "1", "((2))", "2 + 3", "( (4) - 5 +7)".
Sehen Sie sich die Methoden von String und Character an.
Schwierigkeit 2
Implementieren Sie den Euklidischen Algorithmus rekursiv. Verwenden Sie ausser Rekursion nur if-else, Vergleiche und Subtraktion.
Der Euklidische Algorithmus zur Berechnung des größten gemeinsamen Teilers zweier positiver ganzer Zahlen a und b (ggt(a,b)) ist wie folgt rekursiv definiert:
Schwierigkeit 2
Implementieren Sie einen linear-rekursiven Algorithmus, der für ein char-Feld erkennt, ob es sich dabei um ein Palindrom handelt oder nicht. Ein Palindrom ist ein Wort, welches vorwärts und rückwärts gelesen identisch ist. Beispiele: "ABBA", "lagerregal". Die Gross- und Kleinschreibung braucht nicht berücksichtigt zu werden: "Lagerregal" muss also nicht als Palindrom erkannt werden.
Schwierigkeit 1
Implementieren Sie jeweils einen rekursiven Algorithmus, der die Summe a+b und das Produkt a*b zweier natürlicher Zahlen rekursiv berechnet. Dabei sind als arithmetische Funktion lediglich das Addieren von 1 zu einer Zahl oder das Subtrahieren von 1 von einer Zahl erlaubt. Ausser if sind keine weiteren Kontrollanweisungen erlaubt.
Der Zeitaufwand der Addition soll O(a+b) sein, der von der Multiplikation O(a*b).
Schwierigkeit 2
Die Primzahleigenschaft einer natürlichen Zahl z kann durch Ausprobieren aller potentiellen Teiler von 2 bis z-1 überprüft werden: ist keine dieser potentiellen Teiler ein echter Teiler von z, dann ist z eine Primzahl. Diesen Brute-Force-Primzahltest kann man mit einer for-Schleife implementieren. Es geht aber auch rekursiv.
Die Funktion istPrimzahl(p) sei wie folgt mit Hilfe der rekursiven Funktion
istPrimzahl(p, z) definiert:
Implementieren Sie eine rekursive Java-Methode, die istPrimzahl() berechnet (ohne Iterationen).-
Schwierigkeit 2
Gegeben sei folgende rekursiv definierte Funktion f:
Implementieren Sie eine rekursive Java-Methode, die f(n) berechnet (ohne Iterationen).
Um welche Form von Rekursion handelt es sich?
Was berechnet f(n)?
Geben Sie eine nicht-rekursive Implementierung von f an.
Schwierigkeit 2
Sie sollten erst die n-te Potenz einer Zahl mit O(log2n) Zeitaufwand implementiert haben, um diese Aufgabe anzugehen. Die Lösungsidee ist hier die gleiche.
Man kann die n-te Fibonacci-Zahl mit Hilfe der folgenden Gleichung berechnen (Abbildung aus deutscher Wikipedia):
Implementieren und testen Sie erst eine Klasse Matrix, mit der 2x2-Matrizen (int-Werte) repräsentiert und multipliziert werden können. Dazu brauchen Sie kein Feld verwenden: vier int-Attribute reichen aus.
Entwerfen und implementieren Sie dann einen rekursiven Algorithmus, mit dem die n-te Fibonacci-Zahl mit höchstens O(log2n) Zeitaufwand berechnet wird.