Максимальная неубывающая последовательность

[Люсь]

Задача:

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

Какие будут идеи?

Автор рекомендует студентам включить эврику для решения. Предлагаются языки Дельфи, ОбъектПаскаль и просто Паскаль, не по наслышке знакома только с последним, но думаю, может и не нужны будут всякие объектно-ориентированные прибамбасы?

[Dimka]

Люсь, а у тебя какие будут идеи?

Меня смущают фразы "максимальной длины" и "включить эврику" - без них решение вырисовывается даже раньше, чем дочитываешь задание.

P.S. Давай в начале без всяких Паскалей обычным русским языком.

[Петр_Иванович]

А "неубывающую" - это возрастающую последовательность или что-то другое о_О?

[Люсь]

Dimka, идей нет. Это почти программирование игры. Я такое никогда не делала. Не знаю, какое тебе решение вырисовывается, поделись )) Но мне в голову не пришло ничего лучше, чем исходную последовательность засунуть в массив, а потом перебирать его максимум n^n-1 раз, причём, куда результат длины засунуть? Опять в массив неопределенной длины. Как запомнить полученную последовательность, не будучи уверенным, что раньше или позже не было последовательности лучше по результатам? Не знаю! Может быть, здесь массивы вообще не подходят. Тогда что? И как?

Петр_Иванович, ну или неубывающую, т.е. такую, чтоб выполнялось условие:

Код:

 элемент a[i] > =  a[i-1]

[Люсь]

Хм, если б там не было бы слов "максимальной длины" - то и проблем бы никаких не было )))
Но надо найти такую оптимальную "неубывающую" последовательность путём удаления некоторых элементов, причём, насколько я понимаю, это мог бы быть и такой элемент, который бы подошёл по условию для построения очередной новой последовательности, чтобы длина этой последовательности оказалась максимальной по сравнению со всеми другими вариантами такого перебора ))

М-м-м, не уверена, что я понятно написала.
Например, исходная последовательность: 2 3 5 8 2 0 6 3 4 5
Самый прямой вариант (4 элемента) : 2 3 5 8 * * * * * *
Но есть вариант подлиннее (5 элементов) : 2 * * * 2 * * 3 4 5

Ну и как найти самый длинный вариант?

[Dimka]

Люсь, сначала ответь на такой вопрос. Каким образом в математике определяется, что функция возрастает/убывает в какой-то точке?

Затем подумай, как правильный ответ на этот вопрос применить к дискретным последовательностям (нужно будет вспомнить определение).

[Люсь]

Хм, интересно! Но откуда мне знать, что именно об экстремуме говорится в задаче? И причём тут тогда эвристика?

Я думаю, что всё таки так, как я поняла задание, более правильно. Почему нет?

[Dimka]

Люсь, в экстремумах функция не убывает и не возрастает А я спрашиваю, как определить: возрастает она, убывает, или находится в экстремуме?

[Люсь]

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

[Sla]

смотри, а теперь расскажи словами

[Finch]

Люсь, Есть ли ограничения на длину первоначального ряда?

[Люсь]

Я уже говорила:

Код:

 элемент a[i] > =  a[i-1]

Ну по твоему рисунку получается, такая последовательность вплоть до точки экстремума.

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


Finch, по тексту задачи - нет. 

[Dimka]

Люсь, во-первых, ты сказала:

Я не понимаю, к чему ты клонишь.

Это станет видно, когда ты ответишь на вопросы.

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

Это не оправдание для недуманья Наоборот, способствует размышлениям


Кстати, я тут подумал, может преподаватель говорил не про "эврику", а про "эвристику"? Вот тогда всё становится понятно, и как раз тупой полный перебор - не то, что он желает видеть.

[Dimka]

Первая эвристика: искать самую большую (по величине) убывающую подпоследовательность и пытаться её уменьшить за счёт соседней наиболее короткой неубывающей подпоследовательности.

Код: (Text) JScript WSH

function sign(x)
{
        return x < 0 ? -1 : x > 0 ? 1 : 0;
}

function calculateSequenceDifferences(sequence)
{
        var differences = new Array();
        for(var index = 1; index < sequence.length; ++index)
        {
                var previousIndex = index - 1;
                var currentIndex = index;
                var previousItem = sequence[previousIndex];
                var currentItem = sequence[currentIndex];
                var differenceValue = currentItem - previousItem;
                var difference = new Object();
                difference.value = differenceValue;
                difference.startIndex = previousIndex;
                difference.stopIndex = currentIndex;
                differences.push(difference);
        }
        return differences;
}

function calculateMonotonousIntervals(differences)
{
        for(var index = 1; index < differences.length; ++index)
        {
                var previousIndex = index - 1;
                var currentIndex = index;
                var previousDifference = differences[previousIndex];
                var currentDifference = differences[currentIndex];
                if(sign(previousDifference.value) == sign(currentDifference.value))
                {
                        currentDifference.startIndex = previousDifference.startIndex;
                        currentDifference.value += previousDifference.value;
                        delete differences[previousIndex];
                }
        }
        var monotonousIntervals = new Array();
        for(var index in differences)
        {
                var monotonousInterval = differences[index];
                monotonousIntervals.push(monotonousInterval);
        }
        return monotonousIntervals;
}

function detectIndexOfStrongestDecreasingMonotonousInterval(monotonousIntervals)
{
        var indexOfStrongestDecreasingMonotonousInterval = 0;
        var strongestDecrease = monotonousIntervals[indexOfStrongestDecreasingMonotonousInterval];
        for(var index = 0; index < monotonousIntervals.length; ++index)
        {
                var currentIndex = index;
                var currentDifference = monotonousIntervals[currentIndex];
                if(currentDifference.value < strongestDecrease.value)
                {
                        indexOfStrongestDecreasingMonotonousInterval = currentIndex;
                        strongestDecrease = monotonousIntervals[indexOfStrongestDecreasingMonotonousInterval];
                }
        }
        return strongestDecrease.value >= 0 ? NaN : indexOfStrongestDecreasingMonotonousInterval;
}

function detectItemWhoseRemovingCompressesWorstMonotonousInterval(monotonousIntervals, indexOfWorstMonotonousInterval)
{
        var indexOfPreviousMonotonousInterval = indexOfWorstMonotonousInterval - 1;
        var indexOfNextMonotonousInterval = indexOfWorstMonotonousInterval + 1;
        var currentMonotonousInterval = monotonousIntervals[indexOfWorstMonotonousInterval];
        var previousMonotonousInterval = indexOfPreviousMonotonousInterval < 0 ? null : monotonousIntervals[indexOfPreviousMonotonousInterval];
        var nextMonotonousInterval = indexOfNextMonotonousInterval >= monotonousIntervals.length ? null : monotonousIntervals[indexOfNextMonotonousInterval];
        if(previousMonotonousInterval == null)
        {
                return currentMonotonousInterval.startIndex;
        }
        else if(nextMonotonousInterval == null)
        {
                return currentMonotonousInterval.stopIndex;
        }
        else
        {
                var lengthOfPreviousMonotonousInterval = previousMonotonousInterval.stopIndex - previousMonotonousInterval.startIndex;
                var lengthOfNextMonotonousInterval = nextMonotonousInterval.stopIndex - nextMonotonousInterval.startIndex;
                if(lengthOfPreviousMonotonousInterval <= lengthOfNextMonotonousInterval)
                {
                        return currentMonotonousInterval.startIndex;
                }
                else
                {
                        return currentMonotonousInterval.stopIndex;
                }
        }
}

function selectLongestNondecreasingSequence(sequence)
{
        WScript.Echo(sequence.join(" "));

        if(sequence.length < 2)
        {
                return sequence;
        }
        var differences = calculateSequenceDifferences(sequence);
        var monotonousIntervals = calculateMonotonousIntervals(differences);
        var indexOfWorstMonotonousInterval = detectIndexOfStrongestDecreasingMonotonousInterval(monotonousIntervals);
        if(isNaN(indexOfWorstMonotonousInterval))
        {
                return sequence;
        }
        var indexOfExcessItem = detectItemWhoseRemovingCompressesWorstMonotonousInterval(monotonousIntervals, indexOfWorstMonotonousInterval);
        delete sequence[indexOfExcessItem];
        var newSequence = new Array();
        for(var index in sequence)
        {
                var item = sequence[index];
                newSequence.push(item);
        }
        return selectLongestNondecreasingSequence(newSequence);
}

WScript.Echo("Result: " + selectLongestNondecreasingSequence(new Array(2,3,5,8,2,0,6,3,4,5)).join(" "));

Результат ненадёжный. Удаляя малые неубывающие подпоследовательности, тем самым не всегда воздействуем на убывающую подпоследовательность - она даже может расти, соединяясь с другими убывающими подпоследовательностями.

Код:

Сервер сценариев Windows (Microsoft ®) версия 5.8
© Корпорация Майкрософт (Microsoft Corp.), 1996-2001. Все права защищены.

2 3 5 8 2 0 6 3 4 5
2 3 5 8 2 6 3 4 5
2 3 5 8 6 3 4 5
2 3 5 8 6 4 5
2 3 5 8 6 5
2 3 5 8 6
2 3 5 8
Result: 2 3 5 8

[Dimka]

Вторая эвристика: искать самую малую (по величине) убывающую подпоследовательность и пытаться её уменьшить за счёт соседней наиболее короткой неубывающей подпоследовательности.

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

Код: (Text) JScript WSH

function sign(x)
{
        return x < 0 ? -1 : x > 0 ? 1 : 0;
}

function calculateSequenceDifferences(sequence)
{
        var differences = new Array();
        for(var index = 1; index < sequence.length; ++index)
        {
                var previousIndex = index - 1;
                var currentIndex = index;
                var previousItem = sequence[previousIndex];
                var currentItem = sequence[currentIndex];
                var differenceValue = currentItem - previousItem;
                var difference = new Object();
                difference.value = differenceValue;
                difference.startIndex = previousIndex;
                difference.stopIndex = currentIndex;
                differences.push(difference);
        }
        return differences;
}

function calculateMonotonousIntervals(differences)
{
        for(var index = 1; index < differences.length; ++index)
        {
                var previousIndex = index - 1;
                var currentIndex = index;
                var previousDifference = differences[previousIndex];
                var currentDifference = differences[currentIndex];
                if(sign(previousDifference.value) == sign(currentDifference.value))
                {
                        currentDifference.startIndex = previousDifference.startIndex;
                        currentDifference.value += previousDifference.value;
                        delete differences[previousIndex];
                }
        }
        var monotonousIntervals = new Array();
        for(var index in differences)
        {
                var monotonousInterval = differences[index];
                monotonousIntervals.push(monotonousInterval);
        }
        return monotonousIntervals;
}

function detectIndexOfWeakerDecreasingMonotonousInterval(monotonousIntervals)
{
        var indexOfWeakerDecreasingMonotonousInterval = NaN, weakerDecrease = null;
        for(var index = 0; index < monotonousIntervals.length; ++index)
        {
                var currentIndex = index;
                var currentDifference = monotonousIntervals[currentIndex];
                if(currentDifference.value < 0)
                {
                        if(isNaN(indexOfWeakerDecreasingMonotonousInterval))
                        {
                                indexOfWeakerDecreasingMonotonousInterval = currentIndex;
                                weakerDecrease = currentDifference;
                        }
                        else if(currentDifference.value > weakerDecrease.value)
                        {
                                indexOfWeakerDecreasingMonotonousInterval = currentIndex;
                                weakerDecrease = currentDifference;
                        }
                }
        }
        return weakerDecrease == null ? NaN : indexOfWeakerDecreasingMonotonousInterval;
}

function detectItemWhoseRemovingCompressesWorstMonotonousInterval(monotonousIntervals, indexOfWorstMonotonousInterval)
{
        var indexOfPreviousMonotonousInterval = indexOfWorstMonotonousInterval - 1;
        var indexOfNextMonotonousInterval = indexOfWorstMonotonousInterval + 1;
        var currentMonotonousInterval = monotonousIntervals[indexOfWorstMonotonousInterval];
        var previousMonotonousInterval = indexOfPreviousMonotonousInterval < 0 ? null : monotonousIntervals[indexOfPreviousMonotonousInterval];
        var nextMonotonousInterval = indexOfNextMonotonousInterval >= monotonousIntervals.length ? null : monotonousIntervals[indexOfNextMonotonousInterval];
        if(previousMonotonousInterval == null)
        {
                return currentMonotonousInterval.startIndex;
        }
        else if(nextMonotonousInterval == null)
        {
                return currentMonotonousInterval.stopIndex;
        }
        else
        {
                var lengthOfPreviousMonotonousInterval = previousMonotonousInterval.stopIndex - previousMonotonousInterval.startIndex;
                var lengthOfNextMonotonousInterval = nextMonotonousInterval.stopIndex - nextMonotonousInterval.startIndex;
                if(lengthOfPreviousMonotonousInterval <= lengthOfNextMonotonousInterval)
                {
                        return currentMonotonousInterval.startIndex;
                }
                else
                {
                        return currentMonotonousInterval.stopIndex;
                }
        }
}

function selectLongestNondecreasingSequence(sequence)
{
        WScript.Echo(sequence.join(" "));

        if(sequence.length < 2)
        {
                return sequence;
        }
        var differences = calculateSequenceDifferences(sequence);
        var monotonousIntervals = calculateMonotonousIntervals(differences);
        var indexOfWorstMonotonousInterval = detectIndexOfWeakerDecreasingMonotonousInterval(monotonousIntervals);
        if(isNaN(indexOfWorstMonotonousInterval))
        {
                return sequence;
        }
        var indexOfExcessItem = detectItemWhoseRemovingCompressesWorstMonotonousInterval(monotonousIntervals, indexOfWorstMonotonousInterval);
        delete sequence[indexOfExcessItem];
        var newSequence = new Array();
        for(var index in sequence)
        {
                var item = sequence[index];
                newSequence.push(item);
        }
        return selectLongestNondecreasingSequence(newSequence);
}

WScript.Echo("Result: " + selectLongestNondecreasingSequence(new Array(2,3,5,8,2,0,6,3,4,5)).join(" "));

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

Код:

Сервер сценариев Windows (Microsoft ®) версия 5.8
© Корпорация Майкрософт (Microsoft Corp.), 1996-2001. Все права защищены.

2 3 5 8 2 0 6 3 4 5
2 3 5 8 2 0 3 4 5
2 3 5 2 0 3 4 5
2 3 2 0 3 4 5
2 2 0 3 4 5
2 0 3 4 5
0 3 4 5
Result: 0 3 4 5

[Люсь]

Dimka, наверное эвристика, я не отсканировала первую страницу, где было написано про эвристику, так что точно воспроизвести не могла, но посчитала, что Эврика - это типа Озарение! Ну чтоб не громозкое, а элегантное решение )

ну лана, чо ты сразу решение выдал )) Я б подумала )) Просто я имела в виду, чтоб когда я прихожу - были ответы, а не пустой топик, а то так неинтересно )

В коде поразбираюсь попозже, но всё таки не пойму, что конкретно вы имели в виду?
И почему не может быть результирующего варианта, как у меня?

Но есть вариант подлиннее (5 элементов) : 2 * * * 2 * * 3 4 5

Или это такие вот принципы эвристики?

[Dimka]

ну лана, чо ты сразу решение выдал )) Я б подумала )) Просто я имела в виду, чтоб когда я прихожу - были ответы, а не пустой топик, а то так неинтересно )

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

И почему не может быть результирующего варианта, как у меня?

А что лично ты для этого сделала? Это ж твоя задача.

[Вад]

Сдаётся мне, под эвристикой тут подразумевалось динамическое программирование - этим способом задача хорошо разбивается на подзадачи и решается. Если в лоб - то за n*log(n) по времени и квадратичные расходы по памяти (которые, впрочем, несложно превратить в линейные).

Сначала я думал, что можно как-нибудь срезать, построив дерево поиска, но что-то не получается

[Finch]

Люсь прости что запоздал. Смог посвятить этому время только вчера вечером. Решение на С++. Полный перебор всех последовательностей. С срезанием заведомо ложных ветвей.

Код: (C++)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXELEMENT 100

int main() {
        int arr[MAXELEMENT];
        srand(time(0));
        for(int i=0; i<MAXELEMENT; i++) arr[i]=rand() % 20;
        int tree[MAXELEMENT];
        int bigTree[MAXELEMENT];
        int lenBigTree = 0;
        int beg=1;              //Местоположение в tree
        tree[0]=0;
        printf("Исходный ряд :");
        for(int i=0; i<MAXELEMENT; i++) printf("%d ",arr[i]);
        printf("\n");
        bool stat=true;
        tree[beg] = tree[beg-1]+1;
        while (stat)
        {

                while ((tree[beg] < MAXELEMENT) && (beg+MAXELEMENT-tree[beg] > lenBigTree)) {
                        if ((beg == 0) || (arr[tree[beg]] >= arr[tree[beg-1]])) {
                                beg++;
                                tree[beg] = tree[beg-1]+1;
                        }
                        else {
                                tree[beg]++;
                        }
                }
                beg--;
                if ((beg == 0) && !(beg+MAXELEMENT-tree[beg] > lenBigTree)) stat=false;
                if (beg >= 0) {
                        if (beg>lenBigTree) {
                                for(int i=0; i <= beg; i++) bigTree[i] = tree[i];
                                lenBigTree =beg;
                        }
         tree[beg]++;
                }
                else stat=false;
        }
        printf("После обработки :");
        for(int i=0; i<=lenBigTree; i++) printf("%d ",arr[bigTree[i]]);
        printf("\n");
        return 0;
}

[Люсь]

Finch, никто никуда не опоздал
Спасибо, попробую разобраться.

[Dimka]

Полный перебор по дереву для меня как-то более привлекательно делать рекурсией.

Вариант без отсечения ветвей и оптимизации.

Код: (Ruby)

def selectLongestNondecreasingSequence(sequence)
        def nondecreasingSubsequences(sequence)
                return [ sequence ] if sequence.length < 2
                currentItem = sequence.first
                sequenceTail = sequence.slice 1..-1
                subsequences = nondecreasingSubsequences sequenceTail
                newSubsequences = []
                for subsequence in subsequences
                        if subsequence.first >= currentItem then
                                newSubsequence = subsequence.clone
                                newSubsequence.unshift currentItem
                                newSubsequences.push newSubsequence
                        end
                end
                subsequences.push [ currentItem ]
                subsequences = subsequences.concat newSubsequences
                return subsequences
        end
        subsequences = nondecreasingSubsequences sequence
        bestSubsequence = subsequences.first
        for subsequence in subsequences
                bestSubsequence = subsequence if subsequence.length > bestSubsequence.length
        end
        return bestSubsequence
end
longestNondecreasingSequence = selectLongestNondecreasingSequence [ 2, 3, 5, 8, 2, 0, 6, 3, 4, 5 ]
message = longestNondecreasingSequence.join ", "
puts "Result: " + message

Расход памяти нехороший.

Теперь в другом месте можно порассуждать про императивный и декларативный стиль

[Finch]

Dimka, А где Люся найдет в стандартной поставке Windows, Рубин, чтобы проверить твой код?

[Sla]

Finch, а это не обязательно
главное понять что человек делает.

[Dimka]

Finch, а зачем мой код "проверять"? Я его писал не для того, чтобы запускать, а для того, чтобы покороче выразить мысль

[Finch]

Sla, Dimka, Чтоб мне понять, нужно две веши. Хотя бы приблизительно знать. Что я должен понять. И знать хоть чуть чуть синтаксис языка. Тот код, что Dimka привел. Я то смогу с пивом понять. А вот человек, который даже не слышал об Руби, будет считать это издевательством. А тем более такие классные наименования subsequence subsequences. Разница в одну букву. Да и в самом конце. Читабельность кода это очень сильно повышает.

[Dimka]

А вот человек, который даже не слышал об Руби, будет считать это издевательством.

Да не вопрос, пусть считает. Вообще говоря, у меня были несколько иные цели, нежели выдать готовое решение. Готового решения я не дам, о чём сказал Люсе в аське ещё в день создания темы.

А тем более такие классные наименования subsequence subsequences. Разница в одну букву. Да и в самом конце. Читабельность кода это очень сильно повышает.

Вообще offtop, но тема интересная Предлагаю в моём коде поменять идентификаторы так, как ты для себя считаешь оптимальным.

[Вад]

Кому интересно готовое решение? Готовое решение есть в гугле и даже в википедии. И не одно, а целых 4, на любой вкус по производительности и памяти.

[Люсь]

я в шоке ваще.

[Люсь]

У меня нет желания высказывать кому-то какие-то претензии. Я просто начинаю понимать теперь, о чём говорят в модераторском разделе по поводу халявщиков.

Я не просила написать программу!!!
Если у вас так много опыта - это не повод зазнаваться. А я пока только это и вижу. И именно, вижу издевательство! Причём не в том, что вы мне тут пишете программы на непонятных языках (которые я пока не разбирала, потому что мне нужен не код, а принцип решения!!!). А именно в отношении к автору вопроса.

Ещё раз - я в шоке!!! После такого возникает желание просто послать всех и больше никогда не задавать каких бы то ни было вопросов.

Я не знаю, может быть, вам показалось, что я во фразу "я хочу ответов побыстрее" вложила какую-то наглость, но я посещаю интернет 1 раз в неделю!!! Больше не имею возможности!!! И очень хотелось получить какие-то идеи, до которых я сама не дошла в день, когда я посещаю интернет, чтобы в течении недели могла размышлять и что-то накодить.
А вы!!! Пи**ец, у меня только такое слово.

Всё это время вашими решениями не пользовалась. Пыталась пойти по пути двоичного поиска, как меня озарением одарил Альф - он буквально 2 строчки сказал, а у меня появились идеи. Но пока тоже не получилось, потому что в процессе пришло понимание, что нужно решать в рекурсии по принципу дерева, но я такое не умею. В литературе пока тоже понять не могу, как деревья программировать.

А что вы хотели мне сказать со своими функциями и графиками функций - я так и не поняла. Хотите, чтобы поняла - объясните, как в школе объясняют новую тему.

ps: вы = Dimka. К остальным вроде претензий не имею.

[Dimka]

Люсь, у меня тоже есть претензия. За истекшее время я так и не увидел твоей РАБОТЫ над задачей. За неделю можно многое сделать и выложить, а также обозначить план действий на будущее. Поэтому результат закономерный - возникает устойчивое ощущение расхлябанности с твоей стороны.

P.S. Для меня "решение задачи" и "поделиться эмоциями о том, какая у меня задача, как мне Alf советовал двоичные последовательности" - совершенно разные вещи. Последнее уместно в "Общении", а здесь неконструктивно. Потому что по существу вопроса с твоей стороны нет абсолютно ничего. И моё отношение изменится только тогда, когда я увижу результаты (пусть промежуточные) твоей работы: варианты, попытки и т.д. В виде алгоритмов, кода, блок-схем - чего угодно.