Cvičení 7

Úloha 7.1

Pro následující rovinný (planární) graf nalezněte maximální tok metodou severní cesty nasycováním hran.

Obrázek 1: Zadaný graf

Řešení:

Řešení úlohy 7.1

Názorná ukázka Floyd-Warshallova algoritmu, aplikace metody severní cesty a Ford-Fulkersonova algoritmu je ve skriptech doc. Mockové Základy teorie dopravy - úlohy.

Úloha 7.2

Sestrojte Huffmanův kód, jsou-li dány absolutní četnosti výskytu písmen v textu: a:45, b:13, c:12, d:16, e:9, f:5.

Řešení:

kod.pdf (z knihy Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, Second Edition, MIT Press, 2002)

Úloha 7.3

Napište program v jazyce C pro výpočet hodnoty polynomu v bodě pomocí Hornerova schématu. Data načtěte z textového souboru, který má následující strukturu: na prvním řádku je číslo představující stupeň polynomu a na dalším řádku koeficienty oddělené bílým znakem od největšího stupně. Jméno souboru zadejte z klávesnice. Po načtení dat ze souboru se program dotáže na bod, ve kterém má spočítat hodnotu polynomu. Pro uložení koeficintů využijte vektor z knihovny STL.

Řešení:

Dev C++:	horner.dev, horner.cpp
CodeBlocks:	horner.cbp, horner.cpp
Soubor s daty:	polynom.txt

Úloha 7.4

Napište program implementující Eratostenovo síto. Program se dotáže na hodnotu n a vypíše všechna prvočísla do čísla n včetně. Pole pro uložení hodnot 0,1 alokujte dynamicky.

Řešení:

Dev C++:	eratos.dev, eratos.cpp
CodeBlocks:	eratos.cbp, eratos.cpp

Úloha 7.5

Napište program, který počítá integrál metodou Monte Carlo s využitím knihovny GSL (ukázka z přednášky).

Knihovna GSL pro MS Windows: gsl-1.8.exe

Řešení:

Dev C++:	montecarlo.dev, montecarlo.cpp
CodeBlocks:	montecarlo.cbp, montecarlo.cpp

Úloha 7.6

Ukázkový program, který ukládá matici s využitím vektoru z knihovny STL.

Řešení:

Dev C++:	maticestl.dev, maticestl.cpp
CodeBlocks:	maticestl.cbp, maticestl.cpp