Le nombre de 12 morceaux prélevés sur 3 types de fruits peut être calculé par la méthode de Combinaison en double lorsqu'il y a 12 morceaux ou plus de chaque fruit. ça peut. Cependant, s'il existe une limite supérieure de 6 pour chaque fruit, cette méthode ne peut pas être utilisée. Par conséquent, il est nécessaire de réaliser la combinaison de chevauchement avec une limite supérieure par une autre méthode. Dans cet exemple, le nombre est équivalent au cas où les dés sont secoués trois fois et le nombre total de lancers est de 12, donc cette formule peut être utilisée de manière inattendue (je pense).
Il existe une méthode de calcul de ces combinaisons qui se chevauchent avec une limite supérieure basée sur le principe de déduction. Cliquez ici pour accéder au Site de référence.
Depuis Site de référence, définissez la limite supérieure sur m, le type de fruit sur n (le nombre de secousses) et le total. Si t, il peut être calculé par la formule suivante.
\begin{eqnarray}
\sum_{ k = 0 }^{ [ \frac{ t - n }{ m } ]} (-1)^k \cdot {}_n \mathrm{ C }_k \cdot {}_n \mathrm{ H }_{ t - n - m \cdot k }
\end{eqnarray}
25 lorsque m = 6, n = 3 et t = 12.
Python3
import functools as ft
def permutation(n, k):
if k > n:
return 0
elif 0 < k <= n:
return ft.reduce(lambda x, y:x * y, [n - v for v in range(k)])
else:
return 1
def factorial(n):
return permutation(n, n - 1)
def combination(n, k):
return int(permutation(n, k) / factorial(k))
def homogeneous(n, k):
return combination(n + k - 1, k)
def homogeneous_with_limit(m, n, t):
return sum([(-1)**k * combination(n, k) * homogeneous(n, t - n - m * k) \
for k in range(0, int((t - n) / m) + 1)])
if __name__ == '__main__':
print(homogeneous_with_limit(6, 3, 12))
Résultat de sortie
25
Ruby2.4
def permutation(n, k)
if k > n
0
elsif 0 < k && k <= n then ((n - k + 1)..n).inject(:*)
else 1
end
end
def factorial(n)
permutation(n, n - 1)
end
def combination(n, k)
(permutation(n, k) / factorial(k)).to_i
end
def homogeneous(n, k)
combination(n + k - 1, k)
end
def homogeneous_with_limit(m, n, t)
(0..((t - n) / m)).inject(0) {|s, k| s + (-1)**k * combination(n, k) * homogeneous(n, t - n - m * k)}
end
p homogeneous_with_limit(6, 3, 12)
Résultat de sortie
25
PHP7.1
<?php
function permutation(int $n, int $k) : int {
if ($k > $n) return 0;
elseif (0 < $k && $k <= $n)
return array_reduce(range($n - $k + 1, $n), function ($c, $v) { return $c *= $v; }, 1);
else return 1;
}
function factorial(int $n) : int {
return permutation($n, $n - 1);
}
function combination(int $n, int $k) : int {
return intval(permutation($n, $k) / factorial($k));
}
function homogeneous(int $n, int $k) : int {
return combination($n + $k - 1, $k);
}
function homogeneous_with_limit(int $m, int $n, int $t) : int {
return array_reduce(range(0, intval(($t - $n) / $m)), function ($s, $k) use ($m, $n, $t) {
return $s += (-1) ** $k * combination($n, $k) * homogeneous($n, $t - $n - $m * $k);
});
}
print(homogeneous_with_limit(6, 3, 12));
Résultat de sortie
25
Golang
package main;
import (
"fmt"
"math"
)
func permutation(n int, k int) int {
v := 1
if 0 < k && k <= n {
for i := 0; i < k; i++ {
v *= (n - i)
}
} else if k > n {
v = 0
}
return v
}
func factorial(n int) int {
return permutation(n, n - 1)
}
func combination(n int, k int) int {
return permutation(n, k) / factorial(k)
}
func homogeneous(n int, k int) int {
return combination(n + k - 1, k)
}
func homogeneous_with_limit(m int, n int, t int) int {
e := int((t - n) / m) + 1
v := 0
for i := 0; i < e; i++ {
v += int(math.Pow(-1, float64(i))) * combination(n, i) * homogeneous(n, t - n - m *i)
}
return v
}
func main () {
fmt.Printf("%v\n", homogeneous_with_limit(6, 3, 12))
}
Résultat de sortie
25
Le principe de déduction est également utilisé dans la preuve de Eratostenes Sieve. Je manque aussi le symbole gaussien ([x]).
Il y a beaucoup de défis, par exemple, si vous secouez 3 dés et que les jets sont (3,5,4) et (3,4,5), ce sera 12, mais si vous ne considérez pas un tel ordre, un autre Vous devez adopter une approche. De plus, si la valeur maximale des trois yeux coupés en dés n'est pas de 6 mais de valeurs différentes, il est nécessaire d'adopter une autre approche. Le cas où l'ordre n'est pas pris en compte a fait l'objet de l'algorithme quelque part, mais je n'ai pas pu le formuler, et j'ai fini par tourner la boucle, alors j'aimerais réessayer. Si la valeur maximale est différente, trouvez la formule graduelle quelque part et c'est clair.
Recommended Posts