Die Anzahl von 12 Stücken, die aus 3 Arten von Früchten entnommen wurden, kann nach der Methode der doppelten Kombination berechnet werden, wenn 12 oder mehr Stücke jeder Frucht vorhanden sind. es kann. Wenn es jedoch eine Obergrenze von 6 für jede Frucht gibt, kann diese Methode nicht angewendet werden. Daher ist es notwendig, die überlappende Kombination mit einer Obergrenze durch ein anderes Verfahren zu realisieren. In diesem Beispiel entspricht die Anzahl dem Fall, in dem die Würfel dreimal geschüttelt werden und die Gesamtzahl der Würfe 12 beträgt, sodass diese Formel unerwartet verwendet werden kann (glaube ich).
Es gibt eine Methode zur Berechnung solcher überlappenden Kombinationen mit einer Obergrenze basierend auf dem Abzugsprinzip. Klicken Sie hier für Referenzseite.
Setzen Sie auf Referenzseite die Obergrenze auf m, die Fruchtart auf n (die Anzahl der geschüttelten Brötchen) und die Gesamtzahl. Wenn t, kann es durch die folgende Formel berechnet werden.
\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 wenn m = 6, n = 3 und 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))
Ausgabeergebnis
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)
Ausgabeergebnis
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));
Ausgabeergebnis
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))
}
Ausgabeergebnis
25
Das Abzugsprinzip wird auch beim Nachweis von [Eratostenes Sieve] verwendet (http://qiita.com/hiroykam/items/bf1edde04db8d54f4d1f). Ich vermisse auch das Gaußsche Symbol ([x]).
Es gibt viele Herausforderungen, zum Beispiel, wenn Sie 3 Würfel schütteln und die Würfe (3,5,4) und (3,4,5) sind, sind es 12, aber wenn Sie eine solche Reihenfolge nicht berücksichtigen, eine andere Sie müssen einen Ansatz wählen. Wenn der Maximalwert der drei gewürfelten Augen nicht 6, sondern unterschiedliche Werte beträgt, ist ein anderer Ansatz erforderlich. Der Fall, in dem die Reihenfolge nicht berücksichtigt wird, war irgendwo Gegenstand des Algorithmus, aber ich konnte ihn nicht formulieren, und am Ende drehte ich die Schleife, sodass ich es erneut versuchen möchte. Wenn der Maximalwert unterschiedlich ist, suchen Sie die Graduierungsformel irgendwo und es ist klar.
Recommended Posts