Подготовка рекурсии
Еще перед началом рекурсии все точки P сортируются по координате х , а потом по координате у; так получаются списки Px и Py. С каждым элементом списка связана запись с информацией о позиции точки в обоих списках.
Первый уровень рекурсии работает так, как описано ниже; другие уровни работают полностью аналогично. О определяется как множество точек в первых >/2' позициях списка Px («левая половина»), а R — как множество точек в других \чП\ позициях списка Pх («правая половина»); схема разбиения представлена на рис. 5.6. За один проход по Px и Py за время O(n) можно создать четыре списка: Qx с точками Q, отсортированными по возрастанию координаты х; Qy с точками Q, отсортированными по возрастанию координаты y; и два аналогичных списка Rx и Ry. Для каждого элемента каждого из этих списков также хранится его позиция в обоих исходных списках.
Затем рекурсивно определяется ближайшая пара точек в О (с обращениями к спискам Ox и (2v). Предположим, (/„ и ⅞, (правильно) возвращены как ближай- шая пара точек в Q. Аналогичным образом определяется ближайшая пара точек в R, обозначим их f;, и fj.
Еще по теме Подготовка рекурсии:
- ПОДГОТОВКА ПРОФЕССИОНАЛЬНАЯ
- Подготовка переговорщиков.
- Проблемы подготовки журналистов.
- Профессионально-психологическая подготовка (ППП).
- Психологическая подготовка к задержанию.
- 15.7.2. Подготовка возбуждением
- 6.4. Профессионально-психологическая подготовка юриста
- 6.3. Морально-психологическая подготовка юриста
- Часть 1 ПОДГОТОВКА К ВОССТАНОВЛЕНИЮ ДУШИ
- Психологическая подготовка сотрудников к управленческой деятельности
- Сущность, цели, задачи подготовки.
- Глава IV Психологическая подготовка к юридической деятельности