Вторничная задачка :)

← →
Kerk © (2011-05-17 10:40) [0]

Задана последовательность чисел размером N, нужно из этой последовательности убрать минимальное количество элементов так, чтобы она стала упорядоченной по возрастанию

Менять элементы местами нельзя.

← →
KSergey © (2011-05-17 11:00) [1]

Лишь бы как, или быстро?
Лишь бы как - бежим от начала до конца, если встречается символ, мешающий требованию "возрастания" - его убираем.
Запоминаем сколько убрали
Потому убираем первый символ (начинаем со второго пробег) - и снова "убираем" те, которые мешают последовательному возрастанию.
Потом начинаем с третьего.
Не забываем при каждом пробеге учесть, что пропущенные с начала символы - это уже убранные, их надо прибавить к результату.

Из всех вариантов выбираем наилучший.

← →
Kerk © (2011-05-17 11:02) [2]

> KSergey © (17.05.11 11:00) [1]
>
> Лишь бы как, или быстро?

Желательно быстро, конечно.

Я не очень понял как твой алгоритм поведет себя на таких данных
1 2 3 7 4 5 6

← →
TUser © (2011-05-17 11:07) [3]

Память и время какое надо?

← →
Kerk © (2011-05-17 11:12) [4]

Время как можно быстрее, память будем считать, что не важна.

← →
TUser © (2011-05-17 11:17) [5]

> Желательно быстро, конечно.

А пямять побоку? Тогда заводим рядом массив 1, 2, ... , который сортируем по значениям первого массива с такими индексами. Далее бежим по нему, находим наиболее длинную возрастающую подпоследовательность индексов. Время логлинейное, но дополнительная линейная память. Для 1 2 3 7 4 5 6 массив индексов отсортируется как 1 2 3 5 6 7 4, то есть удаляем 4й элемент - семерку.

Есть более оптимальное решение (или не стоит думать)?

зы. Кажется, можно без дополнительной памяти, но за квадрат времени.

← →
Юрий Зотов © (2011-05-17 11:27) [6]

> нужно из этой последовательности убрать

Зачем?
:o)

← →
Упорядочить (2011-05-17 11:49) [7]

> KSergey © (17.05.11 11:00) [1]

Похоже на нормальное (а может быть и единственное, отвечающее условию) решение.
Непонятно для чего несколько пробегов?
Просто пишем "неудаленные" в параллельный массив рядом (не забывая считать удаленные)
:)

← →
Очень злой (2011-05-17 12:01) [8]

> Тогда заводим рядом массив 1, 2, ... , который сортируем
> по значениям первого массива с такими индексами. Далее бежим
> по нему, находим наиболее длинную возрастающую подпоследовательность
> индексов. Время логлинейное, но дополнительная линейная
> память. Для 1 2 3 7 4 5 6 массив индексов отсортируется
> как 1 2 3 5 6 7 4, то есть удаляем 4й элемент - семерку.
>

Хм... А если такой пример:
5 7 1 2 3 4 8 6 9

очевидно, что нужно выкинуть 5 7 8 и оставить 1 2 3 4 6 9 (ну или выкинуть 5 7 6, а оставить 1 2 3 4 8 9)

Но по твоему алгоритму получаем массив индексов:
3 4 5 6 1 8 2 7 9
где наиболее длинная возрастающая подпоследовательность индексов состоит всего из 4 элементов.

← →
TUser © (2011-05-17 12:05) [9]

да, действительно *(

← →
Очень злой (2011-05-17 12:25) [10]

> KSergey © (17.05.11 11:00) [1]
>
> Лишь бы как, или быстро?
> Лишь бы как - бежим от начала до конца, если встречается
> символ, мешающий требованию "возрастания" - его убираем.
>
> Запоминаем сколько убрали
> Потому убираем первый символ (начинаем со второго пробег)
> - и снова "убираем" те, которые мешают последовательному
> возрастанию.
> Потом начинаем с третьего.
> Не забываем при каждом пробеге учесть, что пропущенные с
> начала символы - это уже убранные, их надо прибавить к результату.
>
>
> Из всех вариантов выбираем наилучший.
>

Ну можно с каждым следующим пробегом убирать не первый симвой, а начальную возрастающую подпоследовательность. Т.е. на предыдущей пробежке запоминать первый символ, который пришлось выкинуть, и следующую пробежку уже начинать с него.

← →
Очень злой (2011-05-17 12:33) [11]

Стоп.

> KSergey © (17.05.11 11:00) [1]

В этом алгоритме пооже тоже есть ошибка.

Пример: последовательность:
1 2 3 4 8 9 5 6 7

очевидно что нужно выкинуть 8 9 (оставить 1 2 3 4 5 6 7).
Но по данному алгоритму выкинется 5 6 7
Если конечно я все правильно понимаю...

← →
KSergey © (2011-05-17 13:14) [12]

> Очень злой (17.05.11 12:33) [11]
> Пример: последовательность:
> 1 2 3 4 8 9 5 6 7
>
> очевидно что нужно выкинуть 8 9 (оставить 1 2 3 4 5 6 7).
>
> Но по данному алгоритму выкинется 5 6 7

Точно.
Надо дальше думать

← →
KSergey © (2011-05-17 13:16) [13]

тогда, наверное, надо сразу разбить на группы, в пределах каждой из которых есть возрастание (пусть и из оного элемента) и последовательно подобным же образом убирать целиком группы, сравнивая осталось ли возрастание и столько убрали.
но продумывать уже лень
по работе сейчас не менее запутанные цепочки как раз продумываю :)

← →
TUser © (2011-05-17 13:41) [14]

// Root - корень дерева

function InsertChild (Parent, Value)
if Parent >= Value then return false
for every child of Parent do
InsertChild (child, Value)
if never inserted then
Parent.NewChild := Value
return true

// begin
Root := -MaxInt;
for i := 0 to high do
InsertChild (Root, Arr[i]);
return the longest way in the tree

← →
Kerk © (2011-05-17 13:58) [15]

> TUser © (17.05.11 13:41) [14]

Не очень понял твой код. Но сама идея похожа на правду :)

← →
TUser © (2011-05-17 14:10) [16]

только if never inserted then заменить на if there are child where was not inserted

это полный перебор, так что никакой "оптимальности"

← →
Очень злой (2011-05-17 15:25) [17]

> Не очень понял твой код.

Тоже не совсем понял. особенно не понял, что такое "корень дерева".
если эту задачу представлять в виде дерева, то там должно получиться хитрое дерево, с несколькими корнями и несколькими "конечностями".

← →
TUser © (2011-05-17 16:38) [18]

А дерево с несколькими корнями - это я не понимаю. В коде - там просто перебор. На каждой итерации нам надо хранить все потенциальные возрастающие подпоследовательности. Например для 1 2 3 4 6(1) 8(1) 5 6(2) 7 8 9 надо хранить последовательности

1 2 3 4 6(1) 8(1) 9
1 2 3 4 6(1) 7 8 9
1 2 3 4 5 6(2) 7 8 9

удобнее всего 1 2 3 4 хранить один раз, далее дерево разветвляется. Если мы поставили 6(1) а дальше встретили 8(1), то так и продолжаем. Потом встретили 5, она может войти только после 4. 6(2) может быть продолжением этой 5 (очевидно, что 6(2) бессмысленно ставить после, например 3 или 4 - т.к. это соответствует просто более коротким последовательностям). Семерку можно вставить в конец одной из двух веток. Ну и т.д.

То есть каждую число мы пытаемся вставить в те ветки, которые заканчиваются меньшим числом. Если у нас есть некий узел дерева, то возможно два варианта: 1. узел больше или равен числу, тогда число не может его продолжать, 2. узел меньше числа, тогда узел есть часть подпоследовательности(ей), куда надо добавить число. Тогда либо 2а. у узла нет детей - добавляем туда новое число, 2б. проверяем всех детей этим же алгоритмом, если ни к какому детю нельзя добавить новое число, то добавляем новое дите. Например, 5 добавляется новым дитем после 4, тк у 4 в этот момент один деть, и это 6(1).

Ну и инициируем "алгоритм" начальным числом, которое меньше всех. Это "в лоб" и совсем небыстро (время и память - n*log(n)), но лучше я не знаю.

← →
MBo © (2011-05-17 17:37) [19]

>TUser © (17.05.11 16:38) [18]
>n*log(n)), но лучше я не знаю

Лучшее известное (и вроде доказанное) время для этой задачи и есть n*log(n)(точнее, n*log(MaxIncSeqLen))

← →
Очень злой (2011-05-17 19:50) [20]

2 TUser напиши на Дельфи рабочий пример чтобы было понятнее.

а то, что-то в голову приходят только либо некое подобие волнового алгоритма (с хз какой сложностью), либо рекурсивный со сложностью вроде как 2^n

А то самому стало интерестно...

← →
TUser © (2011-05-17 22:20) [21]

{$apptype console} uses SysUtils; type PTree = ^TTree; TTree = record Value: integer; Children: array of PTree; Parent: PTree; end; procedure FreeTree (var Tree: PTree); var i: integer; begin with Tree^ do for i := 0 to length (Children) - 1 do FreeTree (Children[i]); Dispose (Tree); end; procedure AddChild (Tree: PTree; Value: integer); var i: integer; begin with Tree ^ do begin i := length (Children); SetLength (Children, i + 1); New (Children[i]); SetLength (Children[i]^.Children, 0); Children[i]^.Parent := Tree; end; Tree^.Children[i]^.Value := Value; end; function InsertChild (Tree: PTree; Value: integer): boolean; var i: integer; create: boolean; begin result := Tree^.Value < Value; if not result then exit; create := length (Tree^.Children) = 0; if not create then for i := 0 to length (Tree^.Children) - 1 do if not InsertChild (Tree^.Children[i], Value) then create := true; if create then AddChild (Tree, Value); end; procedure GetDeepest (Tree: PTree; Depth: integer; var Max: PTree; var MaxDepth: integer); var i: integer; begin if Depth > MaxDepth then begin MaxDepth := Depth; Max := Tree; end; with Tree^ do for i := 0 to length (Children) - 1 do GetDeepest (Children[i], Depth + 1, Max, MaxDepth); end; procedure PrintDeepest (Root: PTree); var max, tree: PTree; md: integer; begin max := nil; md := 0; GetDeepest (Root, 1, max, md); tree := max; while tree <> nil do begin write (tree^.Value, " "); tree := tree^.Parent; end; writeln; end; var Root: PTree; i: integer; begin New (Root); with Root ^ do begin SetLength (Children, 0); Value := -MaxInt; Parent := nil; end; for i := 1 to ParamCount do InsertChild (Root, StrToInt (ParamStr (i))); PrintDeepest (Root); FreeTree (Root); end.

dcc32 vtornik.dpr

vtornik 1 2 3 7 4 5 6

6 5 4 3 2 1 -2147483647

← →
Sha © (2011-05-18 00:45) [22]

> MBo © (17.05.11 17:37) [19]

так?

type TNums= array of integer; TSaveRec= record EndPos: integer; NumPos: integer; end; TSave= array of TSaveRec; function MaxSeq(const Nums: TNums): TNums; var Ends: TNums; Save: TSave; i, left, right, middle, hiend: integer; begin; if Length(Nums)=0 then SetLength(Result,0) else begin; SetLength(Ends,Length(Nums)); SetLength(Save,Length(Nums)); hiend:=0; Ends[hiend]:=0; with Save[0] do begin; EndPos:=hiend; NumPos:=Ends[hiend]; end; for i:=1 to Length(Nums)-1 do begin; left:=0; right:=hiend; while true do begin; //двоичный поиск; считаем, что нет дубликатов middle:=(left+right) shr 1; if Nums[i]-Nums[Ends[middle]]<=0 then right:=middle-1 else left:=middle+1; if left>right then begin; Ends[right+1]:=i; with Save[i] do begin; EndPos:=right+1; NumPos:=i; end; if left>hiend then hiend:=hiend+1; break; end; end; end; SetLength(Result,hiend+1); hiend:=hiend; for i:=Length(Nums)-1 downto 0 do with Save[i] do if EndPos=hiend then begin; Result[hiend]:=Nums[NumPos]; hiend:=hiend-1; end; end; Ends:=nil; Save:=nil; end; procedure TForm1.Button1Click(Sender: TObject); var Nums, Seq: TNums; i: integer; begin; SetLength(Nums,10); Nums[0]:=0; Nums[1]:=1; Nums[2]:=2; Nums[3]:=3; Nums[4]:=4; Nums[5]:=8; Nums[6]:=9; Nums[7]:=5; Nums[8]:=6; Nums[9]:=7; Seq:=MaxSeq(Nums); Memo1.Lines.Clear; Memo1.Lines.Add("length: "+IntToStr(Length(Seq))); for i:=0 to Length(Seq)-1 do begin; Memo1.Lines.Add(IntToStr(Seq[i])); end; end;

← →
Игорь Шевченко © (2011-05-18 01:19) [23]

> for i:=Length(Nums)-1 downto 0 do with Save[i] do if EndPos=hiend
> then begin;
> Result[hiend]:=Nums[NumPos];
> hiend:=hiend-1;
> end;
> end;

Первая строка шедевральная. Может, монитор апгрейдить на пошире ?

← →
Sha © (2011-05-18 01:22) [24]

Игорь, у тебя все еще 15" ?

> Игорь, у тебя все еще 15" ?

продам монитор 15.1"
дорого

>Sha
>так?
Похоже, да.

Я, когда баловался с этой задачей, только до вычисления длины дошёл, а корректное сохранение последовательности не осилил.
Суть: элемент Ai можно прицеплять к последовательностям длиной 1..i, последний член которых меньше Ai.
Best[i] хранит лучший конец последовательности длиной i (т.е. наименьший из всех таких последовательностей).
Best - возрастающий массив, так что поиск на нем нетруден.

Prev - была попытка запомнить самую лучшую последовательность, но мой подход неверен (проявится на массивах типа Nums := TNums.Create(3, 9, 5, 8, 6, 11, 14, 2, 7, 13, 1, 15, 9);)

function Sequence(A: array of Integer): Integer; var i, LastSuitable, MaxLen: Integer; Best: array of Integer; // Prev: array of Integer; begin if Length(A) = 0 then begin MaxLen := 0; Exit; end; // SetLength(Prev, Length(A) + 1); SetLength(Best, Length(A) + 2); MaxLen := 1; Best[1] := A[0]; for i := 2 to Length(A) + 1 do Best[i] := MaxInt; for i := 1 to High(A) do begin //после отладки - замена на binary search LastSuitable := 1; while Best[LastSuitable] < A[i] do Inc(LastSuitable); Best[LastSuitable] := A[i]; // Prev[LastSuitable] := i; if LastSuitable > MaxLen then MaxLen := LastSuitable; end; Result := MaxLen; end;

> 3, 9, 5, 8, 6, 11, 14, 2, 7, 13, 1, 15, 9

[21] говорит 3 5 8 11 14 15, вроде то

Best да, стоило бы сохранять.

> MBo

У меня все то же самое. Только массив лучших концов называется Ends.

Сохранение цепочек делал так.
На момент окончания вычислений Ends уже не содежит состояние,
предшествующее получению последней самой длинной цепочки.
Его надо как-то откатить.
Для этого заметим, что в цикле для каждого элемента массива
мы находили и изменяли содержимое ровно одного конца.
Поэтому достаточно сохранять только измененный конец,
а не все вычисленные.

Т.е. Save хранит трассу вычислений, а Ends - состояние.

Р.S.
После отладки остались "водные знаки", их можно выкинуть:
hiend:=hiend; Ends:=nil; Save:=nil;

и еще, т.к. на момент окончания поиска всегда выполняется соотношение left=right+1, то можно вместо
Ends[right+1]:=i; with Save[i] do begin; EndPos:=right+1; NumPos:=i; end;
писать
Ends[left]:=i; with Save[i] do begin; EndPos:=left; NumPos:=i; end;

← →
Скептик (2011-05-18 09:39) [31]

В общем случае задача имеет не единственное решение.
Какому отдать предпочтение?

> Скептик

Цепочек заданной (в том числе максимальной) длины может быть несколько.
Проще и быстрее всего можно найти цепочки,
оканчивающися наименьшим элементом или начинающиеся с наибольшего.
В этом случае на каждом шаге алгоритма работает двоичный поиск.

Подчистил код:
type TNum= integer; TNums= array of TNum; TLogRec= record Pos: integer; Num: TNum; end; TLog= array of TLogRec; function MaxSeq(const Nums: TNums): TNums; var Ends: array of integer; Log: TLog; i, Left, Right, Middle, MaxPos: integer; begin; if Length(Nums)=0 then SetLength(Result,0) else begin; SetLength(Ends,Length(Nums)); SetLength(Log,Length(Nums)); MaxPos:=0; Ends[MaxPos]:=0; with Log[0] do begin; Pos:=MaxPos; Num:=Nums[Ends[MaxPos]]; end; for i:=1 to Length(Nums)-1 do begin; Left:=0; Right:=MaxPos; repeat; //двоичный поиск; считаем, что нет дубликатов Middle:=(Left+Right) shr 1; if Nums[i]<=Nums[Ends[Middle]] then Right:=Middle-1 else Left :=Middle+1; until Left>Right; Ends[Left]:=i; with Log[i] do begin; Pos:=Left; Num:=Nums[i]; end; if Left>MaxPos then MaxPos:=MaxPos+1; end; SetLength(Result,MaxPos+1); for i:=Length(Log)-1 downto 0 do with Log[i] do if Pos=MaxPos then begin; Result[MaxPos]:=Num; MaxPos:=MaxPos-1; end; end; end;

Немного упростил:
type TNum= integer; TNums= array of TNum; TLogRec= record Pos: integer; Num: TNum; end; TLog= array of TLogRec; //поиск возрастающей последовательности максимальной длины function MaxSeq(const Nums: TNums): TNums; var Ends: TNums; Log: TLog; i, Left, Right, Middle, MaxPos, NumCount: integer; begin; NumCount:=Length(Nums); if NumCount=0 then SetLength(Result,0) else begin; SetLength(Ends,NumCount); SetLength(Log,NumCount); MaxPos:=-1; for i:=0 to NumCount-1 do begin; Left:=0; Right:=MaxPos; while Left<=Right do begin; //двоичный поиск; считаем, что нет дубликатов Middle:=(Left+Right) shr 1; if Nums[i]<=Ends[Middle] then Right:=Middle-1 else Left :=Middle+1; end; with Log[i] do begin; Pos:=Left; Num:=Nums[i]; Ends[Left]:=Num; end; if Left>MaxPos then MaxPos:=MaxPos+1; end; SetLength(Result,MaxPos+1); for i:=NumCount-1 downto 0 do with Log[i] do if Pos=MaxPos then begin; Result[MaxPos]:=Num; MaxPos:=MaxPos-1; end; end; end;

и еще немного:
//Поиск возрастающей последовательности чисел максимальной длины //в последовательности неповторяющихся чисел. //Наилучшая цепочка длины L - подпоследовательность, содержащая наименьший //последний элемент среди всех возрастающих подпоследовательностей длины L. //Очевидно, что у более длинных наилучших цепочек последний элемент больше, //чем у более коротких наилучших цепочек, т.к. длинная цепочка всегда //содержит короткую. //Алгоритм в цикле для всех i=0..Length(Nums)-1 и всех подмассивов Nums[0..i] //находит наилучшие цепочки всех возможных длин. Последние элементы цепочек //запоминаются в массиве Ends. На каждом шагу алгоритма изменяется ровно один //элемент массива Ends, т.к. последний элемент изменяется только в цепочке //одной длины. Этот элемент находится при помощи двоичного поиска. //Результат формируется на основании (последних) позиций чисел, //которые они занимали в наилучших цепочках. type TNum= integer; TNums= array of TNum; function MaxSeq(const Nums: TNums): TNums; var NumPos: array of integer; //NumPos[i] - позиция числа Nums[i] в цепочке Ends: TNums; //Ends[i] - последнее число цепочки длины i+1 MaxPos: integer; //текущая верхняя граница массива Ends i, Left, Right, Middle, NumCount: integer; begin; NumCount:=Length(Nums); if NumCount=0 then SetLength(Result,0) else begin; SetLength(NumPos,NumCount); SetLength(Ends,NumCount); MaxPos:=-1; //определяем позицию каждого числа в цепочке for i:=0 to NumCount-1 do begin; Left:=0; Right:=MaxPos; while Left<=Right do begin; //двоичный поиск; считаем, что нет дубликатов Middle:=(Left+Right) shr 1; if Nums[i]<=Ends[Middle] then Right:=Middle-1 else Left :=Middle+1; end; NumPos[i]:=Left; Ends[Left]:=Nums[i]; if MaxPos<Left then MaxPos:=Left; end; //формируем результат SetLength(Result,MaxPos+1); i:=NumCount; while true do begin; dec(i); if NumPos[i]=MaxPos then begin; Result[MaxPos]:=Nums[i]; dec(MaxPos); if MaxPos<0 then break; end; end; end; end;

Вторничная задачка :) Найти похожие ветки