ZADATAK 3 - PODNIZ - 80 bodova

TEST PODACI (skraćeni prikaz)


	Broj M		Broj N		Rješenje	Broj bodova
Test 1	3		4		2		4
Test 2	10		15		6		5
Test 3	20		30		15		7
Test 4	50		100		34		9
Test 5	200		300		109		11
Test 6	1000		1200		435		12
Test 7	2000		2500		790		15
Test 8	3000		3000		82		17

OPIS ALGORITMA

Imamo 2 niza znakova : niz a, duljine m i niz b duljine n. Tražimo duljinu maksimalnog zajedničkog podniza ne nužno uzastopnih elemenata.
Označimo s a[[x]] x-ti element u nizu a, isto tako i b[[x]], x-ti element u nizu b.
Zatim, označimo s a[x] prvih x elemenata niza a i s b[x] prvih x elemenata niza b.
I, na kraju, označimo s t[x,y] duljinu maksimalnog zajedničkog podniza (ne nužno uzastopnih elemenata) od a[x] i b[y] (prvih x elemenata niza a i prvih y elemenata niza b).
Traženi broj iz zadatka je, znači, t[m,n].
Primijetimo slijedeću stvar, t[x,y] moguće je definirati rekurzivno na slijedeći način.
Imamo dva slučaja :
1. a[[x]] = b[[y]]
U tom slučaju je t[x,y] = t[x - 1,y - 1] + 1, što je očito.
2. a[[x]] <> b[[y]]
U tom slučaju je t[x,y] = max š t[x - 1,y],t[x,y - 1] ć, što je malo manje očito, ali je na sreću i dalje očito.
Još samo stavimo da je t[1,1] = 1 ako je a[[1]] = b[[1]], a inače t[1,1] = 0, i to je to, možemo krenuti računati t[m,n].
Zamislimo jednu pravokutnu tablicu dimenzija m x n (u gornjem lijevom uglu je koordinata 1,1) koju dinamički popunjavamo iz gornjeg lijevog ugla, krenuvši udesno do kraja tog retka, i tako redom svaki slijedeći redak sve dok ne stignemo do koordinate (m,n) tj. dok ne popunimo cijelu tablicu.
Prilikom popunjavanja polja (x,y) u toj tablici samo se pitamo da li je a[[x]] = b[[y]] i ako je u to polje upisujemo broj koji se nalaze u gore lijevo dijagonalno susjednom polju uvećan za jedan.
Ako je a[[x]] <> b[[y]], onda u polje (x,y) upisujemo veći od slijedeća dva broja : lijevog susjednog i gornjeg susjednog.
Još moramo paziti na nulti redak i nulti stupac jer, da bi rekurzija ispravno funkcionirala, stavljamo t[x,0] = t[0,x] = 0, za svaki x.
Ako bi to na taj način implementirali u algoritam imali bi problema sa memorijom i alociranjem 30002 integer-a. Zato mudro primijetimo da nama zapravo ne treba cijela tablica nego samo tekući redak i onaj redak iznad tekućeg, jer se brojevi kojima popunjavamo tekući redak baziraju na prethodno izračunatim brojevima iz samo ta dva retka, i problemi sa memorijom su iza nas, barem što se tiče ovog zadatka.

PODNIZ.PAS

program podniz;
const
  MAX_DULJINA = 3000;
var
  m,n : integer;
  prvi_niz,drugi_niz : array [1..MAX_DULJINA] of char;

procedure ucitaj;
var
  i : integer;
  f : text;

begin
  assign(f,'PODNIZ.DAT');
  reset(f);

  readln(f,m);
  for i := 1 to m do
    readln(f,prvi_niz[i]);

  readln(f,n);
  for i := 1 to n do
    readln(f,drugi_niz[i]);

  close(f);
end;

procedure rijesi;
var
  i,j : integer;
  previous_row,current_row : array [0..MAX_DULJINA] of integer;

function max(prvi_broj,drugi_broj : integer) : integer;
begin
  if prvi_broj > drugi_broj then
    max := prvi_broj
  else
    max := drugi_broj;
end;

begin
  for i := 0 to n do
    previous_row[i] := 0;
  current_row[0] := 0;

  for i := 1 to m do
    begin
      for j := 1 to n do
        if prvi_niz[i] = drugi_niz[j] then
          current_row[j] := 1 + previous_row[j - 1]
        else
          current_row[j] := max(previous_row[j],current_row[j - 1]);

      for j := 1 to n do
        previous_row[j] := current_row[j];
    end;

  writeln;
  writeln('Duljina najduzeg podniza = ',current_row[n]);
end;

begin
  ucitaj;
  rijesi;
end.

PODNIZ.C

#include <stdio.h>
#include <stdlib.h>

#define MAX_DULJINA 3000

int m,n;
char prvi_niz[MAX_DULJINA],drugi_niz[MAX_DULJINA];

void ucitaj(void)
{
  int i;
  FILE *fp;

  fp = fopen("PODNIZ.DAT","rt");

  fscanf(fp,"%d\n",&m);

  for (i = 0;i < m;++i)
    fscanf(fp,"%c\n",&prvi_niz[i]);

  fscanf(fp,"%d\n",&n);

 for (i = 0;i < n;++i)
    fscanf(fp,"%c\n",&drugi_niz[i]);

  fclose(fp);
}

void rijesi(void)
{
  int i,j;
  int previous_row[MAX_DULJINA + 1],current_row[MAX_DULJINA + 1];

  for (i = 0;i <= n;++i)
    previous_row[i] = 0;
  current_row[0] = 0;

  for (i = 0;i < m;++i)
  {
    for (j = 0;j < n;++j)
      if (prvi_niz[i] == drugi_niz[j])
        current_row[j + 1] = 1 + previous_row[j];
      else
        current_row[j + 1] = max(previous_row[j + 1],current_row[j]);

    for (j = 1;j <= n;++j)
      previous_row[j] = current_row[j];
  }

  printf("\nDuljina najduzeg podniza = %d\n",current_row[n]);
}

int main(void)
{
  ucitaj();
  rijesi();

  return 0;
}