Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Система с трубами, определить отрезок с пересечением - Мир MS Excel

Регистрация · Логин: · Пароль: · · Забыли пароль?
Страница 1 из 11
Модератор форума: _Boroda_, Pelena, Manyasha, SLAVICK 
Мир MS Excel » Вопросы и решения » Вопросы по VBA » Система с трубами, определить отрезок с пересечением (Макросы/Sub)
Система с трубами, определить отрезок с пересечением
iNAIVi Дата: Четверг, 08.06.2017, 21:42 | Сообщение № 1
Группа: Пользователи
Ранг: Прохожий
Сообщений: 6
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
Нужна помощь с алгоритмизацией задачи в VBA

Дана система N труб (задается вручную), заданных началом и концом.

Например, система из двух труб. (-1(начало),5(конец)); (2;7). Необходимо определить отрезок, на котором пересекается наибольшее количество труб. (в конкретном примере - (2;5)).

Если трубы не пересекаются, выдать об этом сообщение.

PS вообще если не сложно, посоветуйте правильную литературу по началу работы с VBA, источников разных много, но как то они..плохо систематизированы чтоли, информация идет вразнобой.
 
Ответить
СообщениеНужна помощь с алгоритмизацией задачи в VBA

Дана система N труб (задается вручную), заданных началом и концом.

Например, система из двух труб. (-1(начало),5(конец)); (2;7). Необходимо определить отрезок, на котором пересекается наибольшее количество труб. (в конкретном примере - (2;5)).

Если трубы не пересекаются, выдать об этом сообщение.

PS вообще если не сложно, посоветуйте правильную литературу по началу работы с VBA, источников разных много, но как то они..плохо систематизированы чтоли, информация идет вразнобой.

Автор - iNAIVi
Дата добавления - 08.06.2017 в 21:42
AndreTM Дата: Четверг, 08.06.2017, 22:05 | Сообщение № 2
Группа: Друзья
Ранг: Старожил
Сообщений: 1762
Репутация: 496 ±
Замечаний: 0% ±

2003 & 2010
Алгоритм могу дать, код - не дам :)

Примерно так:
- Пройдемся по списку отрезков и построим на его основе список для анализа. Этот новый список будет включать все точки концов отрезков, с назначением им признака +1 для "начальная точка отрезка" и -1 для "конечная точка отрезка. Получим (из примера):
(-1,1; 5,-1; 2,1; 7,-1)
- Отсортируем список точек по возрастанию (если есть совпадающие точки - то первыми должны оказаться точки с признаком -1):
(-1,1; 2,1; 5,-1; 7,-1)
- Если теперь суммировать нарастающим итогом признак (+1 или -1), то максимальное значение счетчика и будет означать начало нужного нам отрезка-ответа (в отдельных переменных запоминаем и максимум, и позицию максимума в списке):
значМакс = 0; позМакс = 0; Счетчик = 0
i=1; Счетчик = 0+1=1; Счетчик>значМакс -> значМакс=Счетчик=1; позМакс=i=1
i=2; Счетчик = 1+1=2; Счетчик>значМакс -> значМакс=Счетчик=2; позМакс=i=2
i=3; Счетчик = 2-1=1; Счетчик>значМакс -> нет
i=4; Счетчик = 1-1=0; Счетчик>значМакс -> нет

- Если значМакс <= 1 - то отрезки не пересекаются
- Иначе получаем решение: точка в позМакс = (2).
Соответственно, следующая "конечная" точка, следующая за максимумом - конец этого отрезка. Точка, следующая за позМакс, и имеющая "признак -1" = (5)


Skype: andre.tm.007
Donate: Qiwi: 9517375010


Сообщение отредактировал AndreTM - Пятница, 09.06.2017, 09:46
 
Ответить
СообщениеАлгоритм могу дать, код - не дам :)

Примерно так:
- Пройдемся по списку отрезков и построим на его основе список для анализа. Этот новый список будет включать все точки концов отрезков, с назначением им признака +1 для "начальная точка отрезка" и -1 для "конечная точка отрезка. Получим (из примера):
(-1,1; 5,-1; 2,1; 7,-1)
- Отсортируем список точек по возрастанию (если есть совпадающие точки - то первыми должны оказаться точки с признаком -1):
(-1,1; 2,1; 5,-1; 7,-1)
- Если теперь суммировать нарастающим итогом признак (+1 или -1), то максимальное значение счетчика и будет означать начало нужного нам отрезка-ответа (в отдельных переменных запоминаем и максимум, и позицию максимума в списке):
значМакс = 0; позМакс = 0; Счетчик = 0
i=1; Счетчик = 0+1=1; Счетчик>значМакс -> значМакс=Счетчик=1; позМакс=i=1
i=2; Счетчик = 1+1=2; Счетчик>значМакс -> значМакс=Счетчик=2; позМакс=i=2
i=3; Счетчик = 2-1=1; Счетчик>значМакс -> нет
i=4; Счетчик = 1-1=0; Счетчик>значМакс -> нет

- Если значМакс <= 1 - то отрезки не пересекаются
- Иначе получаем решение: точка в позМакс = (2).
Соответственно, следующая "конечная" точка, следующая за максимумом - конец этого отрезка. Точка, следующая за позМакс, и имеющая "признак -1" = (5)

Автор - AndreTM
Дата добавления - 08.06.2017 в 22:05
iNAIVi Дата: Пятница, 09.06.2017, 06:01 | Сообщение № 3
Группа: Пользователи
Ранг: Прохожий
Сообщений: 6
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
AndreTM, Спасибо =) а если отрезков N, это не повлияет критично на алгоритм? отрезки же получается могут быть в разных местах.
 
Ответить
СообщениеAndreTM, Спасибо =) а если отрезков N, это не повлияет критично на алгоритм? отрезки же получается могут быть в разных местах.

Автор - iNAIVi
Дата добавления - 09.06.2017 в 06:01
AndreTM Дата: Пятница, 09.06.2017, 06:34 | Сообщение № 4
Группа: Друзья
Ранг: Старожил
Сообщений: 1762
Репутация: 496 ±
Замечаний: 0% ±

2003 & 2010
Хоть миллиард отрезков. Алгоритм линейный по времени выполнения, за исключением процедуры сортировки Которая тоже может быть максимум N*lnN зависимой).


Skype: andre.tm.007
Donate: Qiwi: 9517375010
 
Ответить
СообщениеХоть миллиард отрезков. Алгоритм линейный по времени выполнения, за исключением процедуры сортировки Которая тоже может быть максимум N*lnN зависимой).

Автор - AndreTM
Дата добавления - 09.06.2017 в 06:34
iNAIVi Дата: Пятница, 09.06.2017, 08:23 | Сообщение № 5
Группа: Пользователи
Ранг: Прохожий
Сообщений: 6
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
AndreTM, подумал ещё.. поправь меня если я не прав.
1. начальная сортировка списка должна идти вначале по первой точке, но если они совпадают, по отрицательному значению для счетчика. ну как пример отрезки 0,2 и 2,4. если взять первым 2,1 то счетчик дойдет до 2. а пересечений нет. надо вначале брать 2,-1 потом 2,1.
2. отрезки не пересекаются, если значмакс=1. так? потому в любом случае при наличии хоть 1 отрезка, значмакс=1. если =0 то отрезков вообще нет.
 
Ответить
СообщениеAndreTM, подумал ещё.. поправь меня если я не прав.
1. начальная сортировка списка должна идти вначале по первой точке, но если они совпадают, по отрицательному значению для счетчика. ну как пример отрезки 0,2 и 2,4. если взять первым 2,1 то счетчик дойдет до 2. а пересечений нет. надо вначале брать 2,-1 потом 2,1.
2. отрезки не пересекаются, если значмакс=1. так? потому в любом случае при наличии хоть 1 отрезка, значмакс=1. если =0 то отрезков вообще нет.

Автор - iNAIVi
Дата добавления - 09.06.2017 в 08:23
AndreTM Дата: Пятница, 09.06.2017, 09:30 | Сообщение № 6
Группа: Друзья
Ранг: Старожил
Сообщений: 1762
Репутация: 496 ±
Замечаний: 0% ±

2003 & 2010
Да, сортировку нужно производить так, чтобы "конечные" точки при совпадающих координатах были впереди "начальных".

После этого если какие-то точки совпадают - то алгоритм от этого не изменится. Как ты в примере и привел, если это будут совпадения "конец предыдущего - начало следующего", то алгоритм просто и посчитает именно сначала -1, а потом только +1.

Единственный нюанс - если совпадут начальные точки нескольких отрезков как раз там, где начинается "максимальное пересечение" - то мы ошибемся с поиском конечной точки пересечения. Но это все равно повлияет на проверку уже в конце, после цикла. И достаточно модифицировать алгоритм с "брать позМакс+1" на "брать следующую за позМакс, у которой признак = -1".

Да, действительно, отрезки отсутствуют или не пересекаются вообще, если значМакс<=1. Вообще, значМакс - это как раз "сколько всего пересекается отрезков там, где пересекается максимальное количество отрезков". Раз у нас задача такая, что надо найти пересечения хотя бы двух (и более) отрезков - то значМакс должен там быть не менее 2.

Поправил алгоритм в сообщении.


Skype: andre.tm.007
Donate: Qiwi: 9517375010


Сообщение отредактировал AndreTM - Пятница, 09.06.2017, 09:48
 
Ответить
СообщениеДа, сортировку нужно производить так, чтобы "конечные" точки при совпадающих координатах были впереди "начальных".

После этого если какие-то точки совпадают - то алгоритм от этого не изменится. Как ты в примере и привел, если это будут совпадения "конец предыдущего - начало следующего", то алгоритм просто и посчитает именно сначала -1, а потом только +1.

Единственный нюанс - если совпадут начальные точки нескольких отрезков как раз там, где начинается "максимальное пересечение" - то мы ошибемся с поиском конечной точки пересечения. Но это все равно повлияет на проверку уже в конце, после цикла. И достаточно модифицировать алгоритм с "брать позМакс+1" на "брать следующую за позМакс, у которой признак = -1".

Да, действительно, отрезки отсутствуют или не пересекаются вообще, если значМакс<=1. Вообще, значМакс - это как раз "сколько всего пересекается отрезков там, где пересекается максимальное количество отрезков". Раз у нас задача такая, что надо найти пересечения хотя бы двух (и более) отрезков - то значМакс должен там быть не менее 2.

Поправил алгоритм в сообщении.

Автор - AndreTM
Дата добавления - 09.06.2017 в 09:30
Мир MS Excel » Вопросы и решения » Вопросы по VBA » Система с трубами, определить отрезок с пересечением (Макросы/Sub)
Страница 1 из 11
Поиск:

Яндекс цитирования
© 2010-2017 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!