import math
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
if y == 1 or y == x:
print(1)
if y > x:
print(0)
else:
a = math.factorial(x)
b = math.factorial(y)
div = a // (b*(x-y))
print(div)
Dit programma met binominale coëfficiënten werkt, maar als ik twee van hetzelfde getal invoer dat gelijk zou moeten zijn aan 1 of als y groter is dan x, zou het gelijk moeten zijn aan 0.
Antwoord 1, autoriteit 100%
Deze vraag is oud, maar aangezien hij hoog in de zoekresultaten verschijnt, wil ik erop wijzen dat scipytwee functies heeft voor het berekenen van de binomiale coëfficiënten:
scipy.special.binom()-
import scipy.special # the two give the same results scipy.special.binom(10, 5) # 252.0 scipy.special.comb(10, 5) # 252.0 scipy.special.binom(300, 150) # 9.375970277281882e+88 scipy.special.comb(300, 150) # 9.375970277281882e+88 # ...but with `exact == True` scipy.special.comb(10, 5, exact=True) # 252 scipy.special.comb(300, 150, exact=True) # 393759702772827452793193754439064084879232655700081358920472352712975170021839591675861424
Merk op dat scipy.special.comb(exact=True)Python integers gebruikt, en daarom kan het willekeurig grote resultaten aan!
Qua snelheid geven de drie versies enigszins verschillende resultaten:
num = 300
%timeit [[scipy.special.binom(n, k) for k in range(n + 1)] for n in range(num)]
# 52.9 ms ± 107 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit [[scipy.special.comb(n, k) for k in range(n + 1)] for n in range(num)]
# 183 ms ± 814 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)each)
%timeit [[scipy.special.comb(n, k, exact=True) for k in range(n + 1)] for n in range(num)]
# 180 ms ± 649 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
(en voor n = 300zijn de binomiale coëfficiënten te groot om correct weergegeven te worden met float64-getallen, zoals hierboven weergegeven).
Antwoord 2, autoriteit 51%
Houd er rekening mee dat vanaf Python 3.8de standaardbibliotheek de math.combfunctie om de binomiale coëfficiënt te berekenen:
wiskunde.comb(n, k)
wat het aantal manieren is om k items uit n items te kiezen zonder herhaling n! / (k! (n - k)!):
import math
math.comb(10, 5) # 252
math.comb(10, 10) # 1
Antwoord 3, autoriteit 22%
Hier is een versie die daadwerkelijk de juiste formulegebruikt. 🙂
#! /usr/bin/env python
''' Calculate binomial coefficient xCy = x! / (y! (x-y)!)
'''
from math import factorial as fac
def binomial(x, y):
try:
return fac(x) // fac(y) // fac(x - y)
except ValueError:
return 0
#Print Pascal's triangle to test binomial()
def pascal(m):
for x in range(m + 1):
print([binomial(x, y) for y in range(x + 1)])
def main():
#input = raw_input
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
print(binomial(x, y))
if __name__ == '__main__':
#pascal(8)
main()
…
Hier is een alternatieve versie van binomial()Ik schreef enkele jaren geleden die niet gebruikt math.factorial(), die niet bestond in oude versies van Python. Het retourneert echter 1 als R niet bereikbaar is (0, N + 1).
def binomial(n, r):
''' Binomial coefficient, nCr, aka the "choose" function
n! / (r! * (n - r)!)
'''
p = 1
for i in range(1, min(r, n - r) + 1):
p *= n
p //= i
n -= 1
return p
Antwoord 4, Autoriteit 8%
Dus, deze vraag komt eerst op als u zoekt naar “Implement Binomial Coëfficiënten in Python”. Alleen Dit antwoord in zijn tweede deel bevat een efficiënte implementatie die afhankelijk is van de multiplicatieve formule . Deze formule voert het naakte minimumaantal van vermenigvuldigingen uit. De onderstaande functie is niet afhankelijk van ingebouwde ins of invoer:
def fcomb0(n, k):
'''
Compute the number of ways to choose $k$ elements out of a pile of $n.$
Use an iterative approach with the multiplicative formula:
$$\frac{n!}{k!(n - k)!} =
\frac{n(n - 1)\dots(n - k + 1)}{k(k-1)\dots(1)} =
\prod_{i = 1}^{k}\frac{n + 1 - i}{i}$$
Also rely on the symmetry: $C_n^k = C_n^{n - k},$ so the product can
be calculated up to $\min(k, n - k).$
:param n: the size of the pile of elements
:param k: the number of elements to take from the pile
:return: the number of ways to choose k elements out of a pile of n
'''
# When k out of sensible range, should probably throw an exception.
# For compatibility with scipy.special.{comb, binom} returns 0 instead.
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
total_ways = 1
for i in range(min(k, n - k)):
total_ways = total_ways * (n - i) // (i + 1)
return total_ways
Ten slotte, als u nog grotere waarden nodig heeft en het niet erg vindt om enige nauwkeurigheid uit te wisselen, Stirling’s benaderingis waarschijnlijk de juiste keuze.
Antwoord 5, autoriteit 2%
Hier is een functie die de binominale coëfficiënten recursief berekent met behulp van voorwaardelijke uitdrukkingen
def binomial(n,k):
return 1 if k==0 else (0 if n==0 else binomial(n-1, k) + binomial(n-1, k-1))
Antwoord 6, autoriteit 2%
Je programma gaat verder met de tweede if-instructie in het geval van y == x, wat een ZeroDivisionErrorveroorzaakt. U moet de verklaringen elkaar uitsluiten; de manier om dat te doen is door elif(“else if”) te gebruiken in plaats van if:
import math
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
if y == x:
print(1)
elif y == 1: # see georg's comment
print(x)
elif y > x: # will be executed only if y != 1 and y != x
print(0)
else: # will be executed only if y != 1 and y != x and x <= y
a = math.factorial(x)
b = math.factorial(y)
c = math.factorial(x-y) # that appears to be useful to get the correct result
div = a // (b * c)
print(div)
Antwoord 7, autoriteit 2%
En deze? 🙂 Het gebruikt de juiste formule, vermijdt math.factorialen neemt minder vermenigvuldigingsoperaties:
import math
import operator
product = lambda m,n: reduce(operator.mul, xrange(m, n+1), 1)
x = max(0, int(input("Enter a value for x: ")))
y = max(0, int(input("Enter a value for y: ")))
print product(y+1, x) / product(1, x-y)
Om rekenkunde met grote gehele getallen te vermijden, kunt u ook drijvende-kommagetallen gebruiken,
product(a[i])/product(b[i])naar product(a[i]/b[i])en herschrijf het bovenstaande programma als:
import math
import operator
product = lambda iterable: reduce(operator.mul, iterable, 1)
x = max(0, int(input("Enter a value for x: ")))
y = max(0, int(input("Enter a value for y: ")))
print product(map(operator.truediv, xrange(y+1, x+1), xrange(1, x-y+1)))
Antwoord 8, autoriteit 2%
Voor Python 3 heeft scipy de functie scipy.special.comb, die zowel drijvende-komma als exacte integer-resultaten kan produceren
import scipy.special
res = scipy.special.comb(x, y, exact=True)
Zie de documentatie voor scipy.special.comb.
Voor Python 2 bevindt de functie zich in scipy.misc en werkt op dezelfde manier:
import scipy.misc
res = scipy.misc.comb(x, y, exact=True)
Antwoord 9, autoriteit 2%
Ik raad aan om dynamisch programmeren (DP) te gebruiken voor het berekenen van binomiale coëfficiënten. In tegenstelling tot directe berekening, vermijdt het vermenigvuldigen en delen van grote getallen. Naast de recursieve oplossing slaat het eerder opgeloste overlappende subproblemen op in een tabel voor snel opzoeken. De onderstaande code toont bottom-up (tabel) DP en top-down (gememoriseerde) DP-implementaties voor het berekenen van binomiale coëfficiënten.
def binomial_coeffs1(n, k):
#top down DP
if (k == 0 or k == n):
return 1
if (memo[n][k] != -1):
return memo[n][k]
memo[n][k] = binomial_coeffs1(n-1, k-1) + binomial_coeffs1(n-1, k)
return memo[n][k]
def binomial_coeffs2(n, k):
#bottom up DP
for i in range(n+1):
for j in range(min(i,k)+1):
if (j == 0 or j == i):
memo[i][j] = 1
else:
memo[i][j] = memo[i-1][j-1] + memo[i-1][j]
#end if
#end for
#end for
return memo[n][k]
def print_array(memo):
for i in range(len(memo)):
print('\t'.join([str(x) for x in memo[i]]))
#main
n = 5
k = 2
print("top down DP")
memo = [[-1 for i in range(6)] for j in range(6)]
nCk = binomial_coeffs1(n, k)
print_array(memo)
print("C(n={}, k={}) = {}".format(n,k,nCk))
print("bottom up DP")
memo = [[-1 for i in range(6)] for j in range(6)]
nCk = binomial_coeffs2(n, k)
print_array(memo)
print("C(n={}, k={}) = {}".format(n,k,nCk))
Opmerking: de grootte van de memotabel is ingesteld op een kleine waarde (6) voor weergavedoeleinden, deze moet worden vergroot als u binominale coëfficiënten berekent voor grote n en k.
Antwoord 10, autoriteit 2%
De eenvoudigste manier is om de vermenigvuldigingsformule te gebruiken. Het werkt zoals verwacht voor (n,n) en (n,0).
def coefficient(n,k):
c = 1.0
for i in range(1, k+1):
c *= float((n+1-i))/float(i)
return c
Antwoord 11
Een beetje verkorte multiplicatieve variant gegeven door PM 2Ringen alisianoi. Werkt met python 3 en vereist geen pakketten.
def comb(n, k):
# Remove the next two lines if out-of-range check is not needed
if k < 0 or k > n:
return None
x = 1
for i in range(min(k, n - k)):
x = x*(n - i)//(i + 1)
return x
Of
from functools import reduce
def comb(n, k):
return (None if k < 0 or k > n else
reduce(lambda x, i: x*(n - i)//(i + 1), range(min(k, n - k)), 1))
De deling wordt direct na vermenigvuldiging gedaan om geen hoge getallen te verzamelen.
Antwoord 12
Het is een goed idee om een recursieve definitie toe te passen, zoals in het antwoord van Vadim Smolyakov, gecombineerd met een DP (dynamische programmering), maar voor de laatste kun je de lru_cache-decorator van module functools toepassen:
import functools
@functools.lru_cache(maxsize = None)
def binom(n,k):
if k == 0: return 1
if n == k: return 1
return binom(n-1,k-1)+binom(n-1,k)
Antwoord 13
Voor iedereen op zoek naar het log van de binomiale coëfficiënt (Theano roept dit binomln), heeft het:
from numpy import log
from scipy.special import betaln
def binomln(n, k):
"Log of scipy.special.binom calculated entirely in the log domain"
return -betaln(1 + n - k, 1 + k) - log(n + 1)
(en als uw taal / bibliotheek mist betaln, maar heeft gammaln, zoals GO, geen angst, sinds betaln(a, b)Is slechts gammaln(a) + gammaln(b) - gammaln(a + b), per Mathworld .)