Greedy technika
Feladatok:
  1. Egy egyszemélyes felvonó előtt n személy áll, akik szeretnének feljutni sorra az: e1, e2, …, en emeletekre. Írjunk programot, (Pszeudokód) mely meghatározza:
  2. Adott n tévéműsor, amelyeknek ismert a kezdési és befejezési időpontjuk: ( k1, v1 ), ( k2, v2 ), …, ( kn, vn ). Egy család, akinek egy tévéje van, úgy dönt, hogy a [K, V] időintervallumban ( ki >= K, vi <= V, minden i = 1,..., n ) tévézni fog. Írjunk programot, mely meghatározza, hogy
  3.  n város között telefonhálózatot szeretnénk kiépíteni. Egy nxn méretű, c mátrixban tároljuk, hogy mely városok között építhető ki direkt telefonvonal, valamint, hogy ezek a kapcsolatok egyenként mennyibe kerülnek. Írjunk programot, mely meghatározza, hogy mely városok között kell kiépíteni a direkt telefonvonalakat, úgy, hogy az összes város össze legyen kapcsolva és a költségek minimálisak legyenek.
  4. Adott egy úthálózat - amely n várost köt össze - egy nxn méretű d mátrixban. A d[i][j] elem az i és j városok közti direkt út hosszát tárolja. Írjunk programot, mely meghatározza az első várostól az összes többihez vezető legrövidebb utakat és ezek hosszát.
1. Felvonó
felvono( )
rendezés(e, n) //személyek rendezése emeletek szerint
sz_ido = 0
ossz_ido = 0
minden i = 1.. n-1 végezd
sz_ido = sz_ido + 2*e[i-1]
ossz_ido = osz_ido + sz_ido
vége minden
     ki: ossz_ido
vege felvono
Vissza

2. Tévéműsorok
tevemusor( )
rendezes ((k,v), n) // a musorok rendezese befejezesi ido fuggvenyben
ki: k[1], v[1]
T = v[1] // az utolsonak kivalsztott musor befejezesi idopontja
minden i = 2..n végezd
    ha k[i] >= T akkor
      ki: k[i], v[i]
      T = v[i]
    vége ha
  vége minden
vege tevemusor
Vissza