Алгоритм поиска интервалов
, в которые попадает число.
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [216.73.216.207] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
| Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Алгоритм поиска интервалов
, в которые попадает число.
|
Сообщ.
#16
,
|
|
  |
Pavlovsky, не пройдёт, почти уверен.
попробуй для интервалов 1-5, 6-9, 11-66, 67-74, 75-99, 111-333, 334-660, 660-675, 676-751, 752-999 построить такое дерево. Получается, что какие-то интервалы надо делить. PS при таком подходе не выгоднее ли строить префиксное дерево? |
|
Сообщ.
#17
,
|
|
 |
Мда придется делить. 11-66 поделить на 11-50,5-6,60-66. Это разве страшно?
|
|
Сообщ.
#18
,
|
|
|
|
Делить не страшно, страшно, что после деление дерево может несказанно разрастись.
Добавлено И кстати делить надо будет не так. Пусть 1-5, 6-9, 11-66, 67-74. Из них придется сделать 1-5, 6-6, 7-7, 8-9, 11-59, 60-66, 67-69, 70-74. Добавлено И кстати, если действительно иметь структуру из не пересекающихся отрезков, такую, что вложенные отрезки вложены полностью и между собой тоже не пересекаются, то быстрее дерево префиксов. |
|
Сообщ.
#19
,
|
|
|
|
Если делить не страшно...
Пример 1-5, 6-9, 11-66, 67-74, 75-99, 111-333, 334-660, 660-675, 676-751, 752-999 После деления получим (в скобках исходный интервал): 1-10999(1-5) 11-11099(11-66) 111-333(111-333) 3330-33399(11-66) 334-660(334-660) 660-675(660-675) 6750-67599(67-74) 676-751(676-751) 7510-75199(75-99) 752-999(752-999) интервал 6-9 целиком закрывается более длинными. Кстати, в конкретном примере, количество интервалов не увеличилось! Далее бинарное дерево или дерево префиксов, как кому нравится. |
1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0,0170 ] [ 14 queries used ] [ Generated: 18.07.25, 01:39 GMT ]