Rekursionsaufgabe

[BlubBlub]

Hi ich habe folgende Aufgabe gefunden und versucht zu lösen.
Auf den ersten Blick sah die Aufgabe recht leicht aus, da die
notwendigen Verzweigung im Prinzip bereits vorgegeben sind,
doch bei dem Versuch das dazugehörige Programm umzusetzen
bin ich einfach auf keine gescheite Lösung gekommen.
Wie würdet ihr die Funktion U implementieren?



Für zwei natürliche Zahlen n,x ist Ulam-Zahlenfolge folgendermaßen definiert:

                   { x                    ,falls n = 1                            }
 U(n+1, x) =  { U(n,x)/2           ,falls n > 1 und U(n,x) gerade   }
                  { 3 * U(n,x) +1    ,falls n > 1 und U(n,x) ungerade }

Vervollständigen Sie die rekursive Methode U(n,x) und die main-Methode so, dass bei Eingabe von n, x mit n, x > 0 die n-te Ulam-Zahl ausgegeben wird.

Class MyProgram
{
               public static ___ U(___)
               {

               }

              public static void main(String[] args)
              {
                      int n = //Zahl1 ;
                      int m = // Zahl2 ;




                      System.out.print("Die " + n + "-te Ulam-Zahl ist " + y);
              }
}

 

[XHelp]

Wie hast du sie denn gelöst? Die Funktionsweise lässt sich ja 1zu1 aus der Gleichung übernehmen.

 

[BlubBlub]

Ja genau eigentlich sollte sich die Lösung aus der Gleichung übernehmen lassen.
Mein Versuch sah so aus:

public class MyProgram
{
	public static int U(int n, int x)
	{
		if(n == 1)
		{
			return x;
		}
		else 
		{
			if(U(n,x)%2 == 0)
			{
				return U(n, x)/2;
			}
			else
			{
				return 3*U(n, x)+1;
			}
		}
	}
	
	public static void main(String[] args)
	{		
		int n = //Zahl1;
                int m = //Zahl2;

		int ulam = U(n+1, x);
		System.out.println(ulam);
	}
}

Doch dieses Programm würde nicht deteminieren.

 

[XHelp]

Natürlich nicht. Die oben angeführte bedingung gilt ja auch für U(n+1, x).
Wenn du also n übergeben bekommst, dann musst du den Vorgänger betrachten

 

[BlubBlub]

Das ist richtig, das hab ich auch schon erkannt. Der Programm sollte einen Ansatz
zeigen, den ich probiert habe, um irgendwo anzufangen. Hab mir schon den Kopf
drüber zerbrochen, wie ich das richtig umsetzen soll, aber mich verwirrt die
Gleichung. Was würdet ihr denn an dem Code ändern?

 

[XHelp]

Naja, den funktionsfähig machen:

n-1

bei Rekursion einsetzen.
Darüber hinaus rechnest du 2 mal

U(n,x)

aus, das ist natürlich unnötig, du kannst auch eher so machen:
[JAVA=11]{
int predecessor = U(n-1,x);
if (predecessor%2==0) {
return predecessor/2;
} else {
return 3*predecessor+1;
}
}
[/code]

 

[BlubBlub]

Ah okay ich hab jetzt auch den Denkfehler gefunden, den ich die ganze Zeit gemacht habe.
Muss denn ganz unten im Code (siehe Kommentar) das +1 stehen oder muss das weg?

public class MyProgram
{
    public static int U(int n, int x)
    {
        if(n == 1)
        {
            return x;
        }
        else 
        {
            int u = U(n-1,x);

            if(u%2 == 0)
            {
                return u/2;
            }
            else
            {
                return 3*u+1;
            }
        }
    }
    
    public static void main(String[] args)
    {       
        int n = //Zahl1;
                int m = //Zahl2;
 
        int ulam = U(n+1, x);                   //Muss hier +1 stehen?
        System.out.println(ulam);
    }
}

 

[XHelp]

Muss nicht, dann rechnet er aber für eine andere Zahl das Ergebnis.

 

[BlubBlub]

alles klar. danke für die hilfe