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

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

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

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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
1
2
3
4
5
6
7
8
9
10
11
 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 минут
Я написал тебе лишь кусок цикла, который тебе нужно еще будет самому чуть-чуть подстроить)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .