Wstęp do programowania / Ćwiczenia 3

To są zadania na wyszukiwanie binarne.

Zadanie 1 (Pierwsze wystąpienie x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Znajdź miejsce pierwszego wystąpienia x (lub 0 gdy nie ma żadnego x)

Rozwiązanie 1

function ZnajdźPierwsze(N,x:integer; A:array[1..N] of integer):integer;
//Tablica A posortowana niemalejąco; szukamy pierwszego wystąpienia x w A
var l,p,s : integer;
begin
  l:=1;
  p:=N;
  while l < p do begin
    s:=(l+p)div 2;
    if x > A[s] then l:=s+1;
    else p:=s;
  end;
  if A[l] = x then ZnajdzPierwsze:=l
  else ZnajdzPierwsze:=0;
end;

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Pytanko 1

Jaka będzie wartość A[l] w przypadku gdy x nie ma w tablicy A ?

Zadanie 2 (Ostatnie wystąpienie x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Znajdź miejsce ostatniego wystąpienia x (lub 0 gdy nie ma żadnego x)

Rozwiązanie 1

function ZnajdźOstatnie(N,x:integer; A:array[1..N] of integer):integer;
//Tablica A posortowana niemalejąco; szukamy ostatniego wystąpienia x w A
var l,p,s : integer;
begin
  l:=1;
  p:=N;
  while l < p do begin
    s:=(l+p+1)div 2;
    if x < A[s] then p:=s-1;
    else l:=s;
  end;
  if A[l] = x then ZnajdzOstatnie:=l
  else ZnajdźOstatnie:=0;
end;

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Pytanko 1

Jaka będzie wartość A[l] w przypadku gdy x nie ma w tablicy A ?

Zadanie 3 (Liczba wystąpień x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Wyznacz liczbę wystąpień x w tablicy A.

Wskazówka 1

Trzeba użyć wyszukiwania binarnego a nie liniowego.

Rozwiązanie 1

function LiczbaWystąpień(N,x:integer; A:array[1..N] of integer):integer;
//Tablica A posortowana niemalejąco; wyznaczamy liczbę wystąpień x w A
var p,l: integer;
begin
  l:= ZnajdźPierwsze(N,A,x);
  p:= ZnajdźPierwsze(N,A,x);
  if l <> 0 then LiczbaWystąpień:=p-l+1;
end;

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Zadanie 4 (Wartość równa indeksowi)

Dana jest posortowana rosnąco tablica A typu array[1..N] of integer. Sprawdź czy występuje w niej element o wartości równej swojemu indeksowi. Jeśli tak to wyznacz ten indeks, jeśli nie to funkcja ma dać wartość 0.

Wskazówka 1

Jeśli A[i] < i to też A[i-1] < i-1. I podobnie dla i-2, i-3...1.

Rozwiązanie 1

function Równy(N:integer; A:array[1..N] of integer):integer;
//Tablica A posortowana rosnąco; szukamy i, takiego że A[i]=i
var p,l,s: integer;
begin
  l:=1;
  p:=N;
  while l < p do begin
    s:=(l+p)div 2;
    if A[s] < s then l:=s+1;
    else p:=s;
  end;
  if (A[l]=l) then Równy:=l
  else Równy:=0;
end;

Dla tablic posortowanych niemalejąco to rozwiązanie nie działa.

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Zadanie 5 (Maksimum w ciągu bitonicznym)

Dana jest tablica A typu array[1..N] of integer, w której wartości ułożone są w ciąg bitoniczny (czyli istnieje 1 ≤ i ≤ N, takie że dla wszystkich k, takich że 1 ≤ k < i zachodzi A[k] < A[k+1] a dla wszystkich k, takich że i ≤ k < N zachodzi A[k] > A[k+1]). Znajdź maksimum w tym ciągu.

Wskazówka 1

Szukamy pierwszego elementu dla którego A[i] > A[i+1]. Trzeba uważać na przypadek gdy maksimum jest w A[N].

Rozwiązanie 1

function MaksBitoniczny(N:integer; A:array[1..N] of integer):integer;
//Tablica A zawiera ciąg bitoniczny; szukamy maksimum w tym ciągu
var p,l,s: integer;
begin
  if N=1 then MaksBitoniczny:=1 
  else 
    if A[N-1] < A[N] then MaksBitoniczny:=N 
    else begin
      l:=1;
      p:=N-1;
      while l < p do begin
        s:=(l+p)div 2;
        if A[s] < A[s+1] then l:=s+1;
        else p:=s;
      end;
      MaksBitoniczny:=l;
    end;   
end;

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Zadanie 6 (Pierwiastek z x)

Napisz program obliczający sufit z pierwiastka z x, dla xεN, x > 0 (oczywiście bez operacji pierwiastek).

Wskazówka 1

Najprostsze rozwiązanie jest liniowe.

Rozwiązanie 1

function SufitZPierwiastka1(x:integer):integer;
//Dla x > 0 wyznaczamy sufit z pierwiastka z x
var i: integer;
begin
  i:=1; 
  while x > i*i do i := i+1;
  SufitZPierwiastka1 := i;
end;

Koszt czasowy: liniowy względem N

Koszt pamięciowy: stały

Wskazówka 2

Oczywiście lepiej jest to zrobic binarnie. Szukamy takiej liczby całkowitej i z przedziału [1..x], że (i-1)*(i-1) < x ≤ i*i.

Rozwiązanie 2

function SufitZPierwiastka2(x:Real):integer;
//Dla x > 0 wyznaczamy sufit z pierwiastka z x
var l,p,s : integer;
begin
  l:=1;
  p:=x;
  while l < p do begin
    s:=(l+p)div 2;
    if x > s*s then l:=s+1;
    else p:=s;
  end;
  SufitZPierwiastka2:=l;
end;

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Inna wersja zadania

A jak znaleźć podłogę z pierwiastka z x ?

Wskazówka 3

Analogicznie jak w Rozwiązaniu 2.

Rozwiązanie 3

function PodłogaZPierwiastka(x:Real):integer;
//Dla x > 0 wyznaczamy podłogę z pierwiastka z x
var l,p,s : integer;
begin
  l:=1;
  p:=x;
  while l < p do begin
    s:=(l+p+1)div 2;
    if x < s*s then p:=s-1;
    else l:=s;
  end;
  PodłogaZPierwiastka:=l;
end;

Uwaga: porównaj różnice między Rozwiązaniami 2 i 3 oraz funkcjami ZnajdźPierwsze, ZnajdźOstatnie z Zadania 1 i 2.

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Zadanie 7 (BinPower)

Dla zadanych x,n > 0 wyznacz xⁿ (oczywiscie bez exp i ln).

Wskazówka 1

Oczywiście nie chodzi o to by pomnożyć x przez siebie n-1 razy.

Rozwiązanie 1

function BinPower(x,n:integer):integer;
// Dla x,n > 0 wyznaczamy x do potęgi n 
var z,y,i: integer;
begin
  z:=1;
  y:=x;
  i:=n;
  while i > 0 do begin
    if (i mod 2 = 1) then z:=z*y;
    y:=y*y;
    i:=i div 2;
  end;
  BinPower:=z;
end;

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Zadanie 8 (Najdłuższy podciąg niemalejący)

Dana jest tablica A typu array[1..N] of integer, N > 1. Należy obliczyć długość najdłuższego podciągu niemalejącego w A.

Wskazówka 1

Kluczowe jest użycie dodatkowej tablicy B rozmiaru N, w której pod indeksem i przechowuje się minimalną wartość kończącą podciąg niemalejący o długości i w dotychczas przejrzanej części tablicy A, od 1 do k. Żeby uwzględnić A[k+1] należy w tablicy B odnależć miejsce na A[k+1] (najlepiej binarnie).

Rozwiązanie 1

Zacznijmy od pomocniczej funkcji ZnajdźPierwszyWiększy(A:array[1..N] of integer; l,p,x:integer):integer, która w tablicy A, na odcinku od l do p, wyznacza indeks pierwszego elementu o wartości większej od x przy założeniu że A[p] > x.

function ZnajdźPierwszyWiększy(C:array[1..N] of integer; l,p,x:integer):integer;
//Tablica C jest posortowana niemalejąco na odcinku od l do p, zakładamy, że C[p] > x; 
//szukamy indeksu pierwszego elementu z lewej większego od x  
var s: integer;
begin
  while l < p do begin
    s:=(l+p+1)div 2;
    if x < C[s] then p:=s-1;
    else l:=s;
  end;
  if C[l] <= x then ZnajdźPierwszyWiększy:=l+1
  else ZnajdźPierwszyWiększy:=l;
end;

Teraz funkcja MaxNiemalejący:

function MaxNiemalejący(N:integer; A:array[1..N] of integer):integer;
var ia,ib,z: integer;
    B: array[1..N] of integer;
begin
  ib:=1;
  B[ib]:=A[1]; 
  for ia:=2 to N do
    if A[ia] >= B[ib] then begin
      ib:=ib+1;     
      B[ib]:=A[ia]; 
    end
    else begin 
      z:=ZnajdźPierwszyWiększy(B,1,ib,ia);
      B[z]:=A[ia];
    end;
  MaxNiemalejący:=ib;
end;

Ponieważ dla każdego elementu A wykonujemy wyszukiwanie binarne w B to:

Koszt czasowy: O(N×logN)

Koszt pamięciowy: liniowy względem N

Pytanko 1

Czy algorytm zachłanny by zadziałał (przedłużamy podciąg o ile rozpatrywany element jest większy równy od ostatniego elementu dotychczas znalezionego podciągu) ?