IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Волнистая последовательность
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 3
Пол: Мужской

Репутация: -  0  +


Назовенм последовательность волнистой если для всех кроме первого элемента выполняется: для всех элементов кроме первого и последнего, что либо этот член последовательности больше всех своих соседей, либо меньше.
Например : 12121212121-волнистая
а 123321 - нет
дана последовательность и надо из неё выделить самую большую волнистую подпоследовательность .
Последовательность храниться в массиве помогите хоть алгоритмом.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Идем слева направо по последовательности, и помним, сколько (максимум) последних прочитанных символов удовлетворяют условию "волнистости". А именно:

1. Один символ всегда волнистый.
2. Два символа, только если они не равны, волнистые.
3. n+1 символов - волнистые, если первые n из них - волнистые, и для n-го символа выполняется условие "больше всех своих соседей, либо меньше"


Получается алгоритм:

1. Прочитать следующий символ. Считать его первым в искомой подстроке (ПИП)
2. Прочитать следующий символ. Если он равен ПИП, считать его ПИПом и перейти к шагу 2
3. Иначе считать его вторым в искомой подстроке (ВИП). Найден ответ длины 2.
4. Прочитать следующий символ. Если он равен предыдущему прочитанному, считать его ПИПом и перейти к шагу 2
5. Проверить для предыдущего символа (стоящего перед только что прочитанным) условие волнистости. Если оно выполняется, перейти к шагу 4.
6. Иначе запомнить найденный ответ (не включая последний прочитанный символ). Последних два прочитанных символа считать ПИПом и ВИПом соответственно, и перейти к шагу 4.

При этом "запомнить найденный ответ" означает не вырезать саму подстроку (подмассив), а просто запомнить индексы первого (ПИП) и последнего элементов в подпоследовательности.

Алгоритм получается линейный.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 3
Пол: Мужской

Репутация: -  0  +


нет, вы неправильно мепня поняяли. Подпоследовательностью последовательности (Xn) я имею ввиду любой упорядоченный набор элементов последовательности (yn) где если Yi , yj ( элементы последовательности) и I>j то номер элемента Yi в последовательности Xn будет больше номера Yj в последовательности Xn
Например:
Xn : 1 2 3 4 5 6 7 8 9 0
Yn : 1 3 5 7 9
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






xprogrammer, а теперь перечитай свой первый пост... Там хоть что-то ВООБЩЕ про вторую последовательность было? Чего ты сразу полностью условие не написал?

Значит, так... По 5 (как минимум) примеров ДА волнистых и НЕ волнистых последовательностей приведи, только больше условия меняться не будут. Как приведешь - так и получишь ответ.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 3
Пол: Мужской

Репутация: -  0  +


Волнистые: 1 2 1 2 1 2 1 3 2 6 1 8 4
77
12 13
1 0 5 4
2 6 0 7 6
Не волнистые: 2 2
1 1 2 1 3 1
1 2 3 2 3
2 1 0 1 2 3
2 3 2 3 22 3





примеры : вход : 1 1 2 1 1
выход: 1 2 1
вход : 1 2 3 2 1
выход: 1 3 1
вход: 1 3 2 5 4
выход: 1 3 2 5 4
вход: 1 2 1 5 9
выход: 1 2 1 5


если не понятно, то вы скажите что и я поясню
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(xprogrammer @ 3.11.2006 22:25) *

Подпоследовательностью последовательности (Xn) я имею ввиду любой упорядоченный набор элементов последовательности (yn) где если Yi , yj ( элементы последовательности) и I>j то номер элемента Yi в последовательности Xn будет больше номера Yj в последовательности Xn


О, вот это уже поинтереснее smile.gif

Считаем, что в массиве все числа - от 0 до n-1. Если это не так, то понятно, что можно построить биекцию.

Введем понятие верхних и нижних волнистых подпоследовательностей. Верхней называем такую, у которой последнее число *больше* предпоследнего, нижней - такую, у которой последнее число *меньше* предпоследнего. Подпоследовательности длины 0 и 1 являются и верхними, и нижними одновременно.

Заведем два массива: А[0 .. n-1] и В[0 .. n-1]. Изначально A[i] = B[i] = 0 для всех i.

Идем слева направо по входному массиву (напомню, что все числа в нем - от 0 до n-1). После прочтения каждого числа состояние массивов А и В должно быть таким: A[i] - длина максимальной волнистой верхней подпоследовательности в прочитанном куске, оканчивающейся числом i, B[i] - длина максимальной волнистой нижней подпоследовательности в прочитанном куске, оканчивающейся числом i.

В начале все A[i] = B[i] = 0, потому что еще ничего не прочитано. Теперь, пусть мы прочли число x. В результате могут поменяться только значения A[x] и B[x]. Они станут равны:

A[x] = max(B[0], B[1], B[2], .., B[x-1]) + 1

B[x] = max(A[x+1], A[x+2], A[x+3], .. , A[n - 1]) + 1

Действительно, чтобы с помощью х получить наилучшую верхнюю подпоследовательность, нужно приписать х к наилучшей из найденных нижних подпоследовательностей, оканчивающихся числами, меньшими х. И наоборот.

Пройдя слева направо по всему входному массиву, мы заполним постепенно массивы А и В. Теперь наибольшему из всех чисел в А и В соответствует самая длинная волнистая подпоследовательность. Как ее теперь построить - додумаешь сам.

Вот. Это решение очень легко пишется, и работает за квадрат. Если тебе надо за n log n, разберись с этим, и приходи smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


Ты помоему не прав биекцию ты непосроишь в последовательностях:
1-2-1-2-1-2-1-2-1-2-1-2-1-2-1-2-1
и
1-2-1-2-1-2-1-2-1-2-2-2-1-2-1-2-1


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Reflex @ 4.11.2006 12:45) *

Ты помоему не прав биекцию ты непосроишь в последовательностях:
1-2-1-2-1-2-1-2-1-2-1-2-1-2-1-2-1
и
1-2-1-2-1-2-1-2-1-2-2-2-1-2-1-2-1

Речь немного не о том..
Допустим, последовательность такая:
-5 0 4 8 20 9

Ее можно отождествить (в терминах задачи) с такой:
0 1 2 3 5 4

Так как абсолютное значение разности не важно. Важно только больше или меньше..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


тогда я не понимаю почему это алгоритм будет работать ... но посмотрим что автор сделает ...


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


не понела как он будет работать на 1-2-1-2-1-2-1
поясните кто - ни буть пока наш ночной программер не пришел


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Если честно, не могу врубиться в решение Рыбака - видимо, сказывается то, что уже полпятого ночи (или утра smile.gif)..
Но вот так, на вскидку, не понимаю также, в чем собсно, проблема с алгоритмом.
Что если сделать так..

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

Замечу еще, что искомых подпоследовательностей может быть несколько. Даже приведенный мной алгоритм неоднозначен (в п.1), но неоднозначностей на самом деле больше. Например, для полседовательности
1 3 4 2
ответов может быть два:
1 3 2
или
1 4 2 .
Мой алгоритм из многих возможных выбирает подпоследовательность с максимальной амплитудой волн. Самую штормовую smile.gif.

Если я не прав - скажите, где smile.gif

Простите, забыл представиться: lapp, к вашим услугам smile.gif

Сообщение отредактировано: lapp -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Пионер
**

Группа: Пользователи
Сообщений: 118
Пол: Женский

Репутация: -  0  +


program Problem;

{$APPTYPE CONSOLE}

uses
SysUtils;


var n : integer;
var posl : array [0..100000] of integer;
count, last,sum1,sum2 : integer;
a,b : array [1..100000] of char;
znak : char;

procedure read_data;
var i: integer;
begin
assign(input, 'wave.in');
assign(output, 'wave.out');
reset(input);
rewrite(output);
readln(n);
for i := 1 to n do read(posl[i]);
close(input);
end;

function min(a,b:integer):integer;
begin
if a>b then result:=b else result:=a;
end;
var i: integer;
begin
read_data;
count:=0;
case n of
1 : write(0);
2 : if posl[1]=posl[2] then write(1) else write(0);
else begin
for i:= 2 to n do begin
if posl[i]>posl[i-1] then a[i-1]:='+';
if posl[i]=posl[i-1] then a[i-1]:='0';
if posl[i]<posl[i-1] then a[i-1]:='-';
end;
if a[1]='0' then inc(count);
for i:= 2 to n-1 do
if (a[i]=a[i-1])or(a[i]='0') then inc(count);
write(count);
end;
end;
close(output);
end.
ВОт реализация, алгоритма Lapp


--------------------
Нам не дано предугадать как наше слово отзовется...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Reflex, я праввильно понял, что ты выдаешь только длину максимальной подподпод..под.. блин, уже язык заплетается.. smile.gif подпоследовательности!
Вопрос, мне кажется, стоял в нахождении ее самой..
И, извини, уже падаю на кровать... хватит на сего... хр..хррррр...


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Гость @ 4.11.2006 14:37) *

Если я не прав - скажите, где smile.gif


Прав smile.gif *насвистывая*

Я тогда уж своё объяснять, наверное, не стану. Если кому сильно интересно - могу ответить на конкретные вопросы smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Что - то вы тут разшлись, может я что не так понял конечно, вот таккой вариант пойдет ?

uses crt;
const
n = 6;

type
TArray = array [1..n] of Byte;

const
A : TArray = (
1, 2, 1, 2, 1,3
);

function Compare(a, b: Byte): Integer;
begin
if a > b then
Compare := 1
else if a = b then
Compare := 0
else Compare := -1;
end;

function IsOk: Boolean;
var
i, x, y: Integer;
begin
i := 0;
repeat
inc(i);
if (i <= n - 2) then begin
x := Compare(A[i], A[i + 1]);
y := Compare(A[i + 1], A[i + 2]);
end;
until ((i > n - 2) or (x * y = 0) or (y = x));
isOk := (i > n - 2);
end;

begin
clrscr;
if IsOk then writeln('Sequence -- OK')
else writeln('Sequence -- BAD');
readln;
end.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(klem4 @ 5.11.2006 10:57) *

может я что не так понял конечно, вот таккой вариант пойдет ?

klem4, я правильно понимаю, что ты только проверяешь, является ли последовательность волнистой?
Вопрос задания стоит иначе..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Именно, я упустил видимо это ?

Цитата
надо из неё выделить самую большую волнистую подпоследовательность


?

Если да, то исправить мою програму - добавить 5 строчек ...


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 16:58
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name