gifts2017

Алгоритм “хвост змеи для заполнения прямоугольной области”.

Опубликовал Олег Молочников (milkers) в раздел Программирование - Практика программирования

При разработке http://infostart.ru/public/275582/ столкнулся с необходимостью распределить выделенные задания на прямоугольную область календаря. В результате родился алгоритм, который может пригодиться не только мне и не только в этой задаче.

Молочников Олег Spb. 2014.

Алгоритм “хвост змеи для заполнения прямоугольной области”.

 

При разработке http://infostart.ru/public/275582/ столкнулся с необходимостью распределить выделенные задания на прямоугольную область календаря. В результате родился алгоритм, который может пригодиться не только мне и не только в этой задаче.

Итак:  Есть прямоугольная область произвольного размера. Необходимо разделить ее на несколько областей , расположенных одна за другой по принципу движения змеи, следующим образом: 


 

Сначала создадим функцию Координаты хвоста змеи, которая,  возвратит нам смешение по горизонтальной и вертикальной оси от начала координат в верхнем левом углу, для любой произвольной прямоугольной области по номеру сегмента змеи.  (На рисунке вверху номер сегмента змеи отображен цифрами от 1 до 20).

 

Функция ПолучитьКоординатыХвостаЗмеи(ПравоОбласти,ЛевоОбласти,НизОбласти,ВерхОбласти,СегментХвоста)
    КоординатыСегментаХвостаЗмеи=Новый Структура("Лево, Верх");
    ВысотаОбласти= НизОбласти-ВерхОбласти+1;
    КоординатыСегментаХвостаЗмеи.Верх= (ВысотаОбласти+СегментХвоста-1)%ВысотаОбласти+ВерхОбласти;
    КоординатыСегментаХвостаЗмеи.Лево= Цел((СегментХвоста-1)/ВысотаОбласти)+ЛевоОбласти;
    Возврат КоординатыСегментаХвостаЗмеи;
КонецФункции



Теперь  сам  алгоритм:

//Входные данные:

Лево,Право,Верх,Низ  - координаты области к заполнению.

КоличествоВыделенныхЭтапов –Количество этапов подлежащих распределению;

    КоличествоРядовКЗаполнению=Право-Лево+1;

    КоличествоСтрокКЗаполнению=Низ-Верх+1;

    КоличествоЯчеекКЗаполнению=КоличествоРядовКЗаполнению*КоличествоСтрокКЗаполнению;
    КоличествоЯчеекНаЭтап= Цел(КоличествоЯчеекКЗаполнению/КоличествоВыделенныхЭтапов);
    Если КоличествоЯчеекНаЭтап<1 Тогда
        Отказ=Истина;
        ОбщегоНазначения.СообщитьОбОшибке("Выбранная область слишком мала для размещения выбранных этапов!",Отказ);
        Возврат;
    КонецЕсли;
    НераспределенныеЯчейкиКЗаполнению=КоличествоЯчеекКЗаполнению%КоличествоВыделенныхЭтапов;
    ИндексВыделеннойСтроки=0;
    ТекущийСегментХвоста=1;
    Пока ТекущийСегментХвоста<=КоличествоЯчеекКЗаполнению Цикл
        Если НераспределенныеЯчейкиКЗаполнению >0 Тогда
            Шаг=КоличествоЯчеекНаЭтап+1;
            НераспределенныеЯчейкиКЗаполнению=НераспределенныеЯчейкиКЗаполнению-1;
        Иначе
            Шаг=КоличествоЯчеекНаЭтап;
        КонецЕсли;
        НомерПоследнегоСегмента=ТекущийСегментХвоста+Шаг-1;
        КординатыНачалаТекущегоЭтапа=ПолучитьКоординатыХвостаЗмеи(Право,Лево,Низ,Верх,ТекущийСегментХвоста);
        КординатыКонцаТекущегоЭтапа=ПолучитьКоординатыХвостаЗмеи(Право,Лево,Низ,Верх,НомерПоследнегоСегмента);
        ЧислоРядов=КординатыКонцаТекущегоЭтапа.Лево-КординатыНачалаТекущегоЭтапа.Лево+1;
        Для I=0 по ЧислоРядов-1 Цикл
            Если I=0  Тогда
                ЛевоРяда=КординатыНачалаТекущегоЭтапа.Лево;
                ВерхРяда=КординатыНачалаТекущегоЭтапа.Верх;
            Иначе
                ЛевоРяда=КординатыНачалаТекущегоЭтапа.Лево+I;
                ВерхРяда=Верх;
            КонецЕсли;
            Если I=ЧислоРядов-1 Тогда
                ПравоРяда=КординатыКонцаТекущегоЭтапа.Лево;
                НизРяда=КординатыКонцаТекущегоЭтапа.Верх;
            Иначе
                ПравоРяда=КординатыНачалаТекущегоЭтапа.Лево+I;
                НизРяда=Низ;
            КонецЕсли;
       // текст кода занимающий в таблице сам этап            

//ЗанятьИнтервалСервер(ПравоРяда,   ЛевоРяда,   НизРяда, ВерхРяда,НомерЭтапа);
        КонецЦикла;
        ТекущийСегментХвоста=НомерПоследнегоСегмента+1;
        ИндексВыделеннойСтроки =ИндексВыделеннойСтроки+1;
    КонецЦикла;

 

Пример работы алгоритма на распределении пяти этапов по произвольному интервалу времени:


PS: Надеюсь вам понравится эта и другие мои разработки на http://infostart.ru/profile/48714/.

Очень жду ваших комментариев  и пожеланий.

Молочников Олег Spb. 2014.

 

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Александр Капустин (kapustinag) 21.06.14 18:07
(0), Не совсем уловил необходимость "хвоста змеи" в данном случае.
Имеется матрица M x N элементов, то есть всего M*N элементов. Их нужно занять этими заданиями, причем сначала (с элемента (1,1)) - первое задание, затем второе и т.д.
Два вложенных цикла - по строкам и столбцам матрицы.
Порядковый номер элемента, начиная от элемента (1,1), перед началом цикла присваивается 1, и увеличивается на 1 внутри вложенного цикла.
Пока этот порядковый номер меньше или равен длине сейчас размещаемого задания - заполняем данный элемент матрицы номером задания.
Когда очередное задание размещено, обнуляем переменную n, и переходим к следующему заданию.

На выходе получаем матрицу, элементы которой заполнены слева направо и сверху вниз сначала числом 1, затем 2, ...
Всё.
...
Или я что-то невнимательно прочитал?
2. Олег Молочников (milkers) 22.06.14 11:52
(1) kapustinag, Теоритически да, я в начала так и пробовал, но код получался очень некрасивым и сложным. Задача решается гораздо легче, если перевести ее из двумерного в одномерное пространство, что и делает мой алгоритм.
3. Андрей Акулов (DrAku1a) 23.06.14 09:49
При распределении на лист A4 для проверки влезет ли новая область на страничку - используется "ПроверитьВывод()". Я таким образом разделил вручную по листам - т.е. вывел отчет вниз, далее в полученном отчете выбрал области по листу и вывел их на новом документе методом Вывести -> Присоединить -> Присоединить -> Присоединить... Получил в итоге Ваше заполнение.

Один момент: нужно или следить за высотой строк в выводимом отчете или чтобы высота строк была одинаковой.
4. Олег Молочников (milkers) 23.06.14 10:36
(3) DrAku1a, в частном случае можно воспользоваться и Вашим способом, но для таблиц, двумерных массивов и пр. ваш способ точно не применим, плюс скорость в моем случае выше по определению, из за особенностей работы метода ПроверитьВывод(). Да и к тому же я выложил алгоритм, по принципу "не пропадать же добру". Вдруг кому-нибудь пригодиться. Да и красивое решение получилось :)
5. Sergey Boltach (ser6702) 25.06.14 10:36
Любую N-мерную матрицу можно привести к одномерной. ИМХО
этим еще занимался в период когда формировал и моделировал радиолокационное изображение в статистических алгоритмах и в DOS памяти было мало и делали сами свап файл в которые построчно сбрасывали данные комплексных радиосигналов с разных направлений и с разных дальностей. Когда известен размер матрицы это удобно. Принцип у автора тот же - матрица развернута в строку. Сама реализация на быстродействие не влияет - только особенности языка и способности программиста. Имеет право на существование как готовое решение известной проблемы - потому +
6. Сергей (ildarovich) 30.06.14 12:11
На мой взгляд, для такой простой задачи кода слишком много. И его избыточность не служит понятности, а, наоборот, запутывает.

И вообще никакого "алгоритма" (в смысле определенной последовательности действий) здесь не нужно. Отношение ячейки к этапу определяется ПРОСТОЙ функциональной зависимостью. Достаточно было бы в теле уже приведенной функции рассчитать "Сегмент хвоста" по номеру этапа, количеству ячеек на этап и номеру ячейки внутри этапа. Тогда заполнить ячейки можно было бы простым и понятным циклом по этапам (и вложенным циклам по ячейкам внутри этапа), а также можно было бы начинать заполнение не всегда с верхнего угла, при необходимости "транспонировать" заполнение - то есть идти не по колонкам, а по строчкам, заменив функцию отображения, перезаполнять ячейки выбранных этапов (перекрашивать при выделении) без перезаполнения всей области и так далее.

В общем, я бы не рекомендовал такой подход к решению этой задачи.
7. Олег Молочников (milkers) 30.06.14 12:50
(6) ildarovich, То же вариант решения. По скорости одинаково. У меня тоже внешний цикл выполнится столько раз, сколько этапов разбития. А внутренний нужен только для деления этапа на столбцы. И переносить управляющую логику в функцию или оставить при вызове функции - разницы никакой.
8. Сергей (ildarovich) 30.06.14 14:03
(7) milkers, методически разница очень большая. О скорости здесь речь не идет. Речь идет о способе декомпозиции задачи и вообще о том, что можно называть алгоритмом. По сути, Вы предлагаете "ползать по лабиринту" вместо того, чтобы посмотреть на него сверху, увидеть закономерность и применить ее. Весь так называемый "алгоритм" - это перенос единицы в старший разряд (переход к началу следующей колонки), которому дети учатся, когда начинают уметь считать больше двадцати. Это все равно что умножение заменять последовательным сложением. Но это мое личное мнение в плане того, что можно рекомендовать к использованию, а что нельзя. Это не образцовый подход, а как раз то, чего следует избегать, ИМХО.
Как, например, здесь выделить цветом один из этапов. - Заново сначала проползти по лабиринту?
9. Олег Молочников (milkers) 30.06.14 14:52
(8) Должен признать, что с этой точки зрения определенный смысл в Вашем видении есть. Ну, в любом случае переделка несложная, может быть и наша дискуссия кому-нибудь поможет. Спасибо за дельный совет.
ildarovich; +1 Ответить
10. Александр Полтава (Патриот) 30.06.14 18:17
(0) Мне кажется слишком сложно, что легче заново написать самому, чем разобраться. Например даже такая мелочь -
(ВысотаОбласти+СегментХвоста-1)%ВысотаОбласти
//эквивалентно 
СегментХвоста%ВысотаОбласти-1
11. Олег Молочников (milkers) 01.07.14 10:13
(10) Патриот, Вынужден огорчить, но выражения не эквивалентны. Вот целочисленная проверка:
i=1 j=1 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=1 j=2 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=1 j=3 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=1 j=4 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=1 j=5 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=1 j=6 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=1 j=7 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=1 j=8 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=1 j=9 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=1 j=10 (i+j-1)%i=0 j%i-1=-1!!!!!!!!!!
i=2 j=1 (i+j-1)%i=0 j%i-1=0
i=2 j=2 (i+j-1)%i=1 j%i-1=-1!!!!!!!!!!
i=2 j=3 (i+j-1)%i=0 j%i-1=0
i=2 j=4 (i+j-1)%i=1 j%i-1=-1!!!!!!!!!!
i=2 j=5 (i+j-1)%i=0 j%i-1=0
i=2 j=6 (i+j-1)%i=1 j%i-1=-1!!!!!!!!!!
i=2 j=7 (i+j-1)%i=0 j%i-1=0
i=2 j=8 (i+j-1)%i=1 j%i-1=-1!!!!!!!!!!
i=2 j=9 (i+j-1)%i=0 j%i-1=0
i=2 j=10 (i+j-1)%i=1 j%i-1=-1!!!!!!!!!!
i=3 j=1 (i+j-1)%i=0 j%i-1=0
i=3 j=2 (i+j-1)%i=1 j%i-1=1
i=3 j=3 (i+j-1)%i=2 j%i-1=-1!!!!!!!!!!
i=3 j=4 (i+j-1)%i=0 j%i-1=0
i=3 j=5 (i+j-1)%i=1 j%i-1=1
i=3 j=6 (i+j-1)%i=2 j%i-1=-1!!!!!!!!!!
i=3 j=7 (i+j-1)%i=0 j%i-1=0
i=3 j=8 (i+j-1)%i=1 j%i-1=1
i=3 j=9 (i+j-1)%i=2 j%i-1=-1!!!!!!!!!!
i=3 j=10 (i+j-1)%i=0 j%i-1=0
i=4 j=1 (i+j-1)%i=0 j%i-1=0
i=4 j=2 (i+j-1)%i=1 j%i-1=1
i=4 j=3 (i+j-1)%i=2 j%i-1=2
i=4 j=4 (i+j-1)%i=3 j%i-1=-1!!!!!!!!!!
i=4 j=5 (i+j-1)%i=0 j%i-1=0
i=4 j=6 (i+j-1)%i=1 j%i-1=1
i=4 j=7 (i+j-1)%i=2 j%i-1=2
i=4 j=8 (i+j-1)%i=3 j%i-1=-1!!!!!!!!!!
i=4 j=9 (i+j-1)%i=0 j%i-1=0
i=4 j=10 (i+j-1)%i=1 j%i-1=1
i=5 j=1 (i+j-1)%i=0 j%i-1=0
i=5 j=2 (i+j-1)%i=1 j%i-1=1
i=5 j=3 (i+j-1)%i=2 j%i-1=2
i=5 j=4 (i+j-1)%i=3 j%i-1=3
i=5 j=5 (i+j-1)%i=4 j%i-1=-1!!!!!!!!!!
i=5 j=6 (i+j-1)%i=0 j%i-1=0
i=5 j=7 (i+j-1)%i=1 j%i-1=1
i=5 j=8 (i+j-1)%i=2 j%i-1=2
i=5 j=9 (i+j-1)%i=3 j%i-1=3
i=5 j=10 (i+j-1)%i=4 j%i-1=-1!!!!!!!!!!
i=6 j=1 (i+j-1)%i=0 j%i-1=0
i=6 j=2 (i+j-1)%i=1 j%i-1=1
i=6 j=3 (i+j-1)%i=2 j%i-1=2
i=6 j=4 (i+j-1)%i=3 j%i-1=3
i=6 j=5 (i+j-1)%i=4 j%i-1=4
i=6 j=6 (i+j-1)%i=5 j%i-1=-1!!!!!!!!!!
i=6 j=7 (i+j-1)%i=0 j%i-1=0
i=6 j=8 (i+j-1)%i=1 j%i-1=1
i=6 j=9 (i+j-1)%i=2 j%i-1=2
i=6 j=10 (i+j-1)%i=3 j%i-1=3
i=7 j=1 (i+j-1)%i=0 j%i-1=0
i=7 j=2 (i+j-1)%i=1 j%i-1=1
i=7 j=3 (i+j-1)%i=2 j%i-1=2
i=7 j=4 (i+j-1)%i=3 j%i-1=3
i=7 j=5 (i+j-1)%i=4 j%i-1=4
i=7 j=6 (i+j-1)%i=5 j%i-1=5
i=7 j=7 (i+j-1)%i=6 j%i-1=-1!!!!!!!!!!
i=7 j=8 (i+j-1)%i=0 j%i-1=0
i=7 j=9 (i+j-1)%i=1 j%i-1=1
i=7 j=10 (i+j-1)%i=2 j%i-1=2
i=8 j=1 (i+j-1)%i=0 j%i-1=0
i=8 j=2 (i+j-1)%i=1 j%i-1=1
i=8 j=3 (i+j-1)%i=2 j%i-1=2
i=8 j=4 (i+j-1)%i=3 j%i-1=3
i=8 j=5 (i+j-1)%i=4 j%i-1=4
i=8 j=6 (i+j-1)%i=5 j%i-1=5
i=8 j=7 (i+j-1)%i=6 j%i-1=6
i=8 j=8 (i+j-1)%i=7 j%i-1=-1!!!!!!!!!!
i=8 j=9 (i+j-1)%i=0 j%i-1=0
i=8 j=10 (i+j-1)%i=1 j%i-1=1
i=9 j=1 (i+j-1)%i=0 j%i-1=0
i=9 j=2 (i+j-1)%i=1 j%i-1=1
i=9 j=3 (i+j-1)%i=2 j%i-1=2
i=9 j=4 (i+j-1)%i=3 j%i-1=3
i=9 j=5 (i+j-1)%i=4 j%i-1=4
i=9 j=6 (i+j-1)%i=5 j%i-1=5
i=9 j=7 (i+j-1)%i=6 j%i-1=6
i=9 j=8 (i+j-1)%i=7 j%i-1=7
i=9 j=9 (i+j-1)%i=8 j%i-1=-1!!!!!!!!!!
i=9 j=10 (i+j-1)%i=0 j%i-1=0
i=10 j=1 (i+j-1)%i=0 j%i-1=0
i=10 j=2 (i+j-1)%i=1 j%i-1=1
i=10 j=3 (i+j-1)%i=2 j%i-1=2
i=10 j=4 (i+j-1)%i=3 j%i-1=3
i=10 j=5 (i+j-1)%i=4 j%i-1=4
i=10 j=6 (i+j-1)%i=5 j%i-1=5
i=10 j=7 (i+j-1)%i=6 j%i-1=6
i=10 j=8 (i+j-1)%i=7 j%i-1=7
i=10 j=9 (i+j-1)%i=8 j%i-1=8
i=10 j=10 (i+j-1)%i=9 j%i-1=-1!!!!!!!!!!
12. Марина Чирина (chmv) 01.07.14 10:49
13. Олег Молочников (milkers) 01.07.14 10:54
(12) "Ой как сложно" - о чем это ты?
14. Олег Молочников (milkers) 01.07.14 11:45
(8)
Это не образцовый подход, а как раз то, чего следует избегать, ИМХО.
Как, например, здесь выделить цветом один из этапов. - Заново сначала проползти по лабиринту?

При условии равномерного распределения все что вы сказали истинно. Но как быть если в дальнейшем планируется распределять учитывая предполагаемую длительность этапов, определенную для них на этапе планирования, плюс возможны интервалы связанные с необходимость завершить этапы на другом оборудовании. Как тогда обойтись без "ползанья по лабиринту"?
15. Александр Полтава (Патриот) 25.07.14 22:33
(11) milkers, вынужден огорчиться, действительно лоханулся :)
доводы более чем убедительны
но может хоть так заработает?
(ВысотаОбласти+СегментХвоста-1)%ВысотаОбласти
//эквивалентно 
(СегментХвоста-1)%ВысотаОбласти
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа