Наибольшая возрастающая подпоследовательность

@laconic · Регистрация: 05.11.2012

Author24 — интернет-сервис помощи студентам

Delphi

program true2;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
const
  n=5;
  plusinf=88;
  minusinf=-88;
 
type
 
  Original = array [0..n] of shortint;
  New = array [0..n,0..n] of shortint;
 
var
  i,j:shortint;
  A:Original;
  B:New;
 
begin randomize;
  for i:=1 to n do
    begin
    //  readln(a[i]);
      a[i]:=random(11);
      write(a[i],' ');
    end;
   writeln;writeln;
 
  for i:=0 to n do B[i,0]:=minusinf;
  for i:=0 to n do
    begin
      for j:=1 to n do B[i,j]:=plusinf;
    end;
 
  for i:=1 to n do
    for j:=1 to n do
       begin
         if (B[i-1,j-1]<A[i])and(A[i]<B[i-1,j]) then
           B[i,j]:=A[i]
         else
           B[i,j]:=B[i-1,j];
       end;
 
   for i:=0 to n do
    begin
     for j:=0 to n do write(B[i,j],' ');
     writeln;
    end;
 
   for i:=1 to n do
    begin
     if (B[n,i]<>88) then write(B[n,i],' ');
    end;
 
  readln;
end.

Код работает для положительных чисел массива.
Помогите пожалуйста, что надо исправить, чтобы программа работала с отрицательными числами.

@volvo · 06.11.2012, 10:54

Сообщение от laconic

Код работает для положительных чисел массива.

Точно работает? Увеличил N до 20, диапазон до Random(22). Запускаю, вижу:

4 0 1 7 9 4 12 11 3 3 2 0 6 3 20 14 21 16 10 21

-88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 4 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 7 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 7 9 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 4 9 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 4 9 12 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 4 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 3 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 3 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 6 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 3 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 3 11 20 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 3 11 14 88 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 3 11 14 21 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 3 11 14 16 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 3 10 14 16 88 88 88 88 88 88 88 88 88 88 88 88 88
-88 0 1 2 3 10 14 16 21 88 88 88 88 88 88 88 88 88 88 88 88
0 1 2 3 10 14 16 21

Это что за бред в результате? Где эта подпоследовательность присутствует в исходной? После 10 в исходной последовательности идет только 21, при любой трактовке условия в результате после 10 не может быть ничего кроме 21. Откуда взялись ещё 14 и 16? Почему программа их переместила? Что-то у тебя не так работает... Проверяй.

P.S. Вот поиск наибольшей возрастающей подпоследовательности на Паскале: https://www.cyberforum.ru/pasc... ost1281179 , тестируй.

@Any0019 · 10.11.2012, 16:58

Знаешь, здесь можно пойти немного другим путем, здесь можно сделать так (напишу просто алгоритм, а прогу уже сам сделай):
1)Заполняешь массив произвольными эл-ми;
2)Берешь за некоторую переменную n--> длинну массива
3)Смотришь для n эл-ов есть ли последовательность if есть токая последовательность, то выводишь её на экран
else 4)Берешь n-1 и смотришь строки от 1 до n-1 и от 2 до n если хотя бы одна из них - последовательность, то выводишь её на экран и т.д., пока n не станет равное 1 (продолжаешь действие исключительно, если для n большего чем нынешнее на единицу последовательностей нет)
-
-
-
А проверка осуществляется за счет a[n]>a[n-1]>a[n-2]>...>a[1] (в таком виде)

laconic, это мое предложение того, как написать эту программу (на мой взгляд такой алгоритм более оптимален) --> цикл(цикл())
причем только один "цикл в цикле" будет вполне достаточно)))

Добавлено через 6 минут
P.S. Проверку наличия последовательностей сделай через цикл

Delphi

 z:=1;
 For x:= 2 to n do
 Begin
  if a[x]>a[x-1] then 
  Begin
   z:=z+1;
   Continue;
  end
  else break;     
 end;
 if z=n then "Я не буду дальше писать в виде проги (вообщем дальше ты выводишь последовательность на экран, думаю с этим ты и сам справишься)"

Добавлено через 18 минут
Я написал тебе лишь кусок цикла, который тебе нужно еще будет самому чуть-чуть подстроить)

@volvo Супер-модератор 32835 / 21172 / 8148 Регистрация: 22.10.2011 Сообщений: 36,431 Записей в блоге: 8
	06.11.2012, 10:54	2
	Сообщение от laconic Код работает для положительных чисел массива. Точно работает? Увеличил N до 20, диапазон до Random(22). Запускаю, вижу: 4 0 1 7 9 4 12 11 3 3 2 0 6 3 20 14 21 16 10 21 -88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 4 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 7 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 7 9 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 4 9 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 4 9 12 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 4 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 3 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 3 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 9 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 6 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 3 11 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 3 11 20 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 3 11 14 88 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 3 11 14 21 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 3 11 14 16 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 3 10 14 16 88 88 88 88 88 88 88 88 88 88 88 88 88 -88 0 1 2 3 10 14 16 21 88 88 88 88 88 88 88 88 88 88 88 88 0 1 2 3 10 14 16 21 Это что за бред в результате? Где эта подпоследовательность присутствует в исходной? После 10 в исходной последовательности идет только 21, при любой трактовке условия в результате после 10 не может быть ничего кроме 21. Откуда взялись ещё 14 и 16? Почему программа их переместила? Что-то у тебя не так работает... Проверяй. P.S. Вот поиск наибольшей возрастающей подпоследовательности на Паскале: https://www.cyberforum.ru/pasc... ost1281179 , тестируй. 0

	10.11.2012, 16:58