Pătrările latine au o istorie lungă datând din vremea lui L. Euler. Ele apar în problemele teoriei grupurilor și semigrupurilor, codificarea, planificarea, alocarea resurselor, ordinea inițierii evenimentelor, emiterea de sarcini studenților etc. [55, pp. 261-282]. În prezent, pătratele latine sunt din nou obiectul cercetării active în legătură cu problemele nerezolvate ale geometriei finite.
Definiția. Un pătrat latin de ordinul n este o matrice pătrată m de dimensiune n 'n. ale căror elemente aparțin setului M = n> și fiecare număr din M are loc exact o dată pe fiecare rând și în fiecare coloană m.
Din definiția latrului latin rezultă că rândurile lui m constau în diferite permutări ale numerelor de la 1 la n. Coloanele lui m constau, de asemenea, din diferite permutări ale acestor numere.
De exemplu, ducând la pătratele latine, să luăm în considerare sarcina simplificată de planificare. Fie cinci profesori Pi (i = 1, 2, 5) în cinci lecții consecutive au clase în cinci clase Kj (j = 1, 2.5). În același timp, fiecare dintre profesori este obligat să dea o lecție în fiecare clasă. În această situație, se pare că există 1344 de programe diferite. Mai jos este unul dintre ele:
Elementele lui m sunt interpretate aici, după cum urmează. Profesorul Pi (i = 1, 2, 5) conduce clase în clasa Kj (j = 1, 2.5) în numărul de lecție mi, j.
Mai jos, pe baza algoritmului de recurență cu recurență, se vor construi funcții recursive de numărare a numărului total și de generare a unui set de pătrate latine cu dimensiunea n 'n. În acest caz, ca material de construcție pentru producerea lor, se va folosi secvența P a tuturor permutărilor din elementele reprezentate în ordinea lexicografică.
Reamintim că ordinea lexicografică pe P este introdusă după cum urmează. lăsa
și pentru semnul comparației lexicografice a permutărilor, simbolul <’ (меньше). Тогда считают, что:
În figura 4, toate permutările pentru n = 4 sunt scrise în ordine lexicografică pe coloane. În general, ele pot fi formate folosind o funcție specială recursivă (vezi secțiunea "Permutări"). În forma lexicografică a înregistrării, secvența de permutare P este reprezentată ca blocuri separate de (n - 1)! elemente în fiecare. Dacă renumerotați aceste blocuri de la 0 la (n - 1), atunci toate permutările blocului j (j = 0, 1, ..., n - 1) vor începe cu o cifră (j +1). În viitor, acest fapt va fi folosit în organizarea recursivității.
Putem presupune că elementele liniei zero a oricărui lat lat L format sunt cifre succesive de la 1 la n. Conform acestor convenții, coloana j pentru L este pur și simplu una dintre permutările blocului jth (j = 0, 1, ..., n-1). Prin urmare, un astfel de mecanism pentru formarea sau numărarea numărului tuturor pătratelor latine de dimensiune n 'n este posibil.
Fig. 4. Diagrama formării pătrunderii latine din permutații
Construim următoarea matrice de candidați L. formând fiecare coloană jth de la o anumită permutare a blocului jth P (j = 0,1, ..., n-1). Dacă L este pătrat latin, amintiți-l sau extrageți-l.Dacă nu sunt sortate toate matricile candidat, atunci revenim la pasul 1, altfel organizăm rezultatul rezultatului (dacă este necesar) și calculele sunt terminate.
O asemenea căutare aprofundată a tuturor candidaților este foarte laborioasă. Cu toate acestea, schema propusă poate fi utilizată pe deplin pentru a organiza un bust cu întoarcere, îndepărtând imediat mai mulți candidați înainte de a fi construiți complet. Acest lucru se face mai jos.
5. Numărul de pătrate latine. Scrieți o funcție de program recursiv care, pentru un număr întreg n, numără în mod recursiv numărul de pătrate latine de mărime n 'n cu prima linie a formularului: 1. 2, ..., n.
Soluția. Fie P o secvență de permutări în ordinea lexicografică din elementele n> cu blocuri alocate n (vezi mai sus). Funcțiile Lanum (n) și Latinu (n, fa, mpos, ot, j) rezolvă problema.
Funcția capului Lanum (n) pentru data n pregătește argumentele reale pentru funcția recursivă Latinu ():
n este dimensiunea pătratului și numărul de blocuri în P;
j este nivelul apelului recursiv și numărul blocului din secvența de permutare P.
Să analizăm mai detaliat algoritmul implementat de funcția Latinu (), și dinamica umplerii matricei mpos cu zero și una. În figura 4, din motive metodologice, în mpos, în loc de unități reale, sunt înlocuite următoarele simboluri: #, , $ și%. Acest lucru face posibilă observarea vizuală a corespondenței permutărilor fixe în fiecare dintre blocurile P și umplerea unităților mpos.
În primul rând, observăm că recursivitatea este organizat de numărul j al blocului curent P. din care este selectat coloana următoare pentru L. pătrat latin nou creată Să presupunem că sunt în apelul recursiv-j-lea, adică, pentru L a ales permutare de 0,1, ..., (j - 1) - blocurile P și o coloană t este fixată din blocul j - lea P. Să considerăm separat posibilele cazuri care se exclud reciproc:
A. Pozițiile (s Ps, t - 1) (s = 0, 1.n - 1) ale matricei mpos sunt setate la zero (suma elementelor corespondente este zero):
B. Cel puțin una din pozițiile (s, Ps, t - 1) (s = 1, 2 n - 1) ale matricei mpos este setată la una.
Fie ca afirmația A să fie adevărată, atunci următoarele acțiuni sunt adevărate. Pozițiile (s Ps, t - 1) (s = 1, 2. n -1) ale matricei mpos sunt resetate la una:
iar coloana j este conectată la pătratul format. Mai mult, dacă j Afirmația B este adevărată, după care se fac astfel de acțiuni. In j curent th mută bloc P la coloana următoare ca următorul candidat pentru a fi incluse în L. din nou a realizat una dintre alternativele A sau B. Dacă j> 0 și j-lea bloc P este epuizată, atunci o întoarcere este realizată din recursivă curentă suna. După aceea, elementele mpos. setați în apelul recursiv (j-1) la unul, sunt resetate la zero. Dacă j = 0 și blocul jth este epuizat, funcția Latinu () returnează valoarea calculată ot. Notă. Problema ar putea fi rezolvată mai eficient. De exemplu, așa. Lăsați funcția Latinu () să formeze numai pătrate latine cu coloană zero și coloană zero a formulei 1, 2, ..., n. Dacă numărul lor se dovedește a fi egal cu m. atunci soluția problemei este evident numărul m × (n - 1) !. Pentru implementarea acestui sistem, este suficient să se fixeze la zero inițial bloc permutare P și nu se modifică în timpul calculului său, ceea ce corespunde cu recurență nu este zero, iar primul bloc P. Acest lucru se poate realiza ca urmare a unei funcții Lanum modificare minoră (): Exemple de control. Tabelul arată numărul de pătrate latine pentru valorile lui n de la două la șase. Calculul se bazează pe funcția Lanumq (n). 6. Pătraturile latine. Scrie o funcție recursivă care pentru un număr dat natural n generează și ieșiri pătrate latine ale lui n „n rândul zero și tipul coloanei zero, 1, 2, ..., n. Soluția. În condițiile specificate în condițiile sarcinii, coloana jth a oricărui lat lat L format trebuie selectată din blocul jth al matricei de permutare P (j = 0,1, ... n-1). În acest caz, coloana nulă L trebuie să coincidă întotdeauna cu coloana zero a blocului zero. Pentru a economisi memoria, răspunsul va fi format ca o matrice ot. fiecare coloană k (k = 0,1, ...) care codifică un anumit lat lat L printr-o astfel de schemă. Valoarea elementului oti, k (i = 0, 1.n -1) este numărul celei de-a treia coloane L din matricea P (vezi figura 5). Soluția problemei poate fi funcția latină () și Lainitq (). Calculele pe ele se efectuează aproape la fel ca pentru câteva funcții considerate anterior Latinu () și Lanumq (). Principalele diferențe sunt următoarele. Funcția latină () are, în comparație cu Latinu (), un vector parametru formal suplimentar nou. Este folosit pentru stocarea de cod explodată format următor latină L pătrat într-un număr de coloane succesive P. Fiecare vector nouă matrice nou format este conectat la răspunsurile corecte ot (in Latinu () ot a fost variabilă simplă). Recursie în latină () este organizată, ca în Latinu () funcția, linia j a curentului matricei bloc permutare P. Exemple de control. Mai jos se calculează valoarea funcției Lainitq (4) și pătratele latine corespunzătoare coloanelor sale sunt date în partea dreaptă a matricei rezultate. Fig. 5. Corespondența dintre coloanele matricei de răspuns și pătratele latine Notă. Pentru ca funcția latină () să calculeze toate pătratele latine de dimensiune n 'n pentru un anumit număr natural n cu o linie zero a formulei: 1, 2, .... n și fără restricții la coloana zero, este suficient să modificați ușor programul principal Lainitq (). Noua sa editie poate fi aceasta:
Articole similare
Trimiteți-le prietenilor: