Binominalkoeffizient rekursiv selber berechnen, wie soll das genau gehen? (java)?

Ich habe z. B. n über k

Ich weiß, dass wen n kleiner k oder k kleiner 0 ist, ich einfach return 0 machen kann, in der Methode, die meinen Binominialkoeffizienten hat. und wenn n gleich 0 ist, kann ich einfach return 1 machen.

Wie sieht es jetzt jedoch aus, wenn ich es rekursiv lösen will?

Ich konnte mir schon denken, dass man

(n-1 über k-1) +(n-1 über k-1) rechnet, aber wie würde ich genau das als code schreiben? Bei unserer Aufgabe hat unser Lehrer uns schon vorgegeben wie wir den Binominalkoeffizienten rechnen können, ohne es so rekursiv machen zu müssen. Da gibt es schon irgendwie eine vorgefertigte Kalsse in der Bibliothek von Java.

Aber fürs Verständnis wollte ich mal sehen, wie der Code aussehen würde, wenn man den letzten Schritt selber machen würde, will nur gerne mal testen, ob das gleiche rauskommt.

2 Antworten

TechPech1984

Nutzer, der sehr aktiv auf gutefrage ist

im Thema Computer

24.10.2021, 17:10

kennst du google ? musst du lernen als programmierer , den das wurde alles schon mal gelösst https://www.google.com/search?q=Binominalkoeffizient+rekursiv+java

erstes ergebnis :

https://www.java-forum.org/thema/binomialkoeffizient-rekursiv-berechnen.94228/

das sind ja alles nur mathematische probleme , sollen ja auch nur trainieren , brauch man dann später weniger . ich finde solche aufgaben irgendwie nie nett . hindern einen das programmieren zu lernen weil man ewig auf die mathe runtergebrochen wird . aber da hat jeder prof etc sein eigenen vorstellungen . finde ich sortierungen etc schon besser um rekursionen zu lernen, da es auch sehr komplex werden kann bei mathematischen problemen .

jdqwio2

Fragesteller

24.10.2021, 17:14

Aber da wird der Binomialkoeffizient auch ncith rekursiv berechent, sondern die nutzen eine schon vorgefertigte methode, die Java zur Verfügung stellt

jdqwio2

Fragesteller

24.10.2021, 17:15

Das sollten wir eig. auch nicht rekursiv lösen, unser Prof meinte nur dass es geht und man sich ja mal Gedanken machen kann. Aber im Internet nutzen auch alle die vorgefertigte Methode von java

jdqwio2

Fragesteller

24.10.2021, 17:16

Ach ne sorry bei mir hat die Seite nur gehangen, die haben das doch normal berechent

HermCrafter

24.10.2021, 18:45

Schönen guten Abend,

Leider kann ich Java nur sehr schlecht, für solche Berechnungen nutze ich meistens Python. Deine Aufgabe wird also sein, folgenden Algorithmus in Java zu schreiben.

Ich gehe davon aus, dass die Fakultät rekursiv berechnet werden soll. Daher habe ich 2 Funktionen verwendet. Erstere fk berechnet rekursiv die Fakultät der übergebenen Zahl, zweitere bk errechnet zunächst mithilfe von fk die Fakultät und berechnet daraus anschließend den Binomialkoeffizienten.

def fk(n):
  return 1 if n == 0 else n * fk(n - 1)

def bk(n, k):
  return fk(n) / (fk(k) * fk(n - k))

print(bk(3, 1))

In diesem Falle wird der Binomialkoeffizient von 3 über 1 berechnet. Du könntest den Code auch dahingehend erweitern, dass keine negativen Zahlen übergeben werden dürfen.

Hi, wie kann ich eine Methode aufrufen, die dann rekursiv eine Quadratzahl berechnet und die zurück gibt? WIe würde der Code aussehen

...zur Frage

Java: Rekursion mit String-Methoden?

Hallo,

wir haben momentan das Thema Rekursion und dazu habe ich eine Frage.

private String wasTueIch(String wort) {
  if (wort.length() <= 1)
    return wort;
  else
    return wasTueIch(wort.substring(1, wort.length())) + wort.charAt(0);
}

Meine Frage ist, warum die Methode rekursiv ist und wie man einen Palindromtester (Palindrom: ein Wort, welches gespiegelt die gleiche Bedeutung hat) einbauen kann.

...zur Frage

Java / Palindrom rekursiv erkennen: Kann mir jemand sagen, wo in meinem Code der Fehler liegt?

Hallo,

ich habe eine Methode geschrieben, die mir true oder false liefert, falls der übergebene String ein Palindrom ist oder nicht. Da ich es rekursiv versuche, habe ich leider Schwierigkeiten.

Kann mir jemand sagen, wo der Fehler liegt? Danke schon mal!

public static void main(String[] args) {
  String s = "aknna";
  int length = s.length();

  System.out.println(isPalindrom(s, length));
}

public static boolean isPalindrom(String s, int length) {
  if (s.length() < 1) {
    return true;
  }

  if (s.charAt(0) != s.charAt((s.length() - 1))) {
    return false;
  }

  return isPalindrom(s, length - 1);
}

...zur Frage

Labyrinth Rekursiv durchsuchen Performance?

Ich bin dabei ein Labyrinth Rekursiv zu durchsuchen. Klappt auch bei kleinen Labyrinthen.

Code ist folgender, sollte eigentlich selbsterklärend sein denk ich. Problem ist nun folgendes. Der Professor hat viele JUnit Tests geschrieben und bei großen Labyrinthen dauert es zu lang (4s) und bricht daher ab. Wie schreibe ich den Code Performanter? Oder hab ich einen Denkfehler im Code?

Sprache natürlich Java

Ich kann nicht ausschließen, dass die Tests nicht dazu da sind zu erkennen wie performant der Code generell ist. Heißt, dass man guckt wie viele Tests er schafft um zu wissen welche Performance klasse man so etwa hat.

Stack<Coordinate> shortestPath;

private void recursivelyDiscoveryMaze(int x, int y, int depth, Stack<Coordinate> currentPath) {
    //this.maze.prettyPrint();
    currentPath.push(new Coordinate(x, y));
    if (dX == x && dY == y) {
        if (shortestPath.size() > currentPath.size() || shortestPath.size() == 0) {
            shortestPath = (Stack<Coordinate>) currentPath.clone();
        }
        currentPath.pop();
        return;
    }

    this.maze.getMazeField()[x][y] = 1; //set visited
    depth++;
    if (isValidStep(x + 1, y)) //if can be visited
        recursivelyDiscoveryMaze(x + 1, y, depth, currentPath);
    if (isValidStep(x, y + 1))
        recursivelyDiscoveryMaze(x, y + 1, depth, currentPath);
    if (isValidStep(x - 1, y))
        recursivelyDiscoveryMaze(x - 1, y, depth, currentPath);
    if (isValidStep(x, y - 1))
        recursivelyDiscoveryMaze(x, y - 1, depth, currentPath);
    depth--;
    this.maze.getMazeField()[x][y] = 0; //set unvisited 
    currentPath.pop();
}

...zur Frage

Java: Wie kann ich rekursiv die Nachbarn miteinander addieren?

Hallo, kann mir jemand helfen, den Code etwas umzuwandeln?

Ich möchte hier nicht die Zahlen miteinander addieren, wie es in meinem Code passiert, sondern möchte, dass ich die Nachbarn jeweils miteinander addiere, sodass ich am Ende nur noch eine Zahl da stehen habe.

Das ganze soll rekursiv laufen und das Ergebnis dann, so wie es im Stack abgelegt wurde, nach dem FiFo-Prinzip wieder ausgegeben werden.

Wie müsste dann meine Abbruchbedingung aussehen?

Also ich muss im Array nach einem kompletten Durchgang das letzte Element entfernen. Jedoch weiß ich nicht, wie das aussehen soll und wie das Programm dann abbricht, wenn das Array nur noch die Länge 0 hat.

Danke im Voraus.

  static int arr[] = { 1, 6, 4, 3, 2 };
  
  // using recursion.
  static int findSum(int A[], int N) {
    if (N <= 0)
      return 0;
  
    return (findSum(A, N - 1) + A[N - 1]);
  }
  
  // Driver method
  public static void main(String[] args) {
    System.out.println(findSum(arr, arr.length));
  }
}

...zur Frage

Java Comparator schreiben?

Ich hab folgende Aufgabe, ich soll Spielkarten in Java sortieren.

Mein Prof schrieb folgendes in die Aufgabe:

Mit erster Priorität nach Rängen (Rank) und zwar Ass vor König, König vor Dame, Dame vor Bube, Bube vor 10, 10 vor 9, 9 vor 8, 8 vor 7, 7 vor 6, 6 vor 5, 5 vor 4, 4 vor 3 und 3 vor 2.

und

Mit zweiter Priorität nach Farben (Suit) und zwar Kreuz vor Pik, Pik vor Herz, Herz vor Karo.

Meine jetzige implementation sieht so aus:

@Override
public int compare(Card o1, Card o2) {
    if (o1.equals(o2))
        return 0;
    int comparedValue = Integer.compare(o1.getRank().ordinal(), o2.getRank().ordinal());
    if (comparedValue != 0)
        return comparedValue;
    comparedValue = Integer.compare(o1.getSuit().ordinal(), o2.getRank().ordinal());
    return comparedValue;
}

Nur hab ich da Bauchschmerzen. Erstens, wie geht man dort mit null um? Oder ist das egal?

Dann ist das mit der Ordnung so richtig? Also dass ich gucke, ob der Rank einen unterschied hat, wenn ja, dann return, wenn nicht, soll er die Farbe nehmen.

Technisch funktioniert der Code, mir geht's eher darum, obs semantisch korrekt ist und zur Aufgabe passt.

Dann halt wie man den Nullpointer verhindert. Also ob man eine Exception (in meinem fall Assert false, weil Exception noch verboten), oder ob man 0 oder Integer.max/min nimmt.

Dann noch ne frage am rand. Der obige Code sortiert falsch herum. Wie macht man das jetzt am besten. Ich hab einfach *=-1; gemacht, oder tauscht man die objekte als parameter? Oder wie macht man das elegant?

...zur Frage

Wie funktioniert der Java Code?

private void reversePrint(Node n) {
		if (n == null)
			return;
		else {
			reversePrint(n.getNext());
			System.out.print(n.toString());
		}
	}

es wurde vorher eine eigene liste implementiert also wie man das eben kennt mit node und data.

Jetzt ist meine Frage, wie der obige Code funktioniert? es wird ja die liste rekursiv ausgegeben. jetzt geht der solange entlang bis er am ende ist und dann wird das ausgegeben, aber wie funktinoiert das genau?

er geht ja immer in das else rein in das else rein in das else rein und dann ist am am letzten knoten und dann ist n= null, dann folgt "return" . Bedeutet es nicht hier, dass dann diese methode verlassen wird? und wie funktioniert dann dieses wie von Zauberhand rückwärts ausgeben?

...zur Frage

Java: Vigenère-Verschlüsselung?

Hallo!

Ich habe folgenden Java Code zur Vigenère-Verschlüsselung gefunden. Könnte mir jemand diesen Code Schritt für Schritt erklären? Wieso wird vom Klartext der Buchstabe A abgezogen?

PS: Mit dem Verfahren selber kenne ich mich bestens aus, doch, obwohl dieser Code einwandfrei funktioniert, ist er mir schleierhaft.

public static String vigenereCipher(String plaintext, String key) {
  String ciphertext = "";
  int mod, cipher1, cipher2, cipher3, y = 0;

  for (int x = 0; x < plaintext.length(); x++) {
    cipher1 = plaintext.charAt(x) - 'A';
    mod = x % key.length();
    cipher2 = key.charAt(mod) - 'A';
    cipher3 = (cipher1 + cipher2) % 26 + 'A';
    ciphertext = ciphertext + (char) cipher3;
  }

  return ciphertext;

...zur Frage

Java: readDouble-Methode?

Moin,

folgender Code funktioniert nicht:

public class In {
  public static void main(String[] args) {
    System.out.println(readDouble(" "));
  }

  private static double[] readDouble(String string) {
    return readDouble(" ");
  }
}

Ich bin Anfänger und habe bisher nur die Scanner-Methode benutzt.

Fehlercode (in Zeile 10):

Exception in thread "main" java.lang.StackOverflowError

MfG L

...zur Frage

Wer kann mir Tipps geben um in Java eine Methode zu schreiben die den größten gemeinsamen Teiler berechnet?

Aber nur mit INTS also ohne float ja ich weiß also Komma zahlen sind nicht erlaubt geht das irgendwie mit minus? (Und bitte kein Code also einfach nur in Worten fassen ich muss das selber programmieren!!!)

Mit freundlichen Grüßen

...zur Frage

Java Rekursion mit Potenzzahlen?

public static void main(String[] args) {
		System.out.println(potenzRechner(4,3));
	}

	public static int potenzRechner(int potenzzahl1, int potenzzahl2) {
		
		if (potenzzahl2 == 0) {
			return 1;
		} else if (potenzzahl2 == 1) {
			return potenzzahl1;
		} else {
			return potenzzahl1 * potenzRechner(potenzzahl1, potenzzahl2 - 1);
		}
	}

Ich habe den Code oben mit einer Rekursiven Methode, der die Potenz der mitgegebenen Zahlen (in dem Fall 4 und 3) errechnet. Jedoch kann ich nicht 100% nachvollziehen was im letzten else Zweig passiert.

(return potenzzahl1 * potenzRechner(potenzzahl1, potenzzahl2 - 1);)

Wird Potenzzahl1 (4) nicht mit sich selbst (4) mal genommen, und das Potenzzahl2 (2) mal? Also 4 * 4 * 4 = 64? Und das solange bis Potenzzahl2 bei 1 ankommt. Also (4^3) 4 * 4 * 4 = 64, (4^2) 4 * 4 = 16, (4^1) 4 = 4. Oder verstehe ich was falsch? Dann sollte doch theoretisch das Ergebnis (64) beim ersten durchlauf schon rauskommen, für was dann eine Aufgabe bei der man das Rekursiv machen soll?

Zusammengefasst: Kann mir jemand auf gut Deutsch diesen Ausdruck, in der die Rekursion sattfindet, erklären?

...zur Frage

Zweidimensionales Array wie rekursiv aufrufen?

Hallo,

ich habe ein zweidimensionales Array, bei der ich die BFS durchführen möchte,. Dabei möchte ich den anfangs übergebenen Graph, der als zweidimensionales Integerarray dargestellt ist( Java) im nächsten rekursiven Schritt so weitergeben als Parameter, dass quasi nur das zweidimensionale Array ohne den jeweils obersten Index bleibt, diesbezüglich möchte ich fragen, wie man das deklariert in Java.

danke im Voraus.

Anbei mein Quelltext:

public List<Integer> bfs(int[][] graph, int start) {
    List<Integer> result = new ArrayList<Integer>();
    if(!result.contains(start))
    {
    result.add(start);
    }
    int j=0;
    for(int i= 0; i<graph[j].length; i++)
    {
        if(!result.contains(graph[j][i]))
        {
            result.add(graph[j][i]);
        }
    ]
    bfs(graph[i][],start); // Hier soll der Graph erneut aufgerufen werden, nur ohne Index 0 , also 1 Zeile weniger 
    return result;
}

...zur Frage

Binäre Suche: Iterativ vs rekursiv?

Ich habe beides in Java implementiert, verstehe aber nicht, warum die rekursive Variante mehr als doppelt so schnell ist. Müsste es normalerweise nicht anders herum sein? Oder habe ich bei der iterativen Variante irgendetwas suboptimal gelöst?

public static int binarySearchIterative(int[] a, int z) {
  int left = 0;
  int right = a.length - 1;

  while (left <= right) {
    int midpoint = (int)((left + right) / 2);

    if (z == a[midpoint]) {
      return midpoint;
    }

    if (z < a[midpoint]) {
      right = midpoint - 1;
    }
    else {
      left = midpoint + 1;
    }
  }

  return -1;
}

public static int binarySearchRecursive(int[] a, int z, int left, int right) {
  int midpoint = (int)((left + right) / 2);

  if (right < left) {
    return -1;
  }

  if (z == a[midpoint]) {
    return midpoint;
  }

  if (z < a[midpoint]) {
    return binarySearchRecursive(a, z, left, midpoint - 1);
  }
  else {
    return binarySearchRecursive(a, z, midpoint + 1, right);
  }
}

...zur Frage

Hilfe: Java-Code?

Kann einer mir diesen Code ausführlich erklären?

public int gibBesitzer(int zeile, int spalte) {
        int index = zeile*3+spalte;
        return (spielInt>>>2*index & 0b11) - 1;
    }
public void besetzePosition(int zeile, int spalte, int spieler) {
        int index = zeile*3+spalte;
        spielInt &= ~(0b11 << 2*index); // clear
        spielInt |= (spieler+1) << 2*index;
    }

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen