Hier ist der Code zu einem Teilmengenproblem mit den Argumenten n und k. n steht für die Gesamtzahl der Schüler und k für die Anzahl der Schüler, die ich aus n herausholen möchte. Der Code versucht, die Anzahl der möglichen Kombinationen der Anzahl der Schüler aus der Anzahl n Schüler anzugeben.
%Vor%Ich verstehe den ersten Teil des rekursiven Aufrufs, aber ich habe Probleme, den + Teilmengen (n-1, k) Teil zu verstehen. Kann mir das jemand erklären?
Die Rekursion basiert auf einer einfachen Beobachtung, für die ich ein kombinatorisches Argument geben werde, warum es wahr ist, und nicht einen mathematischen Beweis durch Formeln.
Wenn Sie k elements aus n auswählen, gibt es zwei Fälle:
#n
#n
Da sich diese Ereignisse gegenseitig ausschließen, wird die Gesamtmenge der Kombinationen durch die Anzahl der Kombinationen angegeben, wenn Sie #n wählen, und jene, wenn Sie #n nicht auswählen.
#n
Da wir bereits ein Element ausgewählt haben, müssen wir nur noch ein anderes k-1 -Element auswählen. Da wir uns bereits für ein Element entschieden haben - ob es enthalten ist oder nicht - müssen wir nur noch die restlichen n-1 -Elemente berücksichtigen.
Somit ist die Anzahl der Kombinationen zum Auswählen des Elements #n durch
#n auswählen
Es gibt noch k Elemente, die ausgewählt werden können, aber da wir uns bereits für das Element #n entschieden haben, bleiben nur noch n - 1 -Elemente übrig. Also:
Die Rekursion verwendet die Tatsache, dass wir normalerweise zwischen zwei Situationen unterscheiden können, Lösungen, bei denen das Element n Teil dieser Lösung ist, und diejenigen, bei denen dies nicht der Fall ist.
Eine solche Unterscheidung kann jedoch nicht immer getroffen werden:
n == k im folgenden Code) k == 0 im folgenden Code) In diesen Fällen gibt es nur genau eine Lösung, also
%Vor%Um das zu tun, müssen wir uns davon überzeugen (oder beweisen), dass der Basisfall immer irgendwann getroffen wird.
Nehmen wir an, dass n < k irgendwann ist. Da nach unserer Annahme n ursprünglich größer oder gleich k war, muss muss ein Punkt sein wo n = k , weil n und k zusammen oder nur% verringern co_de% verringert sich um eins, dh es folgt
Dies bedeutet, dass ein Aufruf an n stattgefunden haben muss, damit subset(n - 1, k) unter n sinkt. Dies ist jedoch nicht möglich, da wir einen Basisfall auf k haben, wo wir eine Konstante n = k zurückgeben.
Wir folgern, dass entweder 1 irgendwann abfällt, also n , oder in Unison genau n = k mal so klein wie k .
Somit funktioniert der Basisfall.
Dies ist eher ein mathematisches Problem und keine Programmierfrage. Was Sie tun, berechnet den Binomialkoeffizienten, die Formel ist
%Vor%Eine ausführliche Erläuterung finden Sie hier . Eine rekursive Lösung kann hier gesehen werden. Falls der angegebene Link ungültig wird, suchen Sie einfach mit Google. Ich bezweifle, dass Sie eine bessere Erklärung für SO erhalten werden, als nachdem Sie diesen Artikel auf Wikipedia gelesen haben.
Das Codefragment:
%Vor%verwendet zwei kombinatorische Fakten:
%Vor%als Basisfälle.
Als nächstes folgenden rekursiven Aufruf:
%Vor%übersetzt die folgende Tatsache direkt in den Code:
%Vor%Wenn Sie Schwierigkeiten haben zu verstehen, wie die obige Gleichung gilt, lesen Sie weiter: In nCr wählen wir r Elemente aus n. Die Auswahlmöglichkeiten können in zwei sich gegenseitig ausschließende Klassen klassifiziert werden, wenn wir einen bestimmten Gegenstand betrachten:
Element tritt unter dem ausgewählten Element
aufIn diesem Fall müssen wir die restlichen r-1 Elemente aus den verbleibenden n-1 Elementen auswählen. Dies kann in (n-1) C (k-1) erfolgen.
Element tritt nicht unter dem ausgewählten Element
aufIn diesem Fall müssen wir alle r Elemente aus den verbleibenden n-1 Elementen auswählen, die auf (n-1) Ck-Wegen ausgeführt werden können.
Wir fügen diese zwei hinzu, wie ich bereits sagte, diese zwei Klassen schließen sich gegenseitig aus und bilden daher zusammen die Gesamtwege der Auswahl von r Elementen aus n.