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

Beitragsersteller

24.10.2021, 17:16

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

jdqwio2

Beitragsersteller

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

Beitragsersteller

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

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.

Ähnliche Beiträge

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.

...zum Beitrag

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);
}

...zum Beitrag

Wie berechne ich eine Quadratzahl rekursiv? Also eine Methode wird aufgerufen mit einer Zahl und in der Methode wird rekursiv die Quadratzahl gebildet (Java)?

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

...zum Beitrag

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?

...zum Beitrag

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));
  }
}

...zum Beitrag

Wie programmiert Ihr?

Hallo,

schreibt Ihr alles aus dem Kopf oder schaut Ihr als Programmierer auch nach wie z.B Befehle oder auch ganze Abschnitte Code den Ihr anschließend verwendet? Was macht ein Programmierer aus? Muss er alles aus dem Kopf schreiben können oder viele Bibliotheken auswendig lernen?

Habt Ihr eventuell eine Übersicht vieler Bibliotheken für Java?

LG und vielen Dank für die Antworten!

...zum Beitrag

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();
}

...zum Beitrag

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;
}

...zum Beitrag

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);
  }
}

...zum Beitrag

Array nach Wert prüfen rekrusiv (java)?

Hi sagen wir mal ich habe einen COde der so aussieht:

  public static int calculateBinomialCoefficient (int n, int k)
   {
      if (k == 1)
         return n;
      else if (n >= k && k == 0)
         return 1;
      else
       return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
 
   }
}

Nun hat mein Prof gemeint, dass die rekursion nicht linear ist und zu vielen gleichen Aufrufen mit gleichen Parameterkombis führt. EIne Möglichkeit damit das besser läuft ist es berechente Binomialkoeffizienten in einem zwei dimensionalen Array zu speichern und vor einem rekursiven Aufruf zu prüfen, ob die Lösung bereits 1x exisitert hat. EInen Array haben wir schon gegeben, mit der perfekten Länge.Dann habe ich mir das überlegt:

 public static int calculateBinomialCoefficient (int n, int k)
  {
   if (k == 1)
     return n;
   else if (n >= k && k == 0)
     return 1;
   else
for (int a=0; a<array.length;a++)
{
for (int b=0; b<array.length;b++)
{
if (array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k)
{
return array[a][b];
}else{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
if(array[a][b]==0){
array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
}
}
     
 
  }
}

(Ich hoffe kann man erkennen Tabs sind bisschen verrückt.)

Aber warum funktioniert das nun nicht? Habe doch alles beachtet oder?

...zum Beitrag

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;
    }

...zum Beitrag

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

...zum Beitrag

Rekursive Darstellung des Horner Schema?

Wie der Fragetitel schon sagt, muss ich das Horner Schema rekursiv darstellen (in beliebiger Programmiersprache).
Ich hab einige Stunden damit verbracht, aber bin auf keine rekursive Lösung gekommen, die für Polynome mit Grad >= 3 funktioniert.

Anzumerken ist auch, dass nach einer Multiplikation kein rekursiver Abstieg erfolgen darf und aufgrund der Def. des Horner Schema darf auch nicht mit Potenzen gearbeitet werden.

Die Lösung muss rein auf rekursivem Auf-/Abstieg basieren.

Zu meinen Ansätzen:
Je nach dem, wie ich versucht habe das Schema rekursiv darzustellen, wurde entweder das x nicht richtig ausgeklammert, sodass das Anfangspolynom nicht richtig dargestellt wurde, oder die Anordnung der Koeffizienten war falsch, weshalb das Ergebnis dementsprechend falsch wurde.

Ich hoffe, dass mir hier geholfen werden kann!

Danke für eure Mühen vorab

...zum Beitrag

Java return bedeutung?

Hallo, zb habe ich hier stehen:

public static final double R = 18;

public static double berechneDruck(double v,double t){ 
        return R *t/v;
}

was genau macht das return hier? kann mit das bitte einer ganz einfach erklären^^ danke:)

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen