Black Friday je tu! Využij jedinečnou příležitost a získej až 80 % znalostí navíc zdarma! Více zde
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
BF extended 2022

Algoritmus pro řešení set-cover problému

V minulé lekci, Faktoriál, jsme si ukázali algoritmus pro výpočet faktoriálu včetně popisu a zdrojového kódu bez rekurze i s rekurzí.

Set cover problem - zjištění, které množiny lze vyřadit, aby i po jejich vyřazení sjednocení zbývajících množin bylo rovno sjednocení všech množin.

Asi to bude lépe pochopitelné na příkladu: máme zadány množiny:
{1,2,3}
{2,4}
{4,5,6}

jejich sjednocení je
{1,2,3,4,5,6}

ze zadaných množin vyberte co nejméně množin tak, aby jejich sjednocení stále bylo
{1,2,3,4,5,6}

k tomu nám stačí množiny
{1,2,3}
{4,5,6}

Zadání a diskuze: http://www.itnetwork.cz/…0ce0650db47f#…

Kód byl napsán za hodinu, takže nejsou nijak ošetřeny vstupy/výstupy, není to moc otestované, kód není moc hezký apod. :)

V další lekci, Matice a základní operace s nimi, nejen v kódu, se seznámíme s pojmem matice a naučíme se základní matematické operace, které na ně lze aplikovat.


Galerie

Program byl vytvořen v roce 2012.

 

Stáhnout

Stažením následujícího souboru souhlasíš s licenčními podmínkami

Staženo 255x (28.84 kB)
Aplikace je včetně zdrojových kódů

 

Předchozí článek
Faktoriál
Všechny články v sekci
Matematické algoritmy
Přeskočit článek
(nedoporučujeme)
Matice a základní operace s nimi, nejen v kódu
Program pro vás napsal Luboš Běhounek Satik
Avatar
Uživatelské hodnocení:
2 hlasů
Autor se nyní živí programováním v C++, ale jeho nejoblíbenějším jazykem je C#. První hru napsal okolo roku 2000.
Aktivity

 

 

Komentáře

Avatar
Člen
Člen
Avatar
Člen:6.8.2014 19:23

Holy [email protected]! Ono to funguje...
Dobra praca :D

Odpovědět
6.8.2014 19:23
...
Avatar
David Roško
Člen
Avatar
David Roško:24.2.2015 1:13

Ahoj, urcite diky. Ale je tu jedna otazka. Proc je to tak pomale? Presen toto jsem resil pomoci brutforce metody a bezi to dokonce rychleji (Presto stale pomalu). Nenapada te nejake reseni jak to trochu nakopnout tvuj kod? :)
Jinak jeste jednou diky.

Odpovědět
24.2.2015 1:13
Nikdy neříkej, že to nejde.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 2 zpráv z 2.