Задается натуральное число N и последовательность a1, …, aN из N целых чисел. Мы можем вычеркнуть из этой последовательности какие-то элементы и получить строго возрастающую последовательность. Требуется найти количество строго возрастающих последовательностей максимальной длины, которые мы можем получить вычеркиванием каких-то элементов из введенной последовательности.
Заранее, спасибо. Оля
Ольга
10.05.2007 12:36
Хоть кто-нибудь откликнитесь, пожалуйста, на эту задачу. Помогите решить!!!!!
Lapp
10.05.2007 12:51
Цитата(Ольга @ 10.05.2007 9:36)
откликнитесь, пожалуйста, на эту задачу. Помогите решить!!!!!
Нет проблем . Оля, а можно тебя попросить?.. Я вот выложу код без комментариев, а ты, если можно, объясни, как он работает. Ну, чтобы была реальная польза от списывания.. Идет?.. Если будут вопросы по отдельным моментам - ответим, будь уверена.
Вот код:
{Quantity of Max Length Strictly Increasing Subchains} {by Lapp for Olga} const n=8;
var a,e:array[1..n]of integer; i,j,k,l,m,x:integer; Gr:boolean;
begin //Randomize; for i:=1 to n do begin a[i]:=Random(n); e[i]:=0; Write(a[i]:5) end; WriteLn; m:=1; k:=1; repeat i:=1; while e[i]=1 do if i<n then begin e[i]:=0; Inc(i) end else begin WriteLn('Max Length is ',m,', total of ',k); ReadLn; Exit end; e[i]:=1; l:=1; Gr:=true; x:=i; for j:=i+1 to n do if e[j]=1 then begin Inc(l); if a[x]>=a[j] then Gr:=false else x:=j end; if Gr then if l>m then begin m:=l; k:=1 end else if l=m then Inc(k) until false end.
Добавлено через 2 мин. Да, хочу оговориться, что я считал разными последовательности, составленные из одинаковых чисел, стоящих на разных местах. Иначе говоря, я считал количество способов вычеркивания. Условие можно понимать по-разному, поэтому я счел необходимым привести это уточнение.
Ольга
10.05.2007 15:13
Спасибо большое за реальную помощь. Я программу опробовала и попробую объяснить (может и не все правильно), как она работает. Последовательность заполняется случайными числами. m - максимальное кол-во чисел последовательности к- количество последовательностей Далее идет цикл с постусловием. Идет сравнение последующего числа с предыдущим. Выводится на печать "максимальная последовательность из __чисел и количество возможных последовательностей. А далее я эту часть программы я затрудняюсь объяснить:
e[i]:=1; l:=1; Gr:=true; x:=i; for j:=i+1 to n do if e[j]=1 then begin Inc(l); if a[x]>=a[j] then Gr:=false else x:=j end; if Gr then if l>m then begin m:=l; k:=1 end else if l=m then Inc(k) until false
Если Вы можете, то поясните, пожалуйста.
М
Ольга, при публикации программного текста обязательно используй теги! Lapp
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.