Wstęp do programowania / Ćwiczenia 5

<<< Powrót do modułu Składnia i semantyka instrukcji

To są zadania na wyszukiwanie binarne.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

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

To zadanie było omawiane na wykładzie. Dla pełności włączamy je tu do zestawu.

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 ZnajdźPierwsze:=l
  else ZnajdźPierwsze:=0;
end;

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Wizualizacja

Ćwiczenie 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)

Wskazówka 1

Funkcja div ciągnie w lewo. Jeśli liczba jest nieparzysta, wówczas obcina wynik w dół. Aby uzyskać symetryczny efekt, powinniśmy się zastanowić, jak zmusić div do zaokrąglania w górę.

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 ZnajdźOstatnie:=l
  else ZnajdźOstatnie:=0;
end;

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Wizualizacja

Ćwiczenie 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,x,A);
  p:= ZnajdźOstatnie(N,x,A);
  if l<>0 then LiczbaWystąpień:=p-l+1
  else LiczbaWystąpień:=0
end;

Koszt czasowy: logarytmiczny względem N

Koszt pamięciowy: stały

Wariant rozwiązania, w którym większość kodu ZnajdźPierwsze i ZnajdźOstatnie jest wpisana wprost do treści procedury:

function LiczbaWystąpień1(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,p1,l1: integer;
begin
  l1:=1; p1:=n; 
  while l1<>p1 do
   begin
       s:=(l1+p1) div 2; 
       if A[s]<x then l:=s+1
       else p:=s
   end;
  l:=l1;
  l1:=1; p1:=n; 
  while l1<>p1 do
   begin
       s:=(l1+p1+1) div 2; 
       if A[s]>x then p:=s-1
       else l:=s
   end;
   p:=l1;
   LiczbaWystąpień1:=p-l+1
end;

Uwaga: czy kod ten jest poprawny, gdy x'a nie ma w tablicy?

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

Wizualizacja

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 indeksu maksymalnej wartości 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

Wizualizacja

Zadanie 6 (Pierwiastek z x)

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

Wskazówka 1

Najprostsze rozwiązanie jest liniowe ze względu na wartość pierwiastka z x.

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: pierwiastkowy względem x

Koszt pamięciowy: stały

Wizualizacja

Wskazówka 2

Oczywiście lepiej jest to zrobić 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:integer):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 x

Koszt pamięciowy: stały

Wizualizacja

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:integer):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 x

Koszt pamięciowy: stały

Wizualizacja

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.

Wskazówka 2

Użyj podobnego pomysłu jak przy mnożeniu chłopów rosyjskich. Pamiętaj, że mnożenie ma się tak do dodawania, jak potęgowanie do mnożenia.

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

Wizualizacja

O ile istnieją proste algorytmy mnożące w czasie wielomianowym (choćby szkolne słupki), to w przypadku potęgowania nie ma oczywistego szybkiego algorytmu potęgującego. Można spytać, po co usprawniać kod potęgowania, gdy wykładniki w naturze wcale nie sa takie duże. Nic bardziej mylnego! W jednym z najpopularniejszych algorytmów kryptograficznych - kodowaniu RSA - używa się potęgowania o wykładnikach będących bardzo dużymi liczbami (zazwyczaj stukilkudziesięciocyfrowymi!). Poleglibyśmy sromotnie, gdybyśmy próbowali mnożyć odpowiednią liczbę razy przez siebie podstawę potęgowania.

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,A[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

Wizualizacja

Ćwiczenie 1

Czy algorytm zachłanny by zadziałał? Zachłanność polegałaby na tym, że przedłużalibyśmy podciąg pod warunkiem, że rozważany element jest niemniejszy od ostatniego elementu dotychczas znalezionego maksymalnego podciągu.