Версия для печати темы

Автор: Ольга 8.05.2007 14:58

Помогите решить, пожалуйста, такую задачу:

Задается натуральное число N и последовательность a1, …, aN из N целых чисел.
Мы можем вычеркнуть из этой последовательности какие-то элементы и получить строго возрастающую последовательность.
Требуется найти количество строго возрастающих последовательностей максимальной длины, которые мы можем получить вычеркиванием каких-то элементов из введенной последовательности.

Заранее, спасибо. Оля

Автор: Ольга 10.05.2007 12:36

Хоть кто-нибудь откликнитесь, пожалуйста, на эту задачу. Помогите решить!!!!!

Автор: Lapp 10.05.2007 12:51

Нет проблем .
Оля, а можно тебя попросить?.. Я вот выложу код без комментариев, а ты, если можно, объясни, как он работает. Ну, чтобы была реальная польза от списывания.. Идет?..
Если будут вопросы по отдельным моментам - ответим, будь уверена.

Вот код:

{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