Интересная (возможно) задача.

← →
GEN++ © (2009-06-04 14:09) [0]

Есть:
1. исходный диапазон D целых чисел 0,1,2 .... 999 999
2. массив отрезков M в виде: [начало отрезка], [конец отрезка]
(реально не превысит 1000 позиций) принадлежащих D
3. Процедура myProc(Xb:longword; len:word)
Xb - начало отрезка len длина отрезка (оба из D и len>0)
работающая по след-м правилам:
если входной отрезок Xb...Xb+len-1 примыкает (например 7...9 и 10..100
или 7...9 и 2..6) или перекрывает или находится внутри или пересекается с любым из отрезков из массива M то такой отрезок
в массиве M изменяется (объединяется с входным):
============= Например ==============================
Вх отр Отр в M до Отр в M после вызова процедуры
7..9 10..100 7..100 //примыкание слева
7..9 2..6 2.. 9 //примыкание справа
2..7 6..15 2..15 //пересечение слева
6..15 12..19 6..19 //пересечение справа
1..100 12..19 1..100 //поглощение
14..15 12..19 12..19 //нахождение внутри
7..9 12..19 12..19 //нет объединения
================================================
Если входной отрезок не объединился ни с одним из имеющихся в M
отрезков, то он добавляется к M
Изначально M - пуст

Задача: текст процедуры, которая после N-го вызова в M
сформирует набор не объединяющихся отрезков, упорядоченных
"по возрастанию" начал отрезков.

← →
oldman © (2009-06-04 14:19) [1]

Курсовик пишешь?

← →
oldman © (2009-06-04 14:24) [2]

Банальный цикл перебора.
Можно даже рекурсию привинтить.

← →
oldman © (2009-06-04 14:26) [3]

> ============= Например ==============================
> Вх отр Отр в M до Отр в M после вызова процедуры
> 7..9 10..100 7..100 //примыкание слева
> 7..9 2..6 2.. 9 //примыкание справа
> 2..7 6..15 2..15 //пересечение слева
> 6..15 12..19 6..19 //пересечение справа
> 1..100 12..19 1..100 //поглощение
> 14..15 12..19 12..19 //нахождение внутри
> 7..9 12..19 12..19 //нет объединения
> ================================================

Переведи, как это сочетается с

14..15 12..19 12..19 //нахождение внутри

← →
GEN++ © (2009-06-04 14:26) [4]

>oldman
Бывает, пишу если только в помощь сыну
Но в данном случае это не курсовик, а часть реальной
программы (не комерческой). Естественно программа написана, но мне
кажется мое решение достаточно "коряво", возможно будет
предложено оригинальное решение.

← →
oldman © (2009-06-04 14:29) [5]

> Вх отр Отр в M до Отр в M после вызова процедуры
> 7..9 10..100 7..100 //примыкание слева

И вот это переведи.
Примыкание к чему? До него М был пустой.

И что такое Отр в М?

← →
GEN++ © (2009-06-04 14:33) [6]

>1..100 12..19 1..100 //поглощение
проверяемый отрезок 12..19 лежит внутри входного отрезка 1..100
>14..15 12..19 12..19 //нахождение внутри
проверяемый отрезок 12..19 полностью перекрывает/накрывает
входной отрезок 14..15 следовательно входной "исчезает" а
проверяемый не изменяется.

← →
GEN++ © (2009-06-04 14:39) [7]

Вх отр - отрезок на входе в процедуру задается Xb и len
Отр в M до - i-й отрезок в массиве M до вызова процедуры

> 7..9 10..100 7..100 //примыкание слева
входной отрезок 7..9 "касается" отрезка из M
т.е. если их физически приложить друг к другу получется единый отрезок:
7..9,10..100==7..100

← →
oldman © (2009-06-04 14:43) [8]

> Вх отр Отр в M до Отр в M после вызова процедуры
> > 7..9 10..100 7..100 //примыкание слева
> > 7..9 2..6 2.. 9 //примыкание
> справа

Входит 7-9
Внутри есть 10-100
Примыкаются, получается 7-100
А следующий проверяется с 2-6, который почему-то не объединился с 7-100
и не получился 2-100
???

← →
GEN++ © (2009-06-04 14:52) [9]

В данном примере я привел варианты одной проверки входного
отрезка с i-м элементом массива M чтобы показать алгоритм объединения

← →
oldman © (2009-06-04 14:57) [10]

Тогда точно нужна рекурсия, поскольку после объединения полученный отрезок становится входным и опять надо проверять массив М

← →
oldman © (2009-06-04 15:11) [11]

Не знаю, как делал ты, на ум приходит простое решение в лоб:

Пока не кончились ОтрВХ
Вызов ФункцияПроверки(ОтрВх, М)
Сортировка М

Функция проверки
Проверка элементов М по порядку с 1 до последнего >0
1. ОтрМ внутри ОтрВХ - ОтрМ удаляется из М, СдвигМ
2. ОтрВх внутри ОтрМ - Возврат
3. ОтрВх стыкуется с ОтрМ:
ОтрВх=ОтрВх+ОтрМ
ОтрМ удаляется из М
СдвигМ
Вызов ФункцияПроверки(ОтрВх, М)
4. ОтрВх добавляется в М
Возврат

СдвигМ - понятно для чего?

← →
MBo © (2009-06-04 15:13) [12]

Набор отрезков известен заранее, или они поступают по одному?
(смущает фраза "" процедуры, которая после N-го вызова")

← →
MBo © (2009-06-04 15:22) [13]

Рано отправку нажал...

Если весь набор известен, то делаем так:
Преобразуем отрезки в утроенные с запасом
NewStart = Start * 3 - 2
NewEnd = End * 3 + 2
Сортируем массив записей (точка, +-1 для начала и конца соответсвенно) по координатам точек
Счетчик C инициализируем нулем.
Запоминаем начало отрезка в M
Идем по массиву. Счетчик инкрементируем на величину второго поля записи.
Если он стал нулевым, записываем конец отрезка в M.
Когда переходит из нуля в 1, запоминаем начало очередного отрезка.
По окончанию работы корректируем M ((X+2) div 3 для начал, X div 3 для концов.)

← →
GEN++ © (2009-06-04 15:28) [14]

>MBo
Заранее набор отрезков неизвестен. Их кол-во ограничено, в общем
случае, разумными пределами.
Внешняя программа формирует очередной отрезок и вызывает
процедуру myProc с параметрами этого отрезка.
После N-го вызова (внешняя программа знает когда кончатся новые отрезки
а для myProc - это N-й ее вызов) для внешней программы(вызывающей)
должен быть подготовлен массив M сформированный по приведенным выше
правилам.
Фактически myProc - это некий фильтр, пройдя через который, новый отрезок либо объединяется с имеющимися в M либо добавляется в массив M

← →
MBo © (2009-06-04 15:31) [15]

Есть возможность накопить все отрезки, и посчитать так, как я написал?
Или нужно на каждом этапе иметь текущий набор?

← →
И. Павел (2009-06-04 15:59) [16]

Можно преобразовать массив отрезков в вектор точек (тип элеменов - boolean: true-по точке проходит линия, false-нет). Тогда для добавления нового отрезка устанавливаем в true все его точки. В конце выполняем обратное преобразование вектора в массив отрезков. Программа получится простая, правда, займет больше памяти, и ,если отрезки будут большими, наверное, будет работать помедленнее (хотя не нужно быдет выполнять сортировку и заботиться о пересечении отрезков).
Можно сделать тип элементов byte и в каждый из них писать по 8 точек.

>oldman

Вызов ФункцияПроверки(ОтрВх, М) Сортировка М Функция проверки Проверка элементов М по порядку с 1 до последнего >0 1. ОтрМ внутри ОтрВХ - ОтрМ удаляется из М, СдвигМ 2. ОтрВх внутри ОтрМ - Возврат 3. ОтрВх стыкуется с ОтрМ: ОтрВх=ОтрВх+ОтрМ ОтрМ удаляется из М СдвигМ Вызов ФункцияПроверки(ОтрВх, М) 4. ОтрВх добавляется в М Возврат

Где-то так я и предполагал делать, но есть здесь одно тонкое место:
в п. 3 рекурсиный вызов функцией проверки самой себя. А ну как в M
будет под 1000 элементов и на N-ном шаге начнется повальное объединение
отрезков т.е. каждый "новый" (полученный в рез-те объединения отрезок)
будет обязательно объединяться с имеющимся?????
Выдержит ли стек?
Физически это не реально, но вдруг что "сломается " в вызывающей программе?

>СдвигМ - понятно для чего?
Естественно - раз мы принимаем за новый отрезок полученный в результате
конкатенации предыдущего, то этот новыый отрезок надо удалить из массива
отсюда и сдвиги массива, иниче бесконечная рекурсия.

>MBo
>Есть возможность накопить все отрезки, ....
Принципиально есть, но очень уж тоскливо выделять под это
память. Кроме того физически ~98% отрезков являются продолжением
предыдущего. Собственно исходная задача - объединить несколько входных
Hex файлов в формате Intel Extended. Вам, я полагаю, знаком этот формат.
Для этого последовательно считываем все их данные в массив памяти.
При этом выделяем диапазоны, куда велась загрузка. Далее по этим данным
и диапазонам генерим выходной суммарный файл.

>Принципиально есть, но очень уж тоскливо выделять под это
память.

Тогда можно делать объединение периодически, скажем, по накоплении 1000 отрезков.

А для полной динамики можно использовать такую структуру данных - interval (или segment) tree. Реализуется обычно на основе сбалансированных деревьев (RB или других).

Если отрезков мало (десятки), то я бы запихал их в список, может быть отсортировал бы по начала, и решал бы в лоб, не парясь. Если много (тысячи), то создал бы двойное дерево (по началам и концам), возможно с балансировкой.

>MBo
>TUser

Ваша идея с накоплением - интересная.
Если для каждой точки диапазона D закрепить свой бит, который будет фиксировать раветством 1 факт того что эта точка совпадала с входным отрезком. Всего понадобится 1Mdyte/8 = 128Kbyte временной памяти из кучи
- Winda легко даст.
Далее, по окончанию процесса подкачки отреков, пройти по всему массиву и
сформировать массив сплошных диапазонов (отрезков) это как 2 байта
поменять местами - полная гарантия от потерь отрезков и чего-нибудь еще. !!!!!!!

Всем спасибо за обсуждение!!!

Интересная (возможно) задача. Найти похожие ветки