Обсуждение:Реализация запроса в дереве отрезков сверху — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
: {{tick | ticked=1}} описание перенести в шапку статьи
 
: {{tick | ticked=1}} описание перенести в шапку статьи
 
: {{tick | ticked=1}} зачем какое-то тире перед началом ссылки в разделе «Ссылки».
 
: {{tick | ticked=1}} зачем какое-то тире перед началом ссылки в разделе «Ссылки».
: {{tick}} А почему в описании алгоритма одни интервалы полуоткрытые, а другие — закрытые?
+
: {{tick | ticked=1}} отбивай пробел перед открывающейся скобкой.
: {{tick}} не надо объяснять алгоритм на примере RSQ, объясняй на примере абстрактной операции с деревом отрезков. Вот уже в примере работы — ок, пусть будет RSQ.
+
: {{tick | ticked=1}} нужен отступ перед «Например». А то эти напримеры на разном уровне с пунктами, к которым они относятся.
 +
: {{tick | ticked=1}} текст лучше писать сразу после слова «Замечание», а то как-то трешово смотрится.
 +
: {{tick | ticked=1}} А почему в описании алгоритма одни интервалы полуоткрытые, а другие — закрытые?
 +
: {{tick | ticked=1}} не надо объяснять алгоритм на примере RSQ, объясняй на примере абстрактной операции с деревом отрезков. Вот уже в примере работы — ок, пусть будет RSQ.
 
:: «возвращаем нулевое значение» — это совсем не абстрактно.
 
:: «возвращаем нулевое значение» — это совсем не абстрактно.
 +
::: «возвращаем некоторое значение, которое не повлияет на результат запроса на запрашиваемом полуинтервале.» — а теперь вспомним линал за первый семестр — как такой элемент называется? :) нейтральный. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 14:13, 15 мая 2012 (GST)
 
:: «как некоторую функцию» — почему «некоторую»?
 
:: «как некоторую функцию» — почему «некоторую»?
 
: {{tick | ticked=1}} обычно вершина в дереве отрезков — node, vertex (у тебя же от этого название «ver» образовано?) — ближе к графам.
 
: {{tick | ticked=1}} обычно вершина в дереве отрезков — node, vertex (у тебя же от этого название «ver» образовано?) — ближе к графам.
Строка 9: Строка 13:
 
: {{tick | ticked=1}} ver * 2 и ver * 2 + 1 — неправильно, так как мы все-таки используем 0-индексацию, а 0 * 2 == 0
 
: {{tick | ticked=1}} ver * 2 и ver * 2 + 1 — неправильно, так как мы все-таки используем 0-индексацию, а 0 * 2 == 0
 
: {{tick | ticked=1}} Отрезки в псевдокоде должны быть полуотурытыми, иначе он у тебя может входить в бесконечную рекурсию. (l=k, r=k => m = k, дальше опять вызов от l=k, r=k).  
 
: {{tick | ticked=1}} Отрезки в псевдокоде должны быть полуотурытыми, иначе он у тебя может входить в бесконечную рекурсию. (l=k, r=k => m = k, дальше опять вызов от l=k, r=k).  
: {{tick}} => смотрится фигово, лучше в техе хотя бы. И названия вершин (1, 2 и т.д.) там в техе пиши. еще в примере в одном месте форматирование поехало.
+
: {{tick | ticked=1}} => смотрится фигово, лучше в техе хотя бы. И названия вершин (1, 2 и т.д.) там в техе пиши. еще в примере в одном месте форматирование поехало.
:: '''не исправлено'''
+
:: '''стрелка не исправлена''' --[[Участник:Dgerasimov|Дмитрий Герасимов]] 14:13, 15 мая 2012 (GST)
 +
: {{tick | ticked=1}} псевдокод стал немного трешовый
 +
:: node, a и b в техе не надо писать. Оставь, пожалуй, в техе только значки пересечения и пустого множества.
 +
:: что такое tree[node]? Значение? Откуда у него тогда поля left и right?
 
: {{tick | ticked=1}} Тут надо просто все нормально переписать, а то как-то обрывисто. Добавить интервики, категории. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 00:08, 7 февраля 2012 (MSK)
 
: {{tick | ticked=1}} Тут надо просто все нормально переписать, а то как-то обрывисто. Добавить интервики, категории. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 00:08, 7 февраля 2012 (MSK)
: {{tick}} какие-то странные опечатки и фразы
+
: {{tick | ticked=1}} какие-то странные опечатки и фразы
 
:: `«причем левые границы обоих отрезков - включительно, а правые — нет»
 
:: `«причем левые границы обоих отрезков - включительно, а правые — нет»
 
:: «Текущий полуинтервал совпадает, то возвращаем»
 
:: «Текущий полуинтервал совпадает, то возвращаем»
 
:: «Используем в реализаций полуинтервалы»
 
:: «Используем в реализаций полуинтервалы»
 
:: «каждый полуинтервал разбивается не более, чем на O(log n)  полуинтервал»
 
:: «каждый полуинтервал разбивается не более, чем на O(log n)  полуинтервал»
 +
 +
== Замечания АС ==
 +
:{{tick|ticked=1}} картинка убогая, да еще и jpg
 +
:{{tick|ticked=1}} ""Если текущий полуинтервал совпадает, то возвращаем значение в текущей вершине."" - это не верно по двум причинам: во-первых совпадает с чем? во-вторых, не совпадает, а подмножество
 +
:{{tick|ticked=1}} и тогда не нужно вот это бредовое замечание: ""Замечание.
 +
При передаче новых параметров следует изменять не только границы, за
 +
которые отвечает текущая вершина, но и границы запрашиваемого
 +
полуинтервала, чтобы на последующих шагах произошло полное совпадение
 +
полуинтервалов.""
 +
:{{tick|ticked=1}} Пример вообще не воспринимается.

Текущая версия на 17:40, 7 июня 2012

описание перенести в шапку статьи
зачем какое-то тире перед началом ссылки в разделе «Ссылки».
отбивай пробел перед открывающейся скобкой.
нужен отступ перед «Например». А то эти напримеры на разном уровне с пунктами, к которым они относятся.
текст лучше писать сразу после слова «Замечание», а то как-то трешово смотрится.
А почему в описании алгоритма одни интервалы полуоткрытые, а другие — закрытые?
не надо объяснять алгоритм на примере RSQ, объясняй на примере абстрактной операции с деревом отрезков. Вот уже в примере работы — ок, пусть будет RSQ.
«возвращаем нулевое значение» — это совсем не абстрактно.
«возвращаем некоторое значение, которое не повлияет на результат запроса на запрашиваемом полуинтервале.» — а теперь вспомним линал за первый семестр — как такой элемент называется? :) нейтральный. --Дмитрий Герасимов 14:13, 15 мая 2012 (GST)
«как некоторую функцию» — почему «некоторую»?
обычно вершина в дереве отрезков — node, vertex (у тебя же от этого название «ver» образовано?) — ближе к графам.
Псевдокод надо делать как можно абстрактнее. Зачем передавать в рекурсию левую и правую границу отрезка, если ты уже передаешь ver? Левую и правую границу можно получить как tree[ver].left, tree[ver].right, значение — как tree[ver].value. И почитай правила оформления псевдокода. Можно вообще передавать в рекурсии node, тогда не нужны будут вот эти ver * 2 и ver * 2 + 1, можно будет вызываться от node.left, node.right.
ver * 2 и ver * 2 + 1 — неправильно, так как мы все-таки используем 0-индексацию, а 0 * 2 == 0
Отрезки в псевдокоде должны быть полуотурытыми, иначе он у тебя может входить в бесконечную рекурсию. (l=k, r=k => m = k, дальше опять вызов от l=k, r=k).
=> смотрится фигово, лучше в техе хотя бы. И названия вершин (1, 2 и т.д.) там в техе пиши. еще в примере в одном месте форматирование поехало.
стрелка не исправлена --Дмитрий Герасимов 14:13, 15 мая 2012 (GST)
псевдокод стал немного трешовый
node, a и b в техе не надо писать. Оставь, пожалуй, в техе только значки пересечения и пустого множества.
что такое tree[node]? Значение? Откуда у него тогда поля left и right?
Тут надо просто все нормально переписать, а то как-то обрывисто. Добавить интервики, категории. --Дмитрий Герасимов 00:08, 7 февраля 2012 (MSK)
какие-то странные опечатки и фразы
`«причем левые границы обоих отрезков - включительно, а правые — нет»
«Текущий полуинтервал совпадает, то возвращаем»
«Используем в реализаций полуинтервалы»
«каждый полуинтервал разбивается не более, чем на O(log n) полуинтервал»

Замечания АС

картинка убогая, да еще и jpg
""Если текущий полуинтервал совпадает, то возвращаем значение в текущей вершине."" - это не верно по двум причинам: во-первых совпадает с чем? во-вторых, не совпадает, а подмножество
и тогда не нужно вот это бредовое замечание: ""Замечание.

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

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