Další várka algoritmů

Programování2. duben 2006, 21:19

Už je to nějaký čas, co jsem si napsal poslední příspěvek. Tak jsem si řekl, že by bylo záhodno trochu překvapit čtenáře nějakám článečkem. A hle - je tu!

Sekci o algoritmech jsem rozšířil o dva prográmky, které jsem napsal pro předmět Problémy a algoritmy. První řeší notoricky známou úlohu přelévání kýblů s vodou. Například: máte dva kýble jeden pěti a druhý tří litrový, kohoutek s vodou a odtokový žlábek. Kýble jsou na začátku prázdné a pomocí pouze tří operací - přelití vody z jednoho kýblu do druhého, vylití vody do žlábku a naplnění kýble po okraj - máte do jednoho kýble dostat čtyři litry vody a druhý mít prázdný. Úlohu lze řešit i obecně pro více kýblů. Kromě toho je k prográmku dodávána (ZDARMA!) implementace klasické a prioritní fronty v Javě.

Druhý prográmek zase řeší problém batohu: máte množinu věcí ohodnocených cenou a váhou a batoh s určitou maximální nosností a máte ho naplnit věcmi tak, abyste maximalizovali zisk. Implementoval jsem řešení hrubou silou, metodou větvení a mezí, heuristikou poměru cena/váha a dynamickým programováním.

Při práci na programu na diagnostikování parkinsoniků (a dalších lidí postižených třesem) jsem naimplementoval různé prohlížeče dat a jelikož potřebuji naimplementovat Savitzky-Golay filtr, narazil jsem na stránky Numerical Recipes in C, kde se skrývá celá kniha o implementaci matematických vzorců a postupů. Velice přínosné... Kromě toho jsem provedl (a jako recidivista stále provádím) testy na datech pacientů a vypadá to, že první řešení se již blíží...

A na závěr bych se opět pochlubil dvěma komerčními výtvory, které najdete tradičně v sekci tomu věnované - internetové stránky restaurace a kavárny Café Therapy a hru pro mobilní telefony Boulder Drift.

[1] Martin [web], 15. říjen 2008, 1:06

i hate java! :-)