Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 06.06.2021, 23:39   #1
canadamoscow
Пользователь
 
Аватар для canadamoscow
 
Регистрация: 16.05.2020
Сообщений: 57
По умолчанию Неубывающая последовательность из чисел ряда

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

Входные данные: полседовательность N случайных чисел (1<=N<=100).
Выходные данные:
1-я строка содержит длину максимальной неубыващей последовательности.
2-я строка и далее - пример такой последовательности

Пример:
N = 13
12 59 4 21 36 18 27 79 34 45 47 34 93
7
4 21 27 34 45 47 93

Последний раз редактировалось canadamoscow; 06.06.2021 в 23:55.
canadamoscow вне форума Ответить с цитированием
Старый 06.06.2021, 23:40   #2
canadamoscow
Пользователь
 
Аватар для canadamoscow
 
Регистрация: 16.05.2020
Сообщений: 57
По умолчанию

Код:
begin
  //var a := Arr(12,59,4,21,36,18,27,79,34,45,47,34,93); var n := a.Println.Count;
  var n := ReadlnInteger('N =');
  var a := ArrRandom(n,1,1000); a.Println;
  var SizeNext := ArrFill(n, (0,0)); {item1 (size) - размер самого длинного ряда от текущего до конца,
  item2 (next) - индекс следующего элемента в наибольшем ряду}
  SizeNext[n-1] := (1,-1); //последний элемент один в ряду, индекс следующего отсутствует
  var (sizeMax, index) := (1, n-1); //индекс первого известного элемента длинного ряда
  
  for var i := n-2 downto 0 do begin //заполняем массив SizeNext
    var (size, next) := (0, -1);
    for var j := i+1 to n-1 do //ищем следующее наилучшее неубывающее число
       if (a[i] <= a[j]) and (SizeNext[j].Item1 > size) then
         (size, next) := (SizeNext[j].item1, j);
    SizeNext[i] := (size+1, next);
    if sizeMax <= size+1 then (sizeMax, index) := (size+1, i);
  end;

  sizeMax.Println;
  while index <> -1 do begin
     Print(a[index]); //вывод очередного элемента длинного ряда
     index := SizeNext[index].item2; //индекс слещующего элемента длинного ряда
  end;
end.
Так выглядит массив SizeNext с указанием чисел перед скобками исходного массива с одинаковым индексом.
12 59 4 21 36 18 27 79 34 45 47 34 93
12(7,3) 59(3,7) 4(7,3) 21(6,6) 36(4,9) 18(6,6) 27(5,8) 79(2,12) 34(4,9) 45(3,10) 47(2,12) 34(2,12) 93(1,-1)
7
4 21 27 34 45 47 93 или
12 21 27 34 45 47 93

Последний раз редактировалось canadamoscow; 06.06.2021 в 23:57.
canadamoscow вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Непрерывная неубывающая последовательность чисел (TurboPascal) VladKB1 Помощь студентам 17 13.06.2014 00:06
Дана непустая последовательность целых чисел. Найти: Сумму чисел, больших числа x и количество всех чётных чисел maksim97maksim Паскаль, Turbo Pascal, PascalABC.NET 1 09.04.2014 13:59
Дана последовательность целых чисел a1, a2, …an. Образовать новую последовательность, выбросив из исходной, те члены, которые равн Мария74 C++ Builder 2 04.12.2013 23:09
Дана непустая последовательность вещественных чисел, оканчивающаяся числом 1000. Последовательность является неубывающей. fanatloko Паскаль, Turbo Pascal, PascalABC.NET 1 23.06.2013 14:25
Дана последовательность вещественных чисел. каждая пара чисел задает границы отрезка. Найти количество целых чисел на отрезках 'studentka' Помощь студентам 6 30.11.2011 18:35