Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 30. 12. 2010 16:47
Výpočet chromatického čísla + vstupy řetězců
Dobrý den, potřeboval bych pomoct s úkolem. Má to být naprogramované v C. Potřeboval bych pomoct hlavně se začátkem vstup a ošetření vstupů. Jinak ten výpočet kolik potřebujeme barev už bych snad něják zvládl. Předem dík ;)
Zadání:
Code:
Vaším úkolem je vytvořit program, který umožní optimalizovat výrobu vojenských uniforem. Program podle zadání map určí, kolik různých vzorů uniforem je potřeba vyrábět. Vstupem programu je seznam sousedních států. Na jedné řádce vstupu jsou vždy uvedeny dva státy, které mají společnou hranici. Zadávání sousedních států je ukončeno koncem vstupu (EOF - Ctrl-D resp. Ctrl-Z). Výstupem programu je vypočtený minimální počet uniforem, které je pro takto zadanou mapu států potřeba vyrábět (při zachování podmínky odlišných uniforem sousedících států). Realizovaný program musí ošetřovat nesprávné zadání. Pokud je vstup neplatný, program vypíše chybové hlášení (viz níže) a ukončí se. Testování správnosti vstupu musí probíhat průběžně, v případě nesprávného vstupu musí program reagovat okamžitě. Za chybný vstup je považováno: na řádce nebyla zadaná jména dvou států oddělená pomlčkou (jméno státu je tvořeno tvořeno ASCII znaky s výjimkou bílých znaků a pomlčky, délka jména je omezena na 64 znaků), zadaná dvojice sousedících států se opakuje (stejná dvojice byla již zadaná dříve), bylo zadáno, že stát hraničí sám se sebou. Program je testován v omezeném prostředí, kde je limitovaná velikost dostupné paměti a doba běhu. Limity jsou zvolené tak, aby naivní řešení hrubou silo uspělo ve všech testech s výjimkou testu bonusového (viz nápověda níže). Ukázka práce programu: Zadejte sousedni uzemi: Britain - Ireland Pocet ruznych uniforem: 2 Zadejte sousedni uzemi: Britain - Ireland France - Germany Pocet ruznych uniforem: 2 Zadejte sousedni uzemi: Britain - Ireland France - Germany France - Swiss Swiss - Germany Pocet ruznych uniforem: 3 Zadejte sousedni uzemi: Portugal - Spain Spain - France France - Germany Germany - Czech Czech - Slovakia Slovakia - Poland Pocet ruznych uniforem: 2 Zadejte sousedni uzemi: France - Germany Germany - Swiss France - Swiss France - Italy Swiss - Italy Germany - Italy France - Monaco Swiss - Monaco Germany - Monaco Italy - Monaco Pocet ruznych uniforem: 5 Zadejte sousedni uzemi: France - Germany Germany - Swiss France - Swiss France - Italy Swiss - Italy Germany - Italy France - Monaco Swiss - Monaco Germany - Monaco Pocet ruznych uniforem: 4 Zadejte sousedni uzemi: Germany - Nespravny vstup. Zadejte sousedni uzemi: - Monaco Nespravny vstup. Zadejte sousedni uzemi: France - France Nespravny vstup.
Offline
#2 30. 12. 2010 17:04 — Editoval TomDlask (30. 12. 2010 17:12)
Re: Výpočet chromatického čísla + vstupy řetězců
Pro řešení se hodí znát problém čtyř barev.
Jestliže umíš načítat data (oddělená mezerou) ze vstupu, tak na každém řádku ověřuješ: (s1 je první část stringu, s2 druhá, s3 třetí)
s1 není s3
s2 je pomlčka
+ opakování států - řešil bych polem, do kterého bych si ukládal kdo s kým už sousedí
V C bohužel neumím programovat, takže nemohu poskytnout konkrétní kód.
Jsem omylný, proto ne vše, co jsem napsal, je zaručeně správně.
468
Offline
#3 30. 12. 2010 21:26
Re: Výpočet chromatického čísla + vstupy řetězců
Ahoj, ten problém čtyř barev říká, že každý rovninný graf (tedy mapa států) lze obarvit maximálně čtyřmi barvami, avšak nemáš zaručeno, že ti bude zadána reálná, tudíž rovinná mapa (graf). To ale na řešení nic nezmění.
Algoritmus na výpočet chromatického čísla grafu:
Nejprve si označím všechny vrcholy hodnotou 0 (= zatím neobarvené vrcholy) a vytvořím si proměnnou pocet_barev která bude mít na začátku hodnotu 1 (počet dosud použitých barev). Na začátku vyberu libovolný vrchol a přiřadím mu hodnotu 1 (barva 1; proto má proměnná pocet_barev na začátku hodnotu 1).
Poté v libovolném pořadí projdu všechny dosud neobarvené vrcholy grafu. U každého vrcholu ze sousedů se podívám, jaké nejmenší přirozené číslo nejmají sousední vrcholy tohoto vrcholu (např. pokud mají sousedi 0;0;1;2;4, pak je hledaným číslem 3; pro případ 0;0;0 je hledaným číslem 1). Tímto číslem ohodnotím aktuální vrchol a podívám se, jestli je náhodou toto číslo větší než hodnota proměnné pocet_barev (pokud je větší, tak jsem nyní přidal dosud nepoužitou barvu do grafu a tudíš musím zvětšit hodnotu proměnné pocet_barev o jedničku).
Procházení souvislého (u nesouvislého musím tento postup použít pro všechny neho komponenty = souvislé částy (tedy např. ostrovní státy)) grafu mohu realizovat pomocí fronty - nejprve do ní vložím první vrchol; pokaždé, když ke zpracovávání vyberu z fronty aktuální vrchol, pak do ní vložím všechny neho sousední vrcholy, které mají hodnotu 0 (pokud by se nějaký vrchol ocitl ve frontě vícekát, tak by to nevadilo, protože by se vždy spočítalo stejné číslo).
Offline
#4 30. 12. 2010 21:52
Re: Výpočet chromatického čísla + vstupy řetězců
Nezkoušel jsem to programovat, ale postup by měl být správný.
K tomu, že to nemusí být rovinná mapa: toho jsem si nevšiml, že ty vstupy nemusí odpovídat realitě, ale tvůj postup problému 4 barev nevyužívá, takže to je jedno.
Jsem omylný, proto ne vše, co jsem napsal, je zaručeně správně.
468
Offline
#5 31. 12. 2010 00:03
Re: Výpočet chromatického čísla + vstupy řetězců
↑ vojta01:
Ahoj, tohle bohužel nefunguje.
Na levém obrázku je obarvení, které dostaneme tvým algoritmem když postupně obarvujeme vrcholy s čísly 1, 2, 2, 3, 4, na pravém je obarvení třemi barvami.
Offline
#7 31. 12. 2010 20:11 — Editoval TomDlask (31. 12. 2010 20:11)
Re: Výpočet chromatického čísla + vstupy řetězců
Co to zkusit podle vlastností grafu?
Pokud je spojen každý vrchol s každým, tak bude tím číslem počet vrcholů. Pokud jde o izolované vrcholy (ostrovní státy), tak to bude 1.
Zkoušel jsem hledat a našel jsem třeba toto, také toto, přirozeně wikipedie a spusta dalších. Doufám, že někde najdeš, co jsi potřeboval.
Jsem omylný, proto ne vše, co jsem napsal, je zaručeně správně.
468
Offline