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

{{{3}}}

Ćwiczenie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 2

{{{3}}}

Inna wersja zadania

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

Wskazówka 3

{{{3}}}

Rozwiązanie 3

{{{3}}}

Zadanie 7 (BinPower)

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

Wskazówka 1

{{{3}}}

Wskazówka 2

{{{3}}}

Rozwiązanie 1

{{{3}}}

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

{{{3}}}

Rozwiązanie 1

{{{3}}}

Ćwiczenie 1

{{{3}}}