Латински квадрати имат дълга история, която датира от Ойлер. Те възникват в проблемите на групи и полугрупа теория, кодиране, график, разпределението на ресурсите, приоритет за иницииране събития, издаване задачи на студенти и т.н. [55, c.261 - 282]. В момента, в Латинска площади отново стават обект на активна изследователска дейност, във връзка с нерешените проблеми крайни геометрии.
Определение. Латински квадрат на за п се наричат квадратни размер матрица m п 'п. чиито елементи принадлежат на набор т = п>, където всеки от броя на М появява само веднъж на всеки ред и всяка колона m.
Определянето на латински квадрат предполага, че редовете състоят от м различни пермутации на числата от 1 до п. Колони m също се състоят от различен пермутационен на тези номера.
Като пример, в резултат на латински квадрат, помислете опростена проблем на график. Нека пет учители Pi (I = 1, 2, 5) училище в продължение на пет последователни урока трябва да провеждат заседания в пет класа К; (к = 1, 2, 5). В допълнение, всеки от учителите се изисква да даде урок по всеки клас. В тази ситуация, се оказва, че има 1344 различни възможни графици. един от тях е дадена по-долу:
M елементи се тълкуват като тук. Учител на Pi (I = 1, 2, 5) провеждане на учебна Kj (к = 1, 2, 5) на брой в клас МВР, J.
По-долу алгоритъм, базиран сортиране ще се върне функция построен рекурсивни изброяване на общия и генериране на обобщена латински квадрат размер енд п. Така като строителен материал за тяхното получаване ще бъдат използвани от последователност Р на всички пермутации на елементи, представени в лексикографска ред.
Спомнете си, че лексикографски ред на P се въвежда така. нека
и за да отбележат използва за сравняване на лексикографски пермутации символа <’ (меньше). Тогда считают, что:
На фигура 4, колоните в реда лексикографското написани на всички пермутации за п = 4. Като цяло, те могат да образуват със специален рекурсивни функция (вж. "Пермутации" раздел). Чрез лексикографското нотация пермутация последователност Р е представена като отделен блок (п - 1)! елементи във всяка. Ако тези блокове са номерирани от 0 до (п - 1), всички пермутации на блок J (J = 0, 1, ..., п - 1) ще започнат с цифри (J 1). В бъдеще този факт ще бъде използвана в рекурсията.
Можем да предположим, че линията елементи нула, образувани от всеки вид на квадрат L е поредни номера от 1 до п. В тези споразумения й тата колона на L е просто един от J-ти пермутация блок Р (к = 0, 1, ..., N-1). Следователно възможен механизъм на образуване или преброяване на броя на латински квадрат N 'п.
Фиг. 4. вид на квадрат схема на формиране на пермутации
Ние изграждане на следващия кандидат L. матрица образуваща всяка от своя й тата колона на й-ти блок пермутация P (J = 0,1, ..., п - 1). Ако L е латински квадрат, а след това запомните или да го отпечатате.Ако не всички изброени матрични кандидати, след това се връща на стъпка 1, в противен случай организира изход мишена (ако е необходимо) и изчислението се прекратява.
Такова едно пълно претърсване на всички възможни кандидати е много време. Въпреки това, предложената схема може да се използва за организиране на връщане назад, веднага на какво се много кандидати да завърши изграждането им. Това се прави по-долу.
Задачи 5. Броят на латински квадрати. Напишете рекурсивна функция програма, която, когато предварително определен положително число N от отстъпления брои броя на латински квадрати N 'с първи п тип низ: 1. 2, ..., п.
Решение. Нека P - последователност от пермутации в лексикографска ред на елементите на п> п в разпределени блокове (виж по-горе.). Lanum функция (п) и Latinu (п, FA, mpos, OT, й) решаване на задачата.
Родител функция Lanum (н) за даден п подготвя действителните аргументи за рекурсивни Latinu () функция:
п - размерът на квадрата и броя на блокове в Р;
й - ниво рекурсивно повикване и номер блок последователност Първообразът на П.
Живеят по алгоритъм изпълнява функции Latinu () и динамиката на пълнене на нули матричните mpos и такива. Фигура 4 на методологическите съображения mpos вместо реалните единици мече подмяна на своите герои: #, , $ И%. Това дава възможност за визуално наблюдение на съответствието на записаните промени във всеки един от блоковете P и зарядни mpos единици.
На първо място, ние отбелязваме, че рекурсия се организира от редица й на текущия блок П., от който в следващата колона е избран за новосъздадената Латинска площад Л. Да предположим, че са в к-ти рекурсивни разговор, това е, за L е избрал пермутация на 0,1, ..., (й - 1) -ти блокове р и определена от някои от колона т й -ти блок P. с отделно помисли случаи на такива възможно взаимно изключващи:
А. Позиции (и Пс, т - 1.) (S = 0, 1. N -1) mpos матрица се свежда до нула (сумата на съответните елементи равни на нула):
Б. Поне една от позициите (и PS, т -. 1) (а = 1, 2. N -1) mpos матрица е установен в единица.
Нека твърдението на А. След това се извършват следните стъпки. Артикули. (S Пс, т - 1) (а = 1, 2. N -1) нулиране mpos матрица в единична:
и колона й е свързан с това, образуван от квадрата. Освен това, ако й Нека твърдение Б. След това вземете такива действия. В сегашната J-ти блок P преминава към следващата колона като следващия кандидат за включване в Л. отново реализира една от алтернативите А или Б. Ако й> 0 и к-ти блок P е изчерпан, а след връщането се извършва от текущата рекурсивния обади. Впоследствие на елементи mpos. разположен в (к - 1) ия рекурсивно повикване до един, са нулирани. Ако J = 0 и к-ти блок Р е изчерпана, тогава Latinu () връща изчислената стойност OT. Забележка. Ние считаме, че проблемът може да бъде решен по-ефективно. Например, такъв. Нека Latinu () функция генерира само латински площади с нулев низ и вида на нулевата колона 1, 2, ..., п. Ако броят им ще бъде равен на м. разтворът на проблема, очевидно, е броят на м х (п - 1!). За изпълнение на тази схема, е достатъчно да се определи нулева първоначална пермутация блок P и не се променят по време на изчисление, което съответства с рекурсията не е нула, а на първия блок П. Това може да се постигне след функция малка модификация Lanum (): тестови случаи. Таблицата показва броя на латински квадрат на стойности за п между два и шест. Изчисляването се извършва чрез функция Lanumq (п). Адачи 6. латински квадрати. Добави рекурсивна функция, която за даден естествено число п генерира и подава латински квадрат на п 'п нула ред и нула тип колона 1, 2, ..., п. Решение. При тези условия, проблем, споразумения й та колона, образуван от латински квадрат L трябва да бъде избран от J-ти блок P пермутация матрица (J = 0,1, ... п - 1). В този нула колона L винаги трябва да съвпада с нула нула блок колона P. За да се спести отговор памет ще образуват OT матрица. всяка колона К (к = 0,1, ...), която кодира конкретен латински квадрат L на такава схема. Oti елемент стойност, к (I = 0, 1. N -1) - е номер L и тата колона на матрицата Р (виж фиг.5.). решение на проблема може да е латински () и Lainitq (). Тези изчисления се извършват почти същата като двойка функции преди счита Latinu () и Lanumq (). Основните разлики са следните тук. функция латински () в сравнение с Latinu () има допълнителен формален параметър вектор ново. Той се използва за съхранение на код експлодира формира следващата латински квадрат L в последователни номера колона P. Всеки вектор новообразуваната нова матрица е свързан с правилните отговори OT (в Latinu () OT е проста променлива). Рекурсия в Латинска () функция се осъществява, като в Latinu () функция, ред й на текущия блок пермутация матрица P. тестови случаи. функция долу изчислена стойност Lainitq (4) и в дясно на получената матрица е даден неговите съответни колони латински квадрат. Фиг. 5. На срещата на колоните на отговорите и Латинска площади Забележка. За Латинска () функция за дадено число п изчислява всички латински квадрат с размер п 'п нулевата линия на формата: 1, 2, .... п и без ограничения за нула колона достатъчно леко променена програмата за главата Lainitq (). Нейната нова формулировка може да бъде:Свързани статии