De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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.

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
zondag 12 oktober 2003


klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2019 WisFaq - versie IIb