Úloha 5: Kombinační číslo n nad k

Začátečník kombinatorika cyklus for optimalizace MathML

Cíl úlohy

Vytvořte skript, který z formuláře načte nezáporná celá čísla n a k a vypočítá hodnotu kombinačního čísla (nk) (čte se „n nad k“). Skript optimalizuje výpočet krácením a zamezí zbytečnému přetečení.

Matematická definice kombinačního čísla (MathML)

Kombinační číslo udává počet k-prvkových podmnožin z množiny o n prvcích (kombinace bez opakování):

( n k ) = n! k!⋅(n−k)!

Důležitá vlastnost symetrie, která výrazně urychluje výpočet:

( n k ) = ( n n−k )

Úvahy a doporučený postup řešení

  • Proč nepočítat přímo n! ? Kdybychom počítali 100!/(99!⋅1!), hodnota 100! je obrovské číslo, které v PHP přeteče. Přitom výsledek je pouhých 100! Proto je nutné zkrátit čitatele a jmenovatele ještě před násobením.
  • Optimalizace symetrie: Pokud k>n/2, nahradíme $k = $n - $k. Místo např. (5048) počítáme mnohem jednodušší (502)=50⋅492⋅1.
  • Okrajové případy: Pro k=0 nebo k=n je výsledek vždy 1.
  • Výměna n a k: Pokud uživatel omylem zadá k>n, hodnoty prohodíme a uživatele upozorníme.

Doplňující otázky k zamyšlení a náměty na rozšíření

  • 1. Jak souvisí kombinační čísla s Pascalovým trojúhelníkem a binomickou větou (a+b)n?
  • 2. Jaká je pravděpodobnost výhry ve Sportce (tah 6 čísel ze 49)? Jak ji spočítat pomocí kombinačního čísla (496)?
  • 3. Proč je výhodné v cyklu střídavě násobit a dělit, aby mezivýsledky zůstávaly co nejmenší?
  • 4. Zkuste skript rozšířit o vizuální vykreslení prvních několika řádků Pascalova trojúhelníku do HTML tabulky!

Vyzkoušejte funkční řešení: Otevřít vzorovou úlohu kombcislo.php