Variante der Ackermannfkt < Softwaretechnik+Pro < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:38 Mo 18.11.2013 | | Autor: | i-she |
| Aufgabe | Die folgende Funktion berechnet eine Version (nach Abelson, Sussman: Structure and Interpretation of Computer Programs) der mathematischen Funktion mit dem Namen Ackermann:
Algorithm Ackermann (x, y):
Input: natuerliche Zahlen x, y
Output: Ackermann-Zahl
if (y = 0) then 0
if (x = 0) then 2*y
if (y = 1) then 2
else Ackermann(x-1, Ackermann(x, y-1))
Schreiben Sie eine Java-Methode
public static BigInteger ackermann(BigInteger x, BigInteger y) |
Hallo
zu dieser Aufgabe habe ich mir folgendes gedacht(was nicht so ganz stimmt):
Könnte man mir auf die Sprünge helfen?
package firststeps;
import java.math.BigInteger;
import java.util.Scanner;
public class MyAckermann {
public static Biginteger ackermann(BigInteger x, BigInteger y){
if (y == 0) return 0;
if (x == 0) return rek( x, 2*y);
if (y == 1) return 1;
else
{return rek(x-1, rek(x, y-1));
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("Geben Sie die erste Zahl ein:");
Biginteger x = scan.nextInt();
System.out.print("Geben Sie die zweite Zahl ein");
Biginteger y = scan.nextInt();
System.out.print(ackermann(x,y));
}
}
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:12 Mo 18.11.2013 | | Autor: | Ebri |
Die obige Definition der Ackermannfunktion kann ich nicht nachvollziehen, bis jetzt habe ich sie immer anders gesehen.
Ich kann dir aber ein paar Tipps zu rekursiven Funktionen und dem Arbeiten mit BigInteger geben.
Wie du schon richtig angedeutet hast lässt sich die Ackermannfunktion rekursiv implementieren. Eine rekursive Methode besteht im allgemeinen aus Abbruchbedingungen und dem rekursiven Aufruf.
Beispiel: Fakultät
Def.:
$n! [mm] =\begin{cases} 1, &n=0 \\ n\cdot (n-1)!, &n>0\end{cases} [/mm] $
Code:
public int fak(int n) {
if(n <= 0) {
return 1;
} else {
return n*fak(n-1);
}
}
Abbruchbedingung ist hier: if(n<=0) return 1
Ist die Bedingung nicht erfüllt der rekursive Aufruf: n*fak(n-1)
Die Abbruchbedingungen sind in deinem Fall:
if (y = 0) then 0
if (x = 0) then 2*y
if (y = 1) then 2
Und der rekursive Aufruf: Ackermann(x-1, Ackermann(x, y-1))
Dein rekursiver Aufruf mit rek(x,y) funktioniert nicht, da es die Methode nicht gibt.
Ein paar Worte zu BigInteger:
BigInteger sind Objekte, d.h. normale Operationen wie "+", "-", "*" oder "==" klappen nicht.
BigInteger stellt aber Methoden wie "add(BigInteger val)" oder "equals(BigInteger val)" zur Verfügung.
Sind x, y BigInteger.
Möchte man überprüfen, ob x = 0 ist, kann man das so machen:
"x.equals(BigInteger.ZERO)" oder "x.equals(BigInteger.valueOf(0))"
Möchte man x-1 rechnen:
"x.subtract(BigInteger.ONE)" oder "x.subtract(BigInteger.valueOf(1)"
"add(..)", "subtract(..)" .. geben ein BigInteger mit dem neuen Wert zurück.
Gruß
Ebri
|
|
|
|
