latin négyzetek
Latin négyzetek egy hosszú múltra nyúlik vissza Euler. Ezek merülnek fel problémák a csoportok és félcsoportokra elmélet, a kódolás, ütemezés, erőforrás-allokáció, elsőbbségi megkezdése események kibocsátó feladatok a diákok, stb [55, c.261 - 282]. Jelenleg latin négyzetek ismét lesz a témája az aktív kutatás kapcsán a megoldatlan problémák véges geometriák.
Definíció. Latin négyzetek rend n nevezzük négyzetes mátrix mérete m n „n. amelynek az elemei tartoznak a beállított M = n>, ahol az egyes M szám jelenik pontosan egyszer minden sorban és minden oszlopban m.
A meghatározás a latin négyzet azt jelenti, hogy a sorok állnak m különböző permutációi számok 1-től n. Oszlopok m is állhat különböző permutációs ezeket a számokat.
Példaként, így a latin négyzet, úgy egyszerűsített probléma ütemezési. Hagyja, öt tanár Pi (i = 1, 2, 5) iskola öt egymást követő órák tartson ülést öt osztályba Kj (j = 1, 2, 5). Ezen kívül minden tanár köteles adni a leckét minden osztályban. Ebben a helyzetben, kiderül, vannak 1344 különböző lehetséges menetrendek. egyikük az alábbiakban:
M elemeit értelmezik itt. Tanár Pi (i = 1, 2, 5) vezető osztályban Kj (j = 1, 2, 5) az osztályban szám MI, j.
Az alábbiakban alapú rendezési algoritmus visszatér funkció beépített rekurzív felsorolása az összes és generáló összesített latin négyzet mérete n „n. Így építőanyagként azok előállítására fogják használni a szekvencia P minden permutációját bemutatott elemek lexikografikusan sorrendben.
Emlékezzünk vissza, hogy a lexikográfiai megbízás P vezetünk így. enged
és jelölje ki a lexikográfiai összehasonlítás használt permutációk szimbólum <’ (меньше). Тогда считают, что:
A 4. ábrán, az oszlopok a lexikografikus sorrendben írva az összes permutációinak n = 4. Általában akkor képezhetnek egy speciális rekurzív függvény (lásd. „Permutációk” fejezetben). A lexikográfiai jelölési szekvenciát permutációs P képviseli, mint egy külön blokk (n - 1)! elemek minden. Ha ezek a blokkok vannak számozva 0-tól (n - 1), minden permutációját a blokk j (j = 0, 1, ..., n - 1) indul egy számjegyet (j +1). A jövőben ezt a tényt fogják használni a rekurziót.
Feltételezhetjük, hogy a nulla vonal elemeit kialakítható bármilyen latin négyzet L jelentése egymást követő számok 1-től n. Ezekben a megállapodások j -edik oszlop L egyszerűen az egyik a j-edik permutációs blokk P (j = 0, 1, ..., n -1). Következésképpen, egy lehetséges mechanizmusa képződés vagy megszámoljuk a latin négyzetek N „n.
Ábra. 4. latin négyzet rendszer kialakulásának permutációk
Építünk a következő jelölt L. mátrixképző minden egyes j-edik oszlopának a j-edik permutációs blokk P (j = 0,1, ..., n - 1). Ha L egy latin négyzet, majd memorizálni vagy kinyomtathatja.Ha nem az összes felsorolt mátrix jelöltek, majd visszatér az 1. lépéshez, egyébként szervezni kimeneti cél (ha szükséges) és a számítást a megszűnik.
Az ilyen kimerítő keresés az összes lehetséges jelöltek nagyon időigényes. Azonban a javasolt rendszer jól alkalmazható a szervezet a visszalépés azonnal, mi ment sok jelölt, hogy a teljes szerkezet. Ez alatt történik.
Feladatok 5. számú latin négyzetek. Írja rekurzív program funkció, amely, amikor egy előre meghatározott n pozitív egész szám által visszalépés megszámlálja az latin négyzetek n „az első n String: 1. 2, ..., n.
Határozat. Legyen P - a permutációs sorrend az iexikografikus sorrendben az elemek a n> n c kiosztott blokkok (lásd fent.). Lanum funkció (n) és Latinu (N, fa, mpos, OT, j) A feladat megoldásához.
Szülő funkció Lanum (n) egy adott n előkészíti a tényleges érvek a rekurzív Latinu () funkció:
n - a méret a tér és a blokkok számát a P;
j - szintű rekurzív hívást, és a blokk sorszámát permutációs P.
Laknak egy algoritmus megvalósított funkciók Latinu (), és a dinamikája töltelék a mátrix mpos nullák. 4. ábra A módszertani megfontolások mpos helyett a tényleges egység medve helyett a karakterek: #, , $ És%. Ez lehetővé teszi, hogy vizuálisan a betartását ellenőrizni rögzített műszakban az egyes P blokkok és töltő mpos egység.
Először is megjegyezzük, hogy a rekurzió rendezi száma j az aktuális blokk P., ahonnan a következő oszlopban van kiválasztva az újonnan létrehozott latin négyzet L. Tegyük föl, hogy a j-ik rekurzív hívás, vagyis az L választotta permutációja 0,1, ..., (j - 1) -edik blokkok P és rögzített néhány oszlop t j -edik blokk P. külön-külön úgy esetekben az ilyen lehetséges egymást kölcsönösen kizáró:
A. pozíciók (s Ps, t - 1) (S = 0, 1 n -1) mpos mátrix nullára vannak állítva (kiszámítjuk a megfelelő elemek egyenlő nullával):
B. Legalább az egyik a pozíciók (s Ps, t -. 1) (s = 1, 2 n -1) mpos mátrix van beállítva, hogy az egyik.
Hagyja, hogy a állítását A. Ezután a következő lépéseket végezzük. Tételek (. S Ps, t - 1) (s = 1, 2 n -1) mpos mátrix visszaállítás egy egység:
és az oszlop j össze van kötve, hogy által képzett téren. Továbbá, ha j Hagyja, hogy a B. állítást követően olyan intézkedések megtételére. A jelenlegi j-edik blokk P mozog, hogy a következő oszlopban a következő jelölt felvétel L. ismét rájött egyik alternatíva A vagy B. Ha j> 0 és j-edik blokk P kimerül, akkor a visszatérő végzik a jelenlegi rekurzív hívni. Ezt követően elemek mpos. meg a (j - 1) -edik rekurzív hívás egy, visszaáll nullára. Ha j = 0 és j-edik blokk P kimerül, akkor Latinu () függvény a számított érték ot. Megjegyzés. Úgy véljük, a problémát meg lehet oldani hatékonyabban. Például ez a helyzet. Legyen Latinu () függvény csak generál latin négyzetek null karakterlánc, és a nulla oszlop típusú 1, 2, ..., n. Ha a szám egyenlő lesz a m. a probléma megoldása, nyilvánvalóan, az a szám, m × (n - 1)!. Megvalósítása ez a rendszer, elég kijavítani a nulla kezdeti permutáció blokk P és alatt nem változik a számítás, ami megfelel a rekurzió nem nulla, és az első blokk P. Ezt el lehet érni a következő kisebb módosításával Lanum function (): Teszt esetek. A táblázat azt mutatja, a számos latin négyzetek a, n értéke kettő és hat közötti. A számítás végeztük Lanumq funkció (n). Adachi 6. latin négyzetek. Írása rekurzív függvény, amely egy adott természetes szám n generál, és kiadja latin négyzetek n „n nulla sor és nulla oszlop típusú 1, 2, ..., n. Határozat. Ilyen körülmények között, a probléma megállapodások j-edik oszlop által képzett bármely latin négyzet L kell választani a j-edik blokk P permutációs mátrix (J = 0,1, ... n - 1). Ebben a nulla L oszlopban kell mindig esik egybe nulla-nulla blokk P oszlop Annak érdekében, hogy mentse memória választ képezi majd OT mátrix. minden oszlop k (k = 0,1, ...), amely kódolja specifikus latin négyzet L egy ilyen rendszerben. Oti elem értéke, k (i = 0, 1 n -1) - jelentése szám L edik oszlopban a mátrix P (lásd 5. ábra.). a probléma megoldása lehet a latin () és Lainitq (). Ezek a számítások végeznek majdnem ugyanaz, mint egy pár funkciót korábban úgy Latinu () és Lanumq (). A fő különbség a következők itt. Latin () függvény képest Latinu () van egy további formális paraméter vektor új. Ezt alkalmazzák tárolására kódot felrobbant kialakítva következő latin négyzet L egymást követő oszlopban számok P. Minden vektor újonnan képződött az új mátrix van csatlakoztatva a helyes válaszokat OT (in Latinu () OT egyszerű volt változó). Rekurzió latin () függvény szerveződik, mint a Latinu () funkció, j vonal az aktuális blokk permutációs mátrix P. Teszt esetek. Az alábbiakban számított értéket Lainitq funkció (4), és a jobb a kapott mátrix kapta a megfelelő oszlopok latin négyzetek. Ábra. 5. egyezik az oszlopok a válaszok és a latin négyzetek Megjegyzés. Latin () függvény egy adott egész n kiszámítja az összes latin négyzetek n méretű „n nulla vonal a formában: 1, 2, .... n és korlátozás nélkül a nulla oszlopon elég kis mértékben módosított fej programot Lainitq (). Az ő új szövege lehet:Kapcsolódó cikkek