Kombinationsberechnung (Pascal-Dreieck) (Java)

Mathematische Formel

Die Kombinationsberechnung kann durch die folgende Formel mathematisch ausgedrückt werden.

nCr=\frac{n!}{r!{(n-r)!}}

Probleme im Programm

In der Programmierung gibt es nur wenige Fälle, in denen Sie aufgefordert werden, durch Berechnen nach der mathematischen Formel zu kombinieren. Der Grund ist, dass es bei der Multiplikation des Zählers ** überläuft **.

n! = n\times(n-1)\times(n-2)\cdots2\times1

Wenn Sie beispielsweise nur n = 13 setzen, wird der Maximalwert von int type und overflow überschritten. Wenn n = 22 ist, läuft auch ein langer Typ über. Daher kann es nicht nach der Formel berechnet werden.

Daher wird es durch eine Berechnungsmethode implementiert, die nicht leicht überläuft. In diesem Artikel werde ich die Berechnungsmethode anhand des Pascalschen Dreiecks erläutern.

Berechnung mit dem Pascalschen Dreieck

Pascals Dreieck ist in der folgenden Abbildung dargestellt. [1] Sie können erstellt werden, indem Sie die Summe zweier nebeneinander angeordneter Zahlen einen Schritt nach unten in der Reihenfolge von oben schreiben. Es ist bekannt, dass es dem Ergebnis der Kombinationsberechnung entspricht, daher werden wir dies verwenden.

Im Programm werden Pascals Dreiecke im Voraus in einem zweidimensionalen Array usw. erstellt und nach Bedarf verwendet. Beim Erstellen eines Pascal-Dreiecks handelt es sich bei der Berechnung nur um eine Addition, und es erfolgt keine Berechnung des Maßstabs, sodass die Wahrscheinlichkeit eines Überlaufs geringer ist als bei der Formel.

[1] Abbildung Zitat http://www.mathlion.jp/article/ar103.html

Implementierungsbeispiel

Implementieren Sie bis zu dem Punkt, an dem das Pascal-Dreieck in einem zweidimensionalen Array erstellt werden kann. Schreiben Sie die erste Zeile in ein Array, die erste Zeile in ein Array, die zweite Zeile in ein anderes Array usw.

Füllen Sie die Reihenfolge von oben aus. Wie in der folgenden Abbildung gezeigt, wird das obere Element durch Hinzufügen des oberen Elements zum unteren ** direkt darunter und eines rechts ** zu einem Pascal-Dreieck.

Andere Bedingungen -Berechnungsbetrag: Angenommen, Sie möchten in nCr bis zu etwa n = 2000 berechnen. -Überlauf-Gegenmaßnahmen: Bei dem Problem, Kombinationen zu berücksichtigen, kommt es nicht selten vor, dass die Antwort selbst überläuft, ebenso wie der Berechnungsprozess. Daher lautet die Antwort wie folgt.

Berechnen Sie die Antwort und beantworten Sie den Rest geteilt durch 1000000007.

Hier werden wir es unter der Annahme implementieren, dass solche Überlauf-Gegenmaßnahmen spezifiziert sind (dh die korrekte Implementierung nach dem Gesetz von 1000000007). Wenn keine Überlauf-Gegenmaßnahme angegeben ist, löschen Sie die Zeile mit der Bezeichnung "Überlauf-Gegenmaßnahme" im Kommentar.

Pascal_Array

        //Array-Vorbereitung
		int c[][] = new int [2005][2005];//n=Erstellen Sie mit einem kleinen Rand, damit Sie 2000 Schritte ausführen können.

		//Pascals Dreieckskreation
		int mod = 1000000007;//Überlaufschutz: Im Problem angegeben.
		c[0][0]=1;//Die oberste 1 wird als Anfangswert angegeben.
		for(int i=0;i<2003;i++) {//Drehen Sie die Schleife, um 2000 Schritte zu machen. Ich drehe es mit einem kleinen Rand, damit ich nicht über die Details nachdenken muss.
			for(int j=0;j<2003;j++) {
				long tmp =  c[i][j]%mod;//Überlaufmaßnahmen
				c[i+1][j]+=tmp;
				c[i+1][j+1]+=tmp;
			}
		}

erledigt. Wenn Sie beispielsweise 5C2 suchen möchten, können Sie es mit c [5] [2] abrufen.

Beispiel

ABC132 D Problem Blaue und rote Kugeln https://atcoder.jp/contests/abc132/tasks/abc132_d