Úloha 5: Kombinační číslo n nad k
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 (č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í):
Důležitá vlastnost symetrie, která výrazně urychluje výpočet:
Úvahy a doporučený postup řešení
- Proč nepočítat přímo n! ? Kdybychom počítali , hodnota 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 , nahradíme
$k = $n - $k. Místo např. počítáme mnohem jednodušší . - Okrajové případy: Pro nebo je výsledek vždy
1. - Výměna n a k: Pokud uživatel omylem zadá , 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 ?
- 2. Jaká je pravděpodobnost výhry ve Sportce (tah 6 čísel ze 49)? Jak ji spočítat pomocí kombinačního čísla ?
- 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