Дана система N труб (задается вручную), заданных началом и концом.
Например, система из двух труб. (-1(начало),5(конец)); (2;7). Необходимо определить отрезок, на котором пересекается наибольшее количество труб. (в конкретном примере - (2;5)).
Если трубы не пересекаются, выдать об этом сообщение.
PS вообще если не сложно, посоветуйте правильную литературу по началу работы с VBA, источников разных много, но как то они..плохо систематизированы чтоли, информация идет вразнобой.
Нужна помощь с алгоритмизацией задачи в VBA
Дана система N труб (задается вручную), заданных началом и концом.
Например, система из двух труб. (-1(начало),5(конец)); (2;7). Необходимо определить отрезок, на котором пересекается наибольшее количество труб. (в конкретном примере - (2;5)).
Если трубы не пересекаются, выдать об этом сообщение.
PS вообще если не сложно, посоветуйте правильную литературу по началу работы с VBA, источников разных много, но как то они..плохо систематизированы чтоли, информация идет вразнобой.iNAIVi
Примерно так: - Пройдемся по списку отрезков и построим на его основе список для анализа. Этот новый список будет включать все точки концов отрезков, с назначением им признака +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)
Алгоритм могу дать, код - не дам
Примерно так: - Пройдемся по списку отрезков и построим на его основе список для анализа. Этот новый список будет включать все точки концов отрезков, с назначением им признака +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
Skype: andre.tm.007 Donate: Qiwi: 9517375010
Сообщение отредактировал AndreTM - Пятница, 09.06.2017, 09:46
Хоть миллиард отрезков. Алгоритм линейный по времени выполнения, за исключением процедуры сортировки Которая тоже может быть максимум N*lnN зависимой).
Хоть миллиард отрезков. Алгоритм линейный по времени выполнения, за исключением процедуры сортировки Которая тоже может быть максимум N*lnN зависимой).AndreTM
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
Да, сортировку нужно производить так, чтобы "конечные" точки при совпадающих координатах были впереди "начальных".
После этого если какие-то точки совпадают - то алгоритм от этого не изменится. Как ты в примере и привел, если это будут совпадения "конец предыдущего - начало следующего", то алгоритм просто и посчитает именно сначала -1, а потом только +1.
Единственный нюанс - если совпадут начальные точки нескольких отрезков как раз там, где начинается "максимальное пересечение" - то мы ошибемся с поиском конечной точки пересечения. Но это все равно повлияет на проверку уже в конце, после цикла. И достаточно модифицировать алгоритм с "брать позМакс+1" на "брать следующую за позМакс, у которой признак = -1".
Да, действительно, отрезки отсутствуют или не пересекаются вообще, если значМакс<=1. Вообще, значМакс - это как раз "сколько всего пересекается отрезков там, где пересекается максимальное количество отрезков". Раз у нас задача такая, что надо найти пересечения хотя бы двух (и более) отрезков - то значМакс должен там быть не менее 2.
Поправил алгоритм в сообщении.
Да, сортировку нужно производить так, чтобы "конечные" точки при совпадающих координатах были впереди "начальных".
После этого если какие-то точки совпадают - то алгоритм от этого не изменится. Как ты в примере и привел, если это будут совпадения "конец предыдущего - начало следующего", то алгоритм просто и посчитает именно сначала -1, а потом только +1.
Единственный нюанс - если совпадут начальные точки нескольких отрезков как раз там, где начинается "максимальное пересечение" - то мы ошибемся с поиском конечной точки пересечения. Но это все равно повлияет на проверку уже в конце, после цикла. И достаточно модифицировать алгоритм с "брать позМакс+1" на "брать следующую за позМакс, у которой признак = -1".
Да, действительно, отрезки отсутствуют или не пересекаются вообще, если значМакс<=1. Вообще, значМакс - это как раз "сколько всего пересекается отрезков там, где пересекается максимальное количество отрезков". Раз у нас задача такая, что надо найти пересечения хотя бы двух (и более) отрезков - то значМакс должен там быть не менее 2.
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
