Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

задача на динамическое программирование

44K
31 марта 2009 года
Римма
9 / / 31.03.2009
Надо разработать алгоритм, находящий наибольшую возрастающую подпоследовательность данной последовательности из n чисел. Допускается, чтобы алгоритм работал за время порядка n^2 (но желательно за n*logn);)

Большое спасибо))
311
04 апреля 2009 года
plastictown
309 / / 08.01.2006
Цитата: Римма

Надо разработать алгоритм, находящий наибольшую возрастающую подпоследовательность данной последовательности из n чисел. Допускается, чтобы алгоритм работал за время порядка n^2 (но желательно за n*logn);)

Большое спасибо))



Вы сами пытались что-либо сделать? Язык нужно угадывать?

44K
04 апреля 2009 года
Римма
9 / / 31.03.2009
ой...:confused: в Delphi :)
я пыталась, только не работает. вот код
program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils;
const n=3;
var i,k,n1,j,s:integer; //k-максимальная длина возрастающей
//подпоследовательности
x,u : array [1..n] of integer; //u - минимальный из последних членов
//возрастающих подпоследовательностей длины i
begin
for i:=1 to n do
readln(x);

n1 := 1; k := 1; u[1] := x[1];
while n1 <> n do
begin
n1 := n1 + 1;
//////// поиск
i:=0; j:=k+1;
{u < x[n1] <= u[j], j > i}
while (j - i) <> 1 do
begin
s := i + (j-i) div 2; {i < s < j}
if u >= x[n1] then j := s
else {u < x[n1]}
i := s;
end; {u < x[n1] <= u[j], j-i = 1}
{i - наибольшее из тех чисел отрезка 1..k, для кото-
рых u < x[n1]; если таких нет, то i=0 }
///////////
if i = k then
begin
k := k + 1;
u[k+1] := x[n1];
end
else {i < k, u < x[n1] <= u[i+1] }
u[i+1] := x[n1];
end;

for i:=1 to n do
writeln (u);
readln;
end.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог