9. cvičení - 27.11.2009

• informace k zadání nových domácích úloh
  • Cesta králem na šachovnici (délka)
  • Odstavcovač
  • Kontrola uzávorkování
  • Sokoban
• ukázka řešení domácí úlohy 2
• upozornění: téma a krátká specifikace zápočťáku do konce listopadu
• modulární programování - unit, interface, implementation
• dynamické programování
  • násobení mnoha matic - optimální uzávorkování matic pro minimalizaci počtu násobení prvků matic
    • ukázkové zdrojáky (doc. Pavel Töpfer) - rychle odspodu dynamicky, pomalu odshora rekurzivně
  • nejdelší rostoucí podposloupnost - ukázkový zdroják, viz níže
• inkrementální výpočty
  • spojitá podposloupnost celých čísel s největším součtem

program lis;
{
Nejdelsi rostouci podposloupnost,
aneb Longest Increasing Subsequence (LIS)
 
Mame posloupnost cisel A, chceme spocitat delku LIS v A.
 
Priklad: pro A = [ 6, 3, 6, 10, 8, 9, 10, 10, 4, 1, -1 ] vrati 5.
}
 
const
  MAX=100;
 
function delka_lis(var A : array of integer; delka : integer) : integer;
var
  { Q[i] - delka LIS koncici v A[i] }
  Q : array[0..MAX-1] of integer;
  max : integer;
  j, k : integer;
begin
  { inicializace prvku Q na 1 - jednoprvkove podposl. maji delku 1 }
  for k := 0 to delka-1 do
  begin
    Q[k] := 1;
  end;
  for k := 0 to delka-1 do
  begin
    { chceme delku nejdelsi LIS koncici v A[j], na kterou
      lze napojit A[k] }
    max := 0;
    for j := 0 to k-1 do
    begin
      if ((A[k] > A[j]) AND (Q[j] > max)) then
      begin
        max := Q[j];
      end;
    end;
    { LIS prodlouzime o aktualni prvek A[k] }
    Q[k] := max + 1;
  end;
  { pouze uz jen najdeme maximum v Q }
  for k := 0 to delka-1 do
  begin
    if (Q[k] > max) then
    begin
      max := Q[k];
    end;
  end;
  delka_lis := max;
end;
 
var
  posloupnost : array[0..MAX-1] of integer;
  i : integer;
  N : integer; {delka posloupnosti}
begin
  readln(N);
  if (N > MAX) then
  begin
    N := MAX;
    writeln('Pozor: bude zpracovano najvys ', MAX, ' prvku.');
  end;
  for i := 0 to N-1 do
  begin
    readln(posloupnost[i]);
  end;
  writeln(delka_lis(posloupnost, N));
end.