Обсуждение:Задача о наибольшей возрастающей подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
: {{tick | ticked=1}} оформить номрально разделы и добавить содержание
 
: {{tick | ticked=1}} оформить номрально разделы и добавить содержание
 
: {{tick | ticked=1}} Оформить псевдокод в соответствии с правилами, а то там куча левых операторов, For вместо for и т.д.
 
: {{tick | ticked=1}} Оформить псевдокод в соответствии с правилами, а то там куча левых операторов, For вместо for и т.д.
−
: {{tick}} Раздел «Постановка задачи» не нужен, итак понятно что в статье про задачу главная цель — решить задачу. Просто поместить постановку задачи в шапку.
+
: {{tick | ticked=1}} Раздел «Постановка задачи» не нужен, итак понятно что в статье про задачу главная цель — решить задачу. Просто поместить постановку задачи в шапку.
−
: {{tick}} Пишешь, что строим таблицу a[1..n], а в псевдокоде — строишь с 0 .. n.
+
: {{tick | ticked=1}} Не надо описывать ввод данных и вывод данных. Оформляй псевдокод как функцию, принимающую входные данные и возвращающую результат. Если она выдает наибольшую возрастающую подпоследовательность, то и возвращай vector<int>, или int[], например, а не выводи.
−
: {{tick}} Не надо описывать ввод данных и вывод данных. Оформляй псевдокод как функцию, принимающую входные данные и возвращающую результат. Если она выдает наибольшую возрастающую подпоследовательность, то и возвращай vector<int>, или int[], например, а не выводи.
+
: {{tick | ticked=1}} Разделы первого уровня обособляются как == Раздел ==, а не как ==== Раздел ====
−
: {{tick}} В псевдокоде за n^2, видимо, опечатка — вроде должно быть if (x[j] < x[i]). А x в псевдокоде вообще нигде не упоминается. В общем, см. предыдущий пункт.
+
: {{tick | ticked=1}} Почему наибольшая возрастающая последовательность в псевдокоде называется lsa?
−
: {{tick}} Читай правила оформления псевдокода про круглые скобки вокруг внешнего условия for, if и т.д.
 
−
: {{tick}} Почему наибольшая возрастающая последовательность в псевдокоде называется lsa?
 
−
: {{tick}} Разделы первого уровня обособляются как == Раздел ==, а не как ==== Раздел ====
 
  
−
: Алгоритм за n log n проверю завтра. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 10:22, 1 декабря 2011 (MSK)
+
== Алгоритм за n^2 ==
  
−
: {{tick}} В разделе про алгоритм за <tex> O(n \log n) </tex> треш и муть. Зачем-то написано про нестрогое возрастание, хотя в определении LIS оно строгое, в псевдокоде имена не соотвествуют друг другу. Лучше вообще переписать его и псевдокод заново.
+
: {{tick | ticked=1}} Про оформление псевдокода(правила его оформелния находятся тут [[Обсуждение:Дискретная математика и алгоритмы]]) :
−
: {{tick}} для обоих алгоритмов написать псевдокоды восстановления LIS. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 10:40, 15 октября 2011 (MSD)
+
:* Учти, что for в виде for i = a..b обозначает итерирование от a до b '''включительно'''. То есть он эквивалентен for (int i = a; i <= b; i++).
 +
:* теперь, когда твой код — функция, делай отступ в 4 пробела, как и принято. Тогда и фигурные скобки не понадобятся. Кстати, у блока кода в цикле for тоже должен быть отступ в 4 пробела относительно оператора for, а не восемь. Вообще лучше написать сначала код в каком-нибудь notepad++, а потом сюда вставлять — тогда не придётся ручками считать пробелы.
 +
:* n у тебя нигде не определён. Пиши лучше a.size(даже без () можно), например. maxN тоже не определён.
 +
:* пишем <code>vector<int></code> как это принято — без пробела перед шаблонными аргументами.
 +
:* Читай правила оформления псевдокода про круглые скобки вокруг внешнего условия for, if и т.д.
 +
:* Опять же, не пиши в псевдокоде лишние детали, относящиеся к конскретному языку программирования. Зачем писать revese(v.begin(), v.end()). Человек, не знакомый с C++, это не поймёт, лучше просто reverse(v), или v.reverse().
 +
 
 +
: {{tick | ticked=1}} В псевдокоде за n^2 всё ещё какой-то треш. Ты подсчитываешь динамику в том же входном массиве '''a'''. А d у тебя используется только при восстановлении НВП. А в описании алгоритма вообще используется x. Массив динамики у тебя с 0-индексацией, а база — в первом элементе. В общем, перечитай внимательно всё и напиши нормальный псевдокод.
 +
--[[Участник:Dgerasimov|Дмитрий Герасимов]] 22:45, 2 декабря 2011 (MSK)
 +
 
 +
: {{tick | ticked=1}} Вот теперь всё отлично и понятно. Только в описании ошибка — «d[i] = max(d[j] для всех j …» — надо к максимуму 1 прибавить же.
 +
 
 +
== Алгоритм за n log n ==
 +
 
 +
: {{tick | ticked=1}} Для <= в tex есть \le
 +
: {{tick | ticked=1}} Во время заполнения d в псевдокоде ты затираешь нулевой элемент бесконечностью.
 +
: {{tick | ticked=1}} size у тебя нигде не инизиализируется
 +
: {{tick | ticked=1}} a же должно быть размера n? Тогда у тебя произойдёт выход за границу массива, так как происходит n+1 итерация.
 +
: {{tick | ticked=1}} те же замечания насчёт скобок вокруг условия if, while, for и т.д.
 +
 
 +
: {{tick | ticked=1}} Ещё нужно добавить категории. Какие именно — написано в правилах оформления конспектов.
 +
--[[Участник:Dgerasimov|Дмитрий Герасимов]] 05:45, 3 декабря 2011 (MSK)

Текущая версия на 06:33, 3 декабря 2011

☑ оформить номрально разделы и добавить содержание
☑ Оформить псевдокод в соответствии с правилами, а то там куча левых операторов, For вместо for и т.д.
☑ Раздел «Постановка задачи» не нужен, итак понятно что в статье про задачу главная цель — решить задачу. Просто поместить постановку задачи в шапку.
☑ Не надо описывать ввод данных и вывод данных. Оформляй псевдокод как функцию, принимающую входные данные и возвращающую результат. Если она выдает наибольшую возрастающую подпоследовательность, то и возвращай vector<int>, или int[], например, а не выводи.
☑ Разделы первого уровня обособляются как == Раздел ==, а не как ==== Раздел ====
☑ Почему наибольшая возрастающая последовательность в псевдокоде называется lsa?

Алгоритм за n^2

☑ Про оформление псевдокода(правила его оформелния находятся тут Обсуждение:Дискретная математика и алгоритмы) :
  • Учти, что for в виде for i = a..b обозначает итерирование от a до b включительно. То есть он эквивалентен for (int i = a; i <= b; i++).
  • теперь, когда твой код — функция, делай отступ в 4 пробела, как и принято. Тогда и фигурные скобки не понадобятся. Кстати, у блока кода в цикле for тоже должен быть отступ в 4 пробела относительно оператора for, а не восемь. Вообще лучше написать сначала код в каком-нибудь notepad++, а потом сюда вставлять — тогда не придётся ручками считать пробелы.
  • n у тебя нигде не определён. Пиши лучше a.size(даже без () можно), например. maxN тоже не определён.
  • пишем vector<int> как это принято — без пробела перед шаблонными аргументами.
  • Читай правила оформления псевдокода про круглые скобки вокруг внешнего условия for, if и т.д.
  • Опять же, не пиши в псевдокоде лишние детали, относящиеся к конскретному языку программирования. Зачем писать revese(v.begin(), v.end()). Человек, не знакомый с C++, это не поймёт, лучше просто reverse(v), или v.reverse().
☑ В псевдокоде за n^2 всё ещё какой-то треш. Ты подсчитываешь динамику в том же входном массиве a. А d у тебя используется только при восстановлении НВП. А в описании алгоритма вообще используется x. Массив динамики у тебя с 0-индексацией, а база — в первом элементе. В общем, перечитай внимательно всё и напиши нормальный псевдокод.

--Дмитрий Герасимов 22:45, 2 декабря 2011 (MSK)

☑ Вот теперь всё отлично и понятно. Только в описании ошибка — «d[i] = max(d[j] для всех j …» — надо к максимуму 1 прибавить же.

Алгоритм за n log n

☑ Для <= в tex есть \le
☑ Во время заполнения d в псевдокоде ты затираешь нулевой элемент бесконечностью.
☑ size у тебя нигде не инизиализируется
☑ a же должно быть размера n? Тогда у тебя произойдёт выход за границу массива, так как происходит n+1 итерация.
☑ те же замечания насчёт скобок вокруг условия if, while, for и т.д.
☑ Ещё нужно добавить категории. Какие именно — написано в правилах оформления конспектов.

--Дмитрий Герасимов 05:45, 3 декабря 2011 (MSK)

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:Задача_о_наибольшей_возрастающей_подпоследовательности&oldid=13869»