Calcul combiné (triangle de Pascal) (Java)

Formule mathématique

Le calcul de combinaison peut être exprimé mathématiquement par la formule suivante.

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

Problèmes dans le programme

En programmation, il y a peu de cas où l'on vous demande de combiner en calculant selon la formule mathématique. La raison en est qu'il va ** déborder ** dans la multiplication de la molécule.

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

Par exemple, définir simplement n = 13 dépassera la valeur maximale du type int et débordera. Si n = 22, même le type long débordera. Par conséquent, il ne peut pas être calculé selon la formule.

Par conséquent, il sera mis en œuvre par une méthode de calcul qui ne déborde pas facilement. Dans cet article, j'expliquerai la méthode de calcul en utilisant le triangle de Pascal.

Calcul à l'aide du triangle de Pascal

Le triangle de Pascal est illustré dans la figure ci-dessous. [1] Il peut être créé en écrivant la somme de deux nombres côte à côte une étape vers le bas dans l'ordre à partir du haut. Il est connu pour correspondre au résultat du calcul de combinaison, nous allons donc l'utiliser.

Dans le programme, les triangles de Pascal sont créés à l'avance dans un tableau à deux dimensions, etc., et utilisés selon les besoins. Lors de la création d'un triangle de Pascal, le calcul n'est qu'une addition, et il n'y a pas de calcul d'échelle, il est donc moins susceptible de déborder que la formule.

[1] Citation de la figure http://www.mathlion.jp/article/ar103.html

Exemple d'implémentation

Implémentez jusqu'au point où le triangle de Pascal peut être créé dans un tableau à deux dimensions. Écrivez la première ligne dans un tableau, la première ligne dans un tableau, la deuxième ligne dans un autre tableau, et ainsi de suite.

Remplissez l'ordre du haut. Comme le montre la figure ci-dessous, en ajoutant l'élément supérieur à l'élément inférieur ** directement en dessous et un à droite **, il devient un triangle de Pascal.

D'autres conditions -Montant du calcul: en nCr, supposons que vous vouliez calculer jusqu'à environ n = 2000. -Contre-mesures de débordement: Dans le problème de la prise en compte des combinaisons, il n'est pas rare que la réponse elle-même déborde ainsi que le processus de calcul, donc la réponse est la suivante.

Calculez la réponse et répondez au reste divisé par 1000000007.

Ici, nous allons l'implémenter en supposant que de telles contre-mesures de débordement sont spécifiées (c'est-à-dire la mise en œuvre correcte selon la loi de 1000000007). Si aucune contre-mesure de dépassement n'est spécifiée, supprimez la ligne marquée "Contre-mesure de dépassement" dans le commentaire.

Pascal_Array

        //Préparation du tableau
		int c[][] = new int [2005][2005];//n=Créez avec une petite marge pour pouvoir faire 2000 pas.

		//Création du triangle de Pascal
		int mod = 1000000007;//Protection contre les débordements: spécifiée dans le problème.
		c[0][0]=1;//Le premier 1 est donné comme valeur initiale.
		for(int i=0;i<2003;i++) {//Tournez la boucle pour faire 2000 pas. Je le tourne avec un peu de marge pour ne pas avoir à penser aux détails.
			for(int j=0;j<2003;j++) {
				long tmp =  c[i][j]%mod;//Mesures de débordement
				c[i+1][j]+=tmp;
				c[i+1][j+1]+=tmp;
			}
		}

terminé. Par exemple, si vous voulez trouver 5C2, vous pouvez l'obtenir avec c [5] [2].

exemple

ABC132 D problème boules bleues et rouges https://atcoder.jp/contests/abc132/tasks/abc132_d