Aantal combinatie berekenen bij grote n

Hoe bereken ik met de computer C(n,k) of n!/(n-k)!k! voor n173?

Wim Va
Iets anders - zaterdag 11 oktober 2003

Antwoord

Je kan voorkomen dat je tussenresultaten het bereik van de getallen in jouw programmeertaal overstijgen door afwisselend vermenigvuldigingen en delingen uit te voeren (in plaats van eerst alle vermenigvuldigingen om n! te bepalen)

C(n,k)
= n!/[(n-k)!k!]
= n/1 . (n-1)/2 . ... . (n-k+1)/k

In een of andere pseudocode bekom je dan

temp=1
for j = 1 to k
   temp=temp*(n+1-j)
   temp=temp/j
next j
C=temp

Merk vooral op dat je door eerst te vermenigvuldigen en dan pas te delen je in het domein van de "integers" kan blijven, maw de variabele temp zal op elk moment in de subroutine geheel zijn (kan je dit zelf bewijzen?)

Voor nog veel grotere argumenten kan je overschakelen op logaritmen, of, niet geheel los daar van, de benaderingsformule van Stirling voor faculteiten.

zondag 12 oktober 2003

©2001-2024 WisFaq