BlackBoard | Druckvorschau: rekursive Programmierung

Geschrieben von [DS]-=Pencil=- am 17.08.2004 um 14:41:

rekursive Programmierung

Hy,

weiss jemand wie man eine rekursive Addition in Java schreibt?

Wir müssen bis Freitag zig solcher Programme schreiben und ohne ein rekursives Beispielprogramm schaffe ich das nicht..

Hope You Help

Geschrieben von LX am 17.08.2004 um 14:54:

Rekursive Addition? Was verstehst du denn darunter?

Das klassische Beispiel für Rekursion ist eigentlich immer ein Programm, welches Fakultäten ausgibt. 4! (sprich: die Fakultät von 4) ist das Produkt aller Zahlen von 1-4, also 1*2*3*4=24.

Lässt sich ausdrücken in der rekursiven Formel

n! = n * (n-1)!

In C sieht das dann beispielsweise so aus:

code:
1: 2: 3: 4: 5:	int fak(int n) { if (n <= 1) return 1; else return n*fak(n-1); }

Die IF-Abfrage sorgt dafür, dass die Rekursion eben nicht uns unendliche läuft, sondern dass die Rekursion auch irgendwann wieder zurückläuft. Auch zu beachten ist, dass für jeden Rekursionsschritt Speicher bereitgestellt wird. All zu tief darf die Rekursion also oft nicht gehen, da sonst der Speicher überläuft.

Ich denke mal, Google findet zu Rekursion und Algorithmen auch noch eine Menge weiterer Beispiele.

P.S.: Um die Rekursion zu verstehen, muss man zuerst die Rekursion verstehen...

Geschrieben von [DS]-=Pencil=- am 17.08.2004 um 14:58:

Die Fakultät meine ich nicht.

Sonder direkt eben rekursive Addition..

2+3 rekursiv gerechnet

Hope You Help

Geschrieben von duke am 17.08.2004 um 15:17:

sowas?

public int addition(int a,int b){
int erg;
erg = a + b;
return erg;
}

Ich glaube damit ist einfach eine Methode gemeint, wo man 2 Werte übergibt...quelle

Geschrieben von zoul3 am 17.08.2004 um 15:34:

duke???
das ist doch ne einfache addition,oder?
aber cool....durch die frage hab ich schon wieder ne menge gelernt,nur was pencil wissen will versteh ich immer noch nicht............
im übrigen gibt google da echt alles her

Geschrieben von duke am 17.08.2004 um 16:00:

upps, ich war leicht durcheinander,
Hier kann man es aber nachlesen.

Geschrieben von [DS]-=Pencil=- am 17.08.2004 um 16:45:

@Duke dein Code ist iterativ

Also hier wäre eine Lösung (zumindest erstmal für die Subtraktion) die ich gerade versuche zu basteln, aber er gibt immer nur 6 aus

..

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

class minus
{

public static int minus(int m,int n)
{
  if (n > 0) return m;
  else return minus(m-1,n-1);
}

  public static void main ( String[] args )
  {
    System.out.println(minus(6,2));
  }
}

Hope you Help

Geschrieben von LX am 17.08.2004 um 17:02:

Kunststück, 2 ist ja auch größer 0, also gibt er den ersten Parameter (6) zurück.

Syntaktisch verstehe ich's, aber was das ganze soll, raffe ich nach wie vor net

Geschrieben von [DS]-=Pencil=- am 17.08.2004 um 17:34:

Ja, danke (ich Depp), es hat (logischerweise) jetzt funktioniert..

Es soll garnichts..
Es ist einfach nur eine Übungsaufgabe

..

Die richtige Lösung lautet wie folgt:

Subtraktion

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

class minus
{

public static int minus(int m,int n)
{
  if (n < 1) return m;
  else return minus(m-1,n-1);
}

  public static void main ( String[] args )
  {
    System.out.println(minus(6,2));
  }
}

Addition

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

class addition
{

public static int plus(int m,int n)
{
  if (n < 1) return m;
  else return plus(m+1,n-1);
}

  public static void main ( String[] args )
  {
    System.out.println(plus(6,2));
  }
}

Hope I Helped

..

Geschrieben von [DS]-=Pencil=- am 17.08.2004 um 19:56:

Da es hier rein passt, gleich ein weiteres Problem:

Ich habe jetzt versucht das GGT (rekursiv) zu erstellen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

class ggt
{

public static int plus(int m,int n)
{
  if (n == m) return m;
  else if (m > n) return ggt(m-n,n);
  else (m < n) return ggt(m,n-m);
}

  public static void main ( String[] args )
  {
    System.out.println(ggt(6,2));
  }
}

Dennoch wird ein Fehler beim letzten "else" angesagt (not a statement und ; expected...)

Weiss jemand was das Problem ist?

Hope You Help

Geschrieben von LX am 17.08.2004 um 20:04:

code:
1: 2: 3:	if (n == m) return m; else if (m > n) return ggt(m-n,n); else (m < n) return ggt(m,n-m);

In der letzten Zeile fehlt ein "if". Allerdings kannst du hier auch einfach die Bedingung weglassen, da der einzig verbliebene Fall ja m<n ist, also nur else return(...).

Außerdem heißt deine Funktion immer noch plus().

Geschrieben von Black Star am 17.08.2004 um 20:06:

Es empfiehlt sich auch einfache if-else-...Anweisungen immer zu klammern.
Ist besserer Stil und erspart einem viel Aerger wenn mans uebersieht und nicht weiss, was grad passiert.

Geschrieben von [DS]-=Pencil=- am 17.08.2004 um 20:16:

@LX , ich werde es mal verändern

@Black Star wie meinst du das

Hier gleich noch ein Problem mit dem Quicksort Algorithmuss:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:

class Quicksort
{ static int[] feld;
  static final int maxIndex=99999;

  static void feldFuellen()
  { for (int i=0; i<=maxIndex; i++)
    {  feld[i] = (int)Math.round(Math.random()*900.0 + 100); }
  } // feldFuellen

  static void feldAusgabe()
  { System.out.println("Das Feld enthaelt die folgenden Elemente: ");
    for (int i=0; i<=maxIndex; i++)
    {  System.out.println(feld[i]);
       System.out.println(" ");
    }
    System.out.println();
  } // feldAusgabe

  static void vertausche (int a, int b)
  {  int ablage = feld[a];
     feld[a] = feld[b];
     feld[b] = ablage;
  } // vertausche

static void quicksort(int links, int rechts)
{ int nachlinks = rechts; // Laufindex, der vom rechten Ende nach links laeuft
  int nachrechts = links; // Laufindex, der vom linken Ende nach rechts laeuft
  if (nachrechts < nachlinks)
       { // Pivotelement bestimmen
         int pivot = feld[(nachrechts + nachlinks)/2];

         while (nachrechts <= nachlinks)
         {    // Links erstes Element suchen, das
              // groesser oder gleich dem Pivotelement ist
              while ((nachrechts < rechts) && (feld[nachrechts] < pivot))
                   nachrechts++;

              // Rechts erstes Element suchen, das
              // kleiner oder gleich dem Pivotelement ist
              while ((nachlinks > links) && (feld[nachlinks] > pivot))
                   nachlinks--;

              // Wenn nicht aneinander vorbei gelaufen, Inhalte vertauschen
              if (nachrechts <= nachlinks)
                   { vertausche(nachrechts, nachlinks);
                     nachrechts++;
                     nachlinks--;
                   }
         } // end while

         // Linken Teil sortieren
         if (nachlinks > links) quicksort (links, nachlinks);

         // Rechten Teil sortieren
         if (nachrechts < rechts) quicksort (nachrechts, rechts);

       } // end if
}  // quicksort

  public static void main(String[] arg)
  { feld = new int[maxIndex+1];
    System.out.println("Quicksort-Demo: ");
    feldFuellen();
//    feldAusgabe();
    Stoppuhr t = new Stoppuhr();
    t.starte();
    quicksort(0, maxIndex);
    t.stoppe();
//    feldAusgabe();
    System.out.println("Zeit: " + t.lies() + " ms.");
  } // main
} // class quicksort

Bei Stoppuhr t = new Stoppuhr(); wurde mir ein Fehler angezeigt..

Edit:

Ok das GGT funktioniert jetzt..
Danke für die Hilfe:

Hier der Quellcode

Größter gemeinsamer Teiler:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

class ggt
{

public static int ggt(int m,int n)
{
  if (n == m) return m;
  else if (m > n) return ggt(m-n,n);
  else return ggt(m,n-m);
}

  public static void main ( String[] args )
  {
    System.out.println(ggt(6,2));
  }
}

Hope you Help

Geschrieben von MyK am 18.08.2004 um 19:49:

Zitat:

Original von [DS]-=Pencil=-
Bei Stoppuhr t = new Stoppuhr(); wurde mir ein Fehler angezeigt..

Ein Compiler oder ein Run Time Fehler? Fehlermeldung?

Geschrieben von [DS]-=Pencil=- am 19.08.2004 um 20:31:

Ein Kompilier-Fehler..

Hope You Help

Geschrieben von MyK am 19.08.2004 um 23:59:

Hast du vielleicht noch eine Fehlermeldung?

Spontan würde ich darauf tippen, dass die Klasse Stoppuhr nirgends definiert ist - habe allerdings die Java-Syntax nicht im Kopf, könnte auch an der Klammer liegen - aber eine Fehlermeldung wird mich vielleicht eines Besseren belehren.

Geschrieben von [DS]-=Pencil=- am 21.08.2004 um 09:17:

So lautet die Fehlermeldung:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

Quicksort.java:65: cannot resolve symbol
symbol: class Stoppuhr
location: class Quicksort
     Stoppuhr t = new Stoppuhr();
     ^
Quicksort.java:65: cannot resolve symbol
symbol: class Stoppuhr
location: class Quicksort
     Stoppuhr t = new Stoppuhr();

2 errors

Hope You Help

Geschrieben von MyK am 21.08.2004 um 14:21:

Gibt's denn überhaupt eine Klasse namens Stoppuhr? Ist sie exportiert/public?

Geschrieben von [DS]-=Pencil=- am 26.08.2004 um 10:24:

nein, aber habe ich mit New Stopuhr nicht eine erstellt?
Gibt es ansonsten eine andere Variante wie ich das umgehen kann?

Hope You Help

Geschrieben von Deef am 26.08.2004 um 11:55:

Mit "new" bildet man Instanzen von Klassen ...

Klassen werden mit "class" definiert