Dotaz: Zvlastne zoradenie sutaziacich-algoritmus

[Morelo2211]

Cawte,

mojou ulohou je zoradit sutaziacich,tak ,ze vzdy pod sutaziacim budu vsetci ti nad ktorymi vyhral a ty ktory medzi sebou nasutazili,tak nezalezi na ich vzajomnom poradi. Moj problem je,ale ked mam vstup: 1 2 1 5 5 2 To znamena,ze 1 vyhral na 2, 1 vyhral nad 5 ... Chcel som to tak riesit,ze budem davat sutaziacich do pola a budem si pamatat aj kde som ich ulozil. Teda budem ich na zaciatok alebo na koniec,ale problem nastane,ked mam vlozit to cislo medzi 2 cisla,teda musim ostatne poposuvat a tym bude casova narocnost dost vysoka. Nevie mi niekto dat hint ako to efektivne riesit?

Dik za pomoc

---

---

Odpovědi

[rastos]

Od toho sú dynamické dátové štruktúry. Napr. zoznam.

[fraxinus]

linked list in c

[Morelo2211]

Topologicke trideni.

[Michal Kubeček]

mojou ulohou je zoradit sutaziacich,tak ,ze vzdy pod sutaziacim budu vsetci ti nad ktorymi vyhral a ty ktory medzi sebou nasutazili,tak nezalezi na ich vzajomnom poradi.

Obecně nesplnitelné zadání. Jak chcete např. řešit "1 2 2 3 3 1"?

[Morelo2211]

Ale shak to tvoje sa da riesit. Riesenie je poradie:1,2,3,4

[Michal Kubeček]

A to, že 3 porazil 1 a měl by tudíž být nad ním, budete ignorovat?

[Jamp]

Ehm http://www.ksp.sk/ksp2.0/wiki/Zadania/27-4z priklad 4? :D

[Michal Kubeček]

Tak to už je vrchol… :-(

[AraxoN]

Časová náročnosť posuvu v poli pri počte hráčov do 10 je IMHO nižšia, než réžia spojkových zoznamov, či iných pokročilých štruktúr.