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 Znajdz_Pierwsze(N,A,x):integer;
var l,p,s : integer;
begin
  l:=1;
  p:=N;
  while l < p do begin
    s:=(l+p)div 2;
    if A[s] < x then l:=s+1;
    else p:=s;
  end;
  if A[l] = x then Znajdz_Pierwsze:=l
  else Znajdz_Pierwsze:=0;
end;

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 Znajdz_Ostatnie(N,A,x):integer;
var l,p,s : integer;
begin
  l:=1;
  p:=N;
  while l < p do begin
    s:=(l+p+1)div 2;
    if A[s] > x then p:=s-1;
    else l:=s;
  end;
  if A[l] = x then Znajdz_Ostatnie:=l
  else Znajdz_Ostatnie:=0;
end;

Zadanie 3 (Policz liczbę wystapień x)

Dana jest posortowana niemalejąco tablica A typu array[1..N] of integer i x typu integer. Policz ile razy występuje w niej wartość x.

Wskazówka 1

Trzeba użyc wyszukiwania binarnego a nie liniowego.

Rozwiązanie 1

function Liczba_wystapien(N,A,x):integer;
var p,l: integer;
begin
  l:= Znajdz_Pierwsze(N,A,x);
  p:= Znajdz_Pierwsze(N,A,x);
  if l <> 0 then Liczba_wystapien:=p-l+1;
end;

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 zwróć ten indeks, jeśli nie to zwróć 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 Rowny(N,A):integer;
var p,l,s: integer;
begin
  if (A[1] > 1) or (A[N] < N) then Rowny:=0 
  else 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;
    Rowny:=(A[l]=l);
  end;   
end;

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

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 < i zachodzi A[k] < A[k+1] a dla wszystkich k ≥ i 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 Maks_bitoniczny(N,A):integer;
var p,l,s: integer;
begin
  if N=1 then Maks_bitoniczny:=1 
  else 
    if A[N-1] < A[N] then Maks_bitoniczny:=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;
      Maks_bitoniczny:=l;
    end;   
end;

Zadanie 6 (Pierwiastek z x)

Napisz program obliczający sufit z pierwiastka z x, dla xεR, x > 0. (Oczywiście bez operacji pierwiastek; za to dostępna jest funkcja Sufit).

Wskazówka 1

Najprostsze rozwiązanie jest liniowe.

Rozwiązanie 1

function SufitPierwiastka1(x:Real):integer;
var i: integer;
begin
  i:=1; 
  while i*i < x do i := i+1;
  SufitPierwiastka1 := i;
end;

Wskazówka 2

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

Rozwiązanie 2

function SufitPierwiastka2(x:Real):integer;
var l,p,s : integer;
begin
  l:=1;
  p:=Sufit(x);
  while l < p do begin
    s:=(l+p)div 2;
    if s*s < x then l:=s+1;
    else p:=s;
  end;
  SufitPierwiastka2:=l;
end;

Zadanie 7 (Binpower)

Dla zadanego x$\in$R i n$\in$N policz x^n (oczywiscie bez exp i ln).

Rozwiązanie 1

function Binpower(N,A,x):integer;
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;

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

function Podciag_niemalejący(N,A):integer;
var : integer;
    B: array[1..N] of integer;
begin
  ib:=1;
  B[ib]:=A[1];
  ia:=2; 
  while ia <= N do begin
    if A[ia] >= B[ib] then begin
      ib:=ib+1;     
      B[ib]:=A[ia]; 
    end
    else begin 
      z:=ZnajdzPierwszyWiekszy(B,1,ib);
      B[z]:=A[ia];
      if z = ib+1 then ib:=ib+1;
    end;
    ia:=ia+1;
  end;
  Podciag_niemalejący:=ib;
end;