Rozwiązane zadania
temat: algorytmy

Napisz algorytm (w postaci listy kroków, w pseudokodzie lub w wybranym języku programowania), który dla danego ciągu liczb zapisanych przez dzieci znajdzie pierwszą liczbę zapisaną przez Jasia. Zakładamy, że każde z dzieci zapisało co najmniej jedną liczbę.
Przy ocenie będzie brana pod uwagę złożoność czasowa Twojego algorytmu. Maksymalną liczbę punktów uzyskasz za algorytm o złożoności lepszej niż liniowa.
Uwaga: W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), instrukcje porównania, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje, wykorzystujące wyżej wymienione operacje.
Specyfikacja:
Dane:
- n – liczba całkowita większa od 1
- A[1..n] – tablica zawierająca ciąg n liczb zapisanych przez dzieci (najpierw wszystkie liczby nieparzyste, a potem wszystkie liczby parzyste)
Wynik:
- w – pierwsza od lewej parzysta liczba w tablicy A
...

W zaprezentowanej w tym punkcie funkcji REG(w,n) uzupełnij brakujące elementy tak, aby realizowała ona następującą specyfikację:
Specyfikacja:
Dane:
  n – dodatnia liczba całkowita
  w[1..n] – słowo złożone z liter A, B
Wynik:
  wartość reg(w).
    
Funkcja REG(w,n):
jeżeli n = 1...

Podaj największą i najmniejszą możliwą liczbę wywołań funkcji Rek w wyniku wywołania Rek(2020, 5, 14) dla n = 17 i pewnej, uporządkowanej rosnąco tablicy T[1..17] różnych liczb całkowitych.
Uwaga: Pierwsze wywołanie funkcji Rek(2020, 5, 14) włączamy do ogólnej liczby wywołań.
Odpowiedź:
najmniejsza liczba wywołań …………………………
największa liczba wywołań …………………………...

Podaj, jakie będą wartości parametrów przekazywanych do funkcji Rek w kolejnych jej wywołaniach dla n = 11, tablicy T = [1, 5, 8, 10, 12, 14, 19, 20, 23, 30, 38] oraz pierwszego wywołania Rek(7, 1, 11)....

Złożoność czasowa algorytmu opisanego funkcją Rek dla parametrów x = 1, p = 1, k = n jest
A. sześcienna.
B. kwadratowa.
C. liniowa.
D. logarytmiczna.
Wybierz właściwą odpowiedź....

W wybranej przez siebie notacji (w postaci pseudokodu, listy kroków, lub języka programowania) napisz algorytm zgodny z poniższą specyfikacją:
Dane:
  n – dodatnia liczba całkowita większa niż 2
  T[1..n] – tablica n liczb całkowitych, w której występuje dokładnie jedna moda
Wynik:
  m – moda zestawu liczb zapisanego w tablicy T
Uwaga: w zapisie możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), odwoływanie się do pojedynczych elementów tablicy, porównywanie liczb, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje zawierające wyżej wymienione operacje....

Podaj wynik działania algorytmu dla wskazanych w tabeli wartości n. 
n  p
28  ?
64  ?
80  ?...

Podaj najmniejszą oraz największą liczbę n, dla której wynikiem działania algorytmu będzie p = 10...

Dla każdej liczby całkowitej n > 1 instrukcja oznaczona w algorytmie symbolem (*)
wykona się
A. mniej niż 2·log₂n razy.
B. więcej niż n/2, ale mniej niż n razy.
C. więcej niż n+1, ale mniej niż 2n razy.
D. więcej niż n² razy....

Napisz algorytm (w pseudokodzie lub wybranym języku programowania), który znajdzie i poda
współrzędne skrajnie lewego szczytu, tzn. widocznego dla obserwatora na lewo od wszystkich
pozostałych szczytów.
Specyfikacja:
Dane:
  n – liczba całkowita dodatnia
  X[1..n] – tablica liczb całkowitych
  Y[1..n] – tablica liczb całkowitych dodatnich
  Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 1, 2, …, n.
  Żadne dwa szczyty nie leżą w jednej linii z obserwatorem....

Napisz algorytm (w pseudokodzie lub wybranym języku programowania), który przestawi elementy tablic X i Y tak, aby szczyty były uporządkowane w kolejności, w której obserwator widzi je od lewej do prawej strony. 
Aby otrzymać maksymalną ocenę, Twój algorytm powinien mieć złożoność czasową kwadratową lub mniejszą. 

Algorytm może używać wyłącznie instrukcji sterujących, operatorów arytmetycznych, operatorów logicznych, porównań i przypisań do zmiennych. Zabronione jest używanie funkcji bibliotecznych dostępnych w językach programowania.
Specyfikacja:
Dane:
  n – liczba całkowita dodatnia
  X[1..n] – tablica liczb całkowitych
  Y[1..n] – tablica liczb całkowitych dodatnich
Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 1, 2, …, n....