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

20.06.14

Разработка - Математика и алгоритмы

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

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

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

 

При разработке //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: Надеюсь вам понравится эта и другие мои разработки на //infostart.ru/profile/48714/.

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

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

 

алгоритм хвост змеи

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1715    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4319    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7350    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7820    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4415    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8795    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7720    dusha0020    8    

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

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

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

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

В общем, я бы не рекомендовал такой подход к решению этой задачи.
7. milkers 2859 30.06.14 12:50 Сейчас в теме
(6) ildarovich, То же вариант решения. По скорости одинаково. У меня тоже внешний цикл выполнится столько раз, сколько этапов разбития. А внутренний нужен только для деления этапа на столбцы. И переносить управляющую логику в функцию или оставить при вызове функции - разницы никакой.
8. ildarovich 7846 30.06.14 14:03 Сейчас в теме
(7) методически разница очень большая. О скорости здесь речь не идет. Речь идет о способе декомпозиции задачи и вообще о том, что можно называть алгоритмом. По сути, Вы предлагаете "ползать по лабиринту" вместо того, чтобы посмотреть на него сверху, увидеть закономерность и применить ее. Весь так называемый "алгоритм" - это перенос единицы в старший разряд (переход к началу следующей колонки), которому дети учатся, когда начинают уметь считать больше двадцати. Это все равно что умножение заменять последовательным сложением. Но это мое личное мнение в плане того, что можно рекомендовать к использованию, а что нельзя. Это не образцовый подход, а как раз то, чего следует избегать, ИМХО.
Как, например, здесь выделить цветом один из этапов. - Заново сначала проползти по лабиринту?
9. milkers 2859 30.06.14 14:52 Сейчас в теме
(8) Должен признать, что с этой точки зрения определенный смысл в Вашем видении есть. Ну, в любом случае переделка несложная, может быть и наша дискуссия кому-нибудь поможет. Спасибо за дельный совет.
ildarovich; +1 Ответить
14. milkers 2859 01.07.14 11:45 Сейчас в теме
(8)
Это не образцовый подход, а как раз то, чего следует избегать, ИМХО.
Как, например, здесь выделить цветом один из этапов. - Заново сначала проползти по лабиринту?

При условии равномерного распределения все что вы сказали истинно. Но как быть если в дальнейшем планируется распределять учитывая предполагаемую длительность этапов, определенную для них на этапе планирования, плюс возможны интервалы связанные с необходимость завершить этапы на другом оборудовании. Как тогда обойтись без "ползанья по лабиринту"?
10. Патриот 449 30.06.14 18:17 Сейчас в теме
(0) Мне кажется слишком сложно, что легче заново написать самому, чем разобраться. Например даже такая мелочь -
(ВысотаОбласти+СегментХвоста-1)%ВысотаОбласти
//эквивалентно 
СегментХвоста%ВысотаОбласти-1
11. milkers 2859 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!!!!!!!!!!
15. Патриот 449 25.07.14 22:33 Сейчас в теме
(11) вынужден огорчиться, действительно лоханулся :)
доводы более чем убедительны
но может хоть так заработает?
(ВысотаОбласти+СегментХвоста-1)%ВысотаОбласти
//эквивалентно 
(СегментХвоста-1)%ВысотаОбласти
12. chmv 01.07.14 10:49 Сейчас в теме
13. milkers 2859 01.07.14 10:54 Сейчас в теме
(12) "Ой как сложно" - о чем это ты?
Оставьте свое сообщение