Fórum: Valaki mondja meg!

Az tényleg csoda. Az optimális ugyanis 4 csoport. A felső háromszögmátrix részét használtam a táblázatnak (a program a szimmetrikus részét elkészíti); Glpk-ban van is egy gráfszínezős program az examples mappában ami megoldja ezt a problémát egészértékű programozással, csak annyit tettem hozzá, hogy a színezést is kiíratom: http://pastebin.com/USiCAV5x. A megoldás pedig: http://pastebin.com/XC8g8uAC, először a tárgy (sor)száma, majd a szín száma 1-4-ig. (itt a heurisztikus gyors megoldás is rátalált az opt. megoldásra).

Kicsivel egyszerűbb programmal is meg lehet ezt oldani: rögzítem a színek számát és így keresek egy színezést, ha nincs akkor növelem eggyel a színek számát (ez annyiban kedvezőbb is lehet futásidőben, hogy kevesebb változót használunk). Amúgy nem meglepő ez a fajta megoldás, órarendkészítést tipikusan egészértékű programozással oldunk meg.

Remek, de azért elárulod a helyes gráfot, hogy mi is próbálkozhassunk?

Sikerült 3 csoportba gyűjteni, ami szinte egy csoda!

Ennek a táblázatnak nem kéne szimmetrikusnak lennie? A MAGY E, MAGY K az egyik irányban meg van jelölve, de a másik irányban nincs. Meg tudnád adni a helyes gráfot, és lehetőleg nem csak képként?

Vagyis a megfelelő 19 pontos gráfnak egy jó színezését szeretnéd megtalálni minél kevesebb színnel?

Segítségeteket kérem egy valós problémához, ami azt is mutatja, hogy az órarend összeállítása a mai középiskolákban a lehetetlennel határos. A faktos csoportok láthatók a táblázatban. Az X-ek azt jelentik, hogy van olyan tanuló, aki az oszlop és sor faktot (tantárgyat) együtt választotta. Cél: Minél kevesebb olyan csoportot kell kialakítani a tantárgyakból, amelyek mehetnek egy időben, tehát nincs olyan tanuló, aki egyszerre választotta őket és egyszerre két helyen kéne lennie. Minden ötletet szívesen veszek. Előre is köszönöm!

Üdvözletem - szóval még is csak lenne valaki ,akit érdekelne a téma - nagyon örülök ennek és folytatom az elképzelésem vagyis amit ott az openstudy.com/mathematics oldalon leírtam . - elképzelésem szerint az első alapprím a kettes,az egyedüli páros,majd egy szám különbségre követi a hármas,az első páratlan prím -(itt jegyezném meg,hogy ők,mint egy szám különbségű prímek,lehetnének ,,társ-prímek" - 2 - 3

- az első kör 2 szorozva 3 = 6 +/- 1 = 5 - 7 és így bővül első körben négyre a prímnemzetség

- 5 - 7

- 5 + 7 = 12 +/- 1 = 11 - 13 ikerprímek

- 11 - 13

- 11 + 13 = 24×3=72 +/- 1 = 71 -73 ikerprímek

- 71 - 73

- 71+73=144×3=432 +/- 1 = 431 - 433 ikerprímek

- 431 -433

- 431+433=864×3=2592 +/- 1 = 2591 - 2593 ikerprímek

- és ez lenne az eddigi leghosszabb ikerprím-családfa amit logikusan a kapcsolatok leírásával érthetően értelmezni lehet

köszönöm szépen a véleményeket

Varázsló barátja, Hű De Morgána azt ajánlotta a törpének, hogy a dobozokat úgy helyezze el, hogy csak egyetlen &tex;\displaystyle L&xet; limeszpontjuk legyen. Újult lelkesedéssel látott munkához; egyhelyben ülve, két kézzel rakosgatta a köveket. Nagyon élvezte, hogy amikor egy követ belerak egy dobozba, a másik kezével már veheti is ki a dobozból a másik követ. A végén újra belenézett a dobozokba, és azok --- ahogy várta --- ismét üresek voltak, viszont az összes követ ott látta az &tex;\displaystyle L&xet; pontban.

--- Én soha nem tettem egy követ sem az &tex;\displaystyle L&xet; pontba! Hogy kerültek mégis oda? --- faggatta Merlint.

--- Oda konvergáltak. Ha a köveket pontszerűnek tekintjük, azt mondhatjuk, hogy minden egyes kő egy-egy folytonos görbén mozgott, és ezeknek a görbéknek a közös limesze a 11 órás időpontban éppen az &tex;\displaystyle L&xet; pont.

A törpe ezt sem igazán értette, de nagyon örült, hogy nem vesztek el a kövei. Boldogan kiáltott:

--- MEGVANNAK A SZÍNES KÖVEIM! MEGNYERTEM A BÖLCSESSÉG KÖVÉT!

--- Na jó, téd lehet a Bölcsesség Köve -- válaszolta Merlin. --- Adj ide nekem egyet a köveid közül.

A törpe széles, diadalmas mosollyal ki akarta nyújtani a kezét, hogy kivegyen egy követ az &tex;\displaystyle L&xet; pontból, de ekkor kellemetlen meglepetés érte.

--- Öööö... hova lettek a kezeim?

--- A kezed részecskéi a klasszikus modell szerint pontszerűek, és folytonos görbéken mozognak, de ez csak egyszerűsített modell. A finomabb kvantummechanikai rendszerben a részecskék helyének valószínűségi eloszlását az állapotfüggvényük írja le. A szokásos esetekben az állapotfüggvény egy kis halmazra koncentrálódik, ezért kezelhetjük a részecskéket pontszerűnek. A te eseted viszont valamivel komplikáltabb. Tetszőleges &tex;\displaystyle \varepsilon>0&xet;-ra igaz, hogy &tex;\displaystyle 11-\varepsilon&xet; és &tex;\displaystyle 11&xet; között te az összes dobozba beledugtad mindkét kezedet. Ezért az állapotfüggvények idő szerinti limesze sokkal nagyobb térrészen, a dobozok körül szóródik szét.

--- Már megint nem értem. Muszáj mindig ilyen tudományos bikkfanyelven fogalmazni?

--- Rendben. A kezeid szétkenődtek a térben egy, a dobozok körüli felhőben.

--- Hú. Akkor vegyél el te magadnak egy színes követ az &tex;\displaystyle L&xet; pontból, és léccí, add ide nekem a Bölcsesség Kövét!

--- A kristály törékeny. Tartok tőle, hogy nem tudnád megfogni, átesne a felhőn...

"Amit én hiányolok a meséből, az az, hogy hol volt a törpe a feladat végén. :-)"

A törpe felkereste Merlin ősellenségét, Morgánát, aki azt javasolta a törpének, hogy dél előtt egy fél órával markoljon bele az első dobozba, szedje ki belőle a semmit, rakja vissza a nagy dobozba, és ezt folytassa egészen délig. Csodálkozott a törpe, de végrehajtotta. Végén az összes (egy szám sem hiányzott) köve ott lapult a nagy dobozban, amit még kevésbé értett. Morgána hisztérikus gonosz nevetéséből a "kompakkság" szót vélte kihallani, de arra nem dobott semmit a keresője, belenyugodott.

Merlin nem csak a bölcsek kövét vesztette így el, de kiderült hogy a hulladékmegsemmisítő üzemei sem pont azt csinálják amit szeretne -- ki kellett hát valamit találnia...

Segítsünk Merlinnek! Adjunk olyan algoritmust, amelyik képes a gömbön vagy a projektív síkon* is megsemmisíteni a dolgokat!

* a törpék 0 magasak

Én úgy értem a kérdést, hogy a második feladatban is a későbbi kő mozog tovább a kisebb sorszámmal, tehát megismételjük az első feladatot; a kövek nem sétálnak ki a végtelenbe, csak a sorszámok. Az &tex;\displaystyle n&xet;-edik lépésben az &tex;\displaystyle n&xet;-edik kő (&tex;\displaystyle 1&xet;-es sorszámmal) bekerül az &tex;\displaystyle n&xet;-edik dobozba, és többször már nem vesszük ki a dobozból, viszont a számát minden menetben letöröljük és &tex;\displaystyle 1&xet;-gyel nagyobbra cseréljük.

A feladat végén minden dobozban egyetlen, számozatlan kő lesz, az &tex;\displaystyle n&xet;-edik dobozban az eredetileg &tex;\displaystyle n&xet;-edik kő.

Amit én hiányolok a meséből, az az, hogy hol volt a törpe a feladat végén. :-)