Új hozzászólás Aktív témák

• Gyuri16 senior tag

  #2238

  #2237 Carpigabi

  2010-12-30 14:01:50

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  Gyuri16

  senior tag

  #2237 Carpigabi

  #2237 Carpigabi

  Egy iskolai feladathoz kellene:

  Katonai egyenruhakat kellene gyártani, h a haboruban levo orszagok egymast megtudjak különböztetni.

  A bemeneti adat:

  1.orszag - 2. ország .... ahol 1.orszag szomszédja és ellensége a 2. orszagnak.

  eredményben tehát kikell szamitani a minimalis mennyisegű (színű) egyenruhát, amire szükség van ...

  Példák:

  Britain - Ireland
  Szükséges egyenruhák száma: 2

  Britain - Ireland
  France - Germany
  Szükséges egyenruhák száma: 2

  Britain - Ireland
  France - Germany
  France - Swiss
  Swiss - Germany
  Szükséges egyenruhák száma: 3

  iskolai feladatot itt helyetted senki nem fogja megcsinalni, viszont segitunk ha elakadsz, es konkret kerdesed van.

  a feladathoz:
  szetosztod a grafot osszefuggo komponensekre
  mindegyiknek kiszamolod a kromatikus szamat es a legnagyobb lesz a megoldas.

  kromatikus szam egy osszefuggo grafhoz:
  binaris keresessel. egy lepesben kibprobalod eleg e m szin (m legyen mondjuk n/2 az elejen, mivel tudjuk, hogy a kromatikus szam maximum n). ezt bruteforce csinalod.
  innen a siker fuggvenyeben mindig kizarod a fel intervallumot, es megtalalod a legkisebb erteket amire meg atmegy a szinezes

Új hozzászólás Aktív témák