И еще одна задача:

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

Это сообщение отредактировал(а) ALEXANDRO - 9.11.2004, 18:46

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

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

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

Perchilla
Так цикл и есть один.

sergej.z
Посмотрю, есть ли в моём втором массиве оно или нет.

Цитата

Но КАК смотреть в очереди или массиве без цикла?

а зачем без цикла?
я вообще предлагал решение другой задачи, которая появилась недавно
в связи с этим предложение: для каждой задачи создавать отдельную тему

Придумал решение задачи Morpheus'а, вечером или завтра код будет. Описание алгоритма на полторы страницы
Хорошая задача, сегодня убил более часа под гневным взором начальника

Разбил ряд на два подряда, левый и магазин. В магазине уже просмотренная часть ряда. магазин все время старается передвинутся влево, иначе расширяется. При сдвиге смотрим какой ряд меньше, магазиный или левый, удаляем меньший. Удалённый подряд запоминаем в начале оставшегося(в смысле как аттрибут). При удалении подряда востанавливаем все уделённые им подряды. Тогда: из ряда всегда удаляется наименьший подряд; все удалённые подряды после удаления их "предка", востанавливаются, получая шанс остатся.

В коде будет понятно

Sardar Обычно в задачах по информатике решение простое.

А для тех кто си не знает можно алгоритм привести?

sergej.z
на PHP, думаю, лучше

php, perl

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

Код

<html> <body> <script language="javascript" type="text/javascript"> function processArray(rij, mi) { //здесь происходит работа  var tj=rij.length, i, j, rest;  while(mi>0) {    i=mi;    while(i<rij.length) { //Вверх по магазину      if(i<=0) return rij; //отсортированно      for(j=mi-1; j>=0 && rij[j].value>rij[i].value; j--); //Вниз по левому ряду      if(i==mi&&j==mi-1) { //расширим магазин        i=--mi;        if(debug) alert("Увеличим магазин: "+mi+", "+i);        continue;      }      else if(j>tj) break; //магазин раздвоился      tj=j; i++;    }    if(mi-++tj>i-mi) { //удалим из магазина      var rem=rij.slice(mi, i);      rij[mi-1].removed=rem;      for(var q=0, rest=[]; q<rem.length; q++) rest=rest.concat(rem[q].removed);      rij=rij.slice(0, mi).concat(rest, rij.slice(i, rij.length));      mi=mi-1;      if(debug) dumprij("Удалим магазинный ряд: ", rem);      if(debug) dumprij("Востановим элементы: ", rest);    } else { //удалим из левого ряда      var rem=rij.slice(tj, mi);      rij[mi].removed=rem;      for(var q=0, rest=[]; q<rem.length; q++) rest=rest.concat(rem[q].removed);      rij=rij.slice(0, tj).concat(rest, rij.slice(mi, rij.length));      mi-=rem.length;      if(debug) dumprij("Удалим левый ряд: ", rem);      if(debug) dumprij("Востановим элементы: ", rest);    }  }  return rij; } function dumprij(text, test) { //распечатка ряда чисел   var ret=[];   ret.length=test.length;   for(var i=0; i<test.length; i++) ret[i]=test[i]? test[i].value: "whoops: "+i;   alert(text+ret); } //тестируем var test=[15, 1,2, -1 ,3, 56, 57, 4,5,0]; for(var i=0; i<test.length; i++) { //обратим это дело в обьекты, так удобнее  test[i]={value:test[i], removed:[]}; } var debug=true; var beginlen=test.length; test=processArray(test, test.length-1); dumprij("Готово, убрали "+(beginlen-test.length)+" элементов: \n", test); </script> </body>

Код

Алгоритм. Мы должны получить очередь с элементами упорядоченных по возрастанию. Начнем с конца очереди, говоря "берём следующий элемент из ряда", мы берем предидущий, т.е. N-1, где N - текущий элемент. Уже просмотренные элементы, упорядоченные по возрастанию мы назовём магазином, в начале в магазине только 1 элемент - последний элемент из ряда. Следующий элемент в магазине это N+1, где N - текущий элемент. Если не понятно, то ряд поделен на два подряда - не просмотренные элементы и магазин, где магазин все время расширяется. Когда останется только один магазин работа алгоритма завершится. Не промстренные элементы будем также называть левым рядом. Визуально: |--------|+++|                     ^^ - текущий элемент и следуюххий элемент в магазине                   ^ - следующий элемент в ряде Берём первый элемент из магазина, сравниваем его с следующим элементом из ряда. Если элемент больше или равен, то расширяем магазин: |-----|+|  ->  |----|++| Если он меньше, то меняем их местами "в уме", повторяем процедуру пока элемент не остановится. |--------#*****|+++|         ^^ - сдвигаемый элемент и элементы большие сдвигаемого. Берем следующий элемент из магазина и делаем те же действия. Если элемент остановился на том же месте, то помечаем его как связанный с первым элементом - этакий сдвигаемый малый подряд. Повторяем процедуру для следующего элемента из магазина и так пока не кончится магазин. Если магазин закончился или очередной сдвигаемый элемент из магазина остановился ранее, то останавливаемся. Сравниваем длинну сдвинутых элементов из магазина и длинну подряда только что просмотренных элементов: |-------###**%***|++|             ^ - элемент из магазина остановившийся ранее, т.е. больше чем следующий элемент от него           ^ - передвинутые элементы левого ряда, длинна подряда равна 2        ^ - передвинутые элементы из магазина, длинна подряда равна 3 Удаляем подряд с наименьшей длинной. Как смотри ниже. На этом примере длина подряда левого ряда меньше(2), чем длинна подряда магазина, потому удаляем подряд левого ряда. Существует регистр удалённых подрядов:  элемент -> подряд При удалении мы заносим в этот регистр удалямеый подряд под: -> первым элементом оставшегодя магазинного ряда(левый подряд удалён) -> последним элементовом оставшегося левого подряда(магазинный подряд удалён) |-------###**%***|++|           ^ это подряд          ^ - этот элемент - ключ В JS реализации я сделал на обьектах, где удалённый ряд одно из свойств элемента. Пробегаемся по удалённому подряду, проверяем есть ли под его элементами удаленные ранее подряды. Если есть, то вставляем их на место удалённого подряда. Продолжим работу с первого магазинного элемента. Как видим очередь будет постоянно менятся, меньшие по длинне очереди будут удалятся. Но так как дальше возможна более длинная очередь, которая удалит предидущую, то необходимо востанавливать все изменения удлаяемой очереди, для этого мы ввели регистр.

Сначала построим для нашей исходной последовательности ориентированный граф.
Обозначим через V(i) число, стоящее на i-м месте в исходном списке (нумерация начинается с 1).
Пусть вершинам соответствуют позиции чисел в списке (вершина x_i соответствует
числу, стоящему в i-й позиции),
а дуга проведена от вершины x_i к вершине x_j
тогда и только тогда, когда число i<j и V(i) <= V(j).
Очевидно, в силу ассоциативности операции сравнения, данный граф бесконтурный
и отсортированная по возрастанию последовательность чисел максимальной
длины соответствует максимально длинному пути в этом графе.

Задача поиска пути максимальной длины в бесконтурном графе
решается с помощью разбиения вершин графа на слои, которое строится следующим
образом:
1. Выбираем в графе все источники (вершины, у которых нет входящих дуг)
и называем это множество вершин первым слоем.
2. Удаляем из графа вершины предыдущих слоев, у получившегося графа
ищем источники и называем их очередным слоем.
3. Повторяем пункт 2 пока вершин не останется.

Замечание 1. В бесконтурном графе всегда есть источники.

Замечание 2. При удалении из бесконтурного графа нескольких вершин со всеми
инцидентными дугами получившийся граф также является бесконтурным.

Замечание 3. Обозначим слои через S_1, S_2, ..., S_k.
Тогда выполнены свойства a) Между вершинами одного слоя нет дуг.
б) Для каждой вершины очередного слоя A найдется по крайней мере одна
вершина из предыдущего слоя B, такая, что в графе есть дуга из B в A.

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

Ясно, что все вершины пути максимальной длины должны попасть в разные слои,
поэтому слоев не меньше, чем длина максимального пути.
С другой стороны, можно построить путь, длина которого равна числу слоев.
Действительно, рассмотрим произвольную вершину A _последнего_ слоя.
В предпоследнем слое найдется вершина B, такая что в графе есть
дуга из B в A. Поднимаясь последовательно таким образом к первому
слою построим искомый максимальный путь.

Замечание 4. Алгоритм разбиение графа на слои имеет квадратичную сложность,
а поиск пути максимальной длины -- линейную, поэтому весь алгоритм
имеет квадратичную сложность.
Наивные переборные алгоритмы исходной задачи имеют
экспоненциальную сложность (с основанием около 1.5),
поэтому значения N выше 200 для них практически недостижимы.

Описанный алгоритм я реализовал на языке Smalltalk (VisualWorks).
Сначала добавим в стандартный класс SequenceableCollection
вспомогательный метод:


Затем создадим новый подкласс GraphSort класса Object
с двумя instance-методами:





Все, теперь идем в Workspace и тестируем:
list := #(10 30 20 90 70 60 70 80 330 230 560 120 990 340 )
sorter := GraphSort new.
r := sorter run: list.
В переменной r получили индексы
элементов максимальной подпоследовательности:
List (1 2 5 7 8 9 11 13)

Выведем для наглядности сами элементы:
r collect: [:i | list at: i]
Результат: List (10 30 70 70 80 330 560 990)

Теперь тестируем производительность на списках случайных чисел (64 bit Double):
list := (1 to: 100) collect: [:i | Random new next].
Core.Time millisecondsToRun: [r := sorter run: list. ]
Результат: 93

list := (1 to: 200) collect: [:i | Random new next].
Core.Time millisecondsToRun: [r := sorter run: list. ]
Результат: 1010

list := (1 to: 400) collect: [:i | Random new next].
Core.Time millisecondsToRun: [r := sorter run: list. ]
Результат: 8732

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

Чтобы привести программу к исходной постановке, нужно в методах "selectSources:"
и "run:" заменить нестрогое сравнение "<=" строгим "<".

кто-то может написать решение этой задачи на Java,а то 2 дня уже не могу с ней разобраться,пожалуйста.

Это то что есть,но из последовательности он берет элементы на шару,а не возрастающую последовательность  

Это сообщение отредактировал(а) monster89 - 24.5.2007, 07:51