Cvičenia: 6. týždeň
Ciele cvičení:
- rozumieť princípom generovania postupností technikou backtracking
- vedieť aplikovať backtracking na riešenie kombinatoricko-optimalizačných problémov
Variácie (dla zwariowanych)
Navrhnite a upravte program na generovanie váriácií s opakovaním tak, aby ste generovali variácie s opakovaním z prvkov ľubovoľnej zadanej množiny?
Rýchlo sa rozdeliť a každý svojou cestou...
Dvaja zlodeji spoločne získali lup pozostávajúci z n predmetov. Každý z predmetov má svoju cenu. Po akcii chcú isť každý svojou cestou. Vytvorte program, ktorý nájde čo najspravodlivejšie rozdelenie predmetov medzi zlodejov, t.j. chceme minimalizovať rozdiel medzi cenou lupu prvého zlodeja a druhého zlodeja.
- Navrhnite ako tento problém riešiť pre
kzlodejov.
Nepriateľské čísla
Na telesnú chodia rôzne čísla (v jednej triede nie sú 2 rovnaké čísla). Medzi niektorými číslami sú priateľstvá, naopak niektoré čísla sa doslova nenávidia. Čísla sa nemajú rady, ak je jedno z čísel deliteľom toho druhého. Napríklad čísla 8 a 4 sa nenávidia, lebo 4 je deliteľom 8. Aby rozcvička na telesnej prebehla bez konfliktov, učiteľ musí nájsť také usporiadanie čísel v triede do radu, aby medzi žiadnymi 2 číslami stojacimi vedľa seba nepanovala nenávisť.
Pre zadanú množinu n rôznych čísel nájdite všetky bezkonfliktné usporiadania čísel do radu. Snažte sa, aby vaše riešenie bolo čo najefektívnejšie.
Problém dám na šachovnici (pre dámy aj pánov)
Nájdite také rozmiestnenie n dám na šachovnici n x n, aby sa navzájom neohrozovali.
- V prípade potreby sa môžete obmedziť na
n = 8.
Chemický sklad
Úloha z Palmy: http://palma.strom.sk/PAZ1bS3/U2l/
- u E[xtra] skupiny sa očakáva úspešné odoslanie úlohy cez systém Palma
Variácie (dla zdolnych)
- Vytvorte program na generovanie variácií s
h-opakovaním prvkov zo zadanej množiny.h-opakovanie znamená, že každý prvok sa môže vo vygenerovanej postupnosti nachádzať nanajvýšhkrát. - Navrhnite, ako nerekurzívne generovať všetky
k-prvkové variácie s opakovaním z prvkovn-prvkovej množiny.