Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2009.08.02;
Скачать: CL | DM;

Вниз

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

 
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 точек.


 
GEN++ ©   (2009-06-04 16:00) [17]

>oldman

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

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


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

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


 
GEN++ ©   (2009-06-04 16:08) [18]

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


 
MBo ©   (2009-06-04 16:19) [19]

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

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

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


 
TUser ©   (2009-06-04 17:07) [20]

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


 
GEN++ ©   (2009-06-04 17:53) [21]

>MBo
>TUser

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

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



Страницы: 1 вся ветка

Текущий архив: 2009.08.02;
Скачать: CL | DM;

Наверх




Память: 0.53 MB
Время: 0.011 c
2-1244439390
Gans
2009-06-08 09:36
2009.08.02
TMemo добавление строк


15-1243497903
VirEx (work)
2009-05-28 12:05
2009.08.02
День программиста


15-1243936738
boriskb
2009-06-02 13:58
2009.08.02
С юбилеем!


15-1243590539
pasha_golub
2009-05-29 13:48
2009.08.02
Изменение published свойств компонентов


15-1243926982
xayam
2009-06-02 11:16
2009.08.02
Вопрос по php-ext