Zadanie 30
WE: tablica A[1..n]
WY: max, min - maksymalni i minimalny element tablicy A.
Wymaganie dodatkowe: wszystko oblicz w jednym przebiegu przez A.
Zadanie 31
WE: tablica A[1..n], n; A jest posortowane "<=" (niemalejąco)
WY: x = liczba różnych elementów w tablicy A
Wymaganie dodatkowe: wszystko oblicz w jednym przebiegu przez A.
Zadanie 31.1
WE: tablica A[1..n]
WY: x = liczba różnych elementów w tablicy A
Zadanie 32
WE: tablica A[1..n]
WY: lmax, lmin - liczba maksymalnych i minimalnych
elementów w tablicy A
Wymaganie dodatkowe: wszystko oblicz w jednym przebiegu przez A.
Zadanie 33
WE: tablica A[1..n], n, m
WY: znaleźć element tablicy A który najczęściej występuje w A
Założenie: elementy tablicy A należą do zbioru {1, ..., m}
Zadanie 33.1
WE: tablica A[1..n], n
WY: odwróć kolejność elementów tablicy A
Zadanie 33.2
WE: tablica A[0..n] zawierająca współczynniki wielomianu
W(x) = A[n]*x^n + A[n-1]*x^(n-1) + ... + A[1]*x + A[0]
WY: oblicz wartość tego wielomianu.
Wymaganie dodatkowe: liczba operacji mnożenia powinna wynosić O(n).
Zadanie 34
WE: tablica A[1..n], i1, k, i2
Napisz algorytm przesuwający fragment tablicy A zaczynający się w elemencie
"i1", o długości "k", w miejsce zaczynające się od elementu "i2".
Algorytm musi sprawdzać czy przesunięcie jest w ogóle możliwe.
Zadanie 35
Napisz algorytm generujący losową permutację zbioru {1, ..., n} w tablicy
A[1..n]. Zakładamy że dysponujemy funkcją random(k) zwracającą liczbę
wybraną ze zbioru {1, ..., k} z tym samym prawdopodobieństwem (=1/k).
Wszystkie permutacje mają mieć to samo prawdopodobieństwo = 1/(n!), i ma to
być oczywiste ...
Zadanie 36
WE: A[1..n], c -liczba całkowita
WY: rotacja cykliczna tablicy A o c -elementów (jeśli c<0 to
przesuwamy "w lewo").
Wymaganie dodatkowe: algorytm ma działać w czasie O(n) [a nie O(c*n), co
oznacza że nie można napisać algorytmu rotującego cyklicznie o 1 lub -1 element
i powtarzać go c -krotnie]
Uwagi: nie ma zakazu używania pomocniczych tablic.
Zadanie 36.5 (*)
Wykonaj rotacje cykliczną z zadania 36 z dodatkowym wymaganiem że NIE
WOLNO używać tablic pomocniczych (i nadal czas działania ma wynosić O(n)).
Wskazówka: przyda się tu rozpatrywanie 2 przypadków "c dzieli n" i "c nie
dzieli n".
..............................................................
Zadanie
37
WE: dane są macierze A[1..a1, 1..a2], B[1..b1, 1..b2]
WY: macierz C[1..a1, 1..b2], taka że C = A * B
Przypominam jak się mnoży macierze: do elementu C[i,j] wpisujemy iloczyn
skalarny i-tego wiersza macierzy A oraz j-tej kolumny macierzy B (wiersz i
kolumna muszą mieć tą samą długość!). Algorytm powinien sprawdzać czy mnożenie
macierzy jest w ogóle możliwe.
Zadanie 38
WE: dana jest macierz kwadratowa M[1..n, 1..n]
WY: sprawdź czy M jest "magiczna", tj czy wszystkie kolumny i wiersze maja tą
samą sumę elementów.
Zadanie 39
WE: dana jest "kostka" V[1..m, 1..n, 1..p].
WY: oblicz i wypisz sumy elementów znajdujących się na wszystkich 6 ścianach tej kostki.
Zadanie 40
WE: dana jest "kostka" V[1..m, 1..n, 1..p].
WY: min i max - minimalny i maksymalny element kostki.
Zadanie 41
WE: liczby a, b, c
WY: tablica A[1..n, 1..n] wypełniona
następującymi wartościami: główna przekątna A ma być wypełniona liczbą "b", przekątna pod główną przekątną ma być wypełniona liczbą "a", przekątna nad główną przekątną ma być wypełniona liczbą "c", pozostałe elementy macierzy maja być wyzerowane.
Zadanie 42
WE: oceny[1..n] - tablica zawierająca oceny ze zbioru {2,3,4,5}
WY: rozkład ocen w procentach, podany w tablicy rozklad[2..5], której
elementami są liczny rzeczywiste z przedziału [0,1].
Zadanie 43
Zaimplementuj tablicę dwuwymiarową
V[K0..K1, L0..L1]
przy pomocy jednowymiarowej tablicy V1.
Innymi słowy: zakładamy że dysponujemy tablicami jednowymiarowymi a potrzebujemy
tablic dwuwymiarowych i chcemy je "symulować" przy pomocy tablic
jednowymiarowych.
L0 L0+1 L1-1 L1 K0 x x x x x x x x x K0+1 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x K1-1 x x x x x x x x x K1 x x x x x x x x x ^ to są elementy tablicy V, o współrzędnych (a,b) gdzie a=K0..K1, b=L0..L1
Dla elementu V[a,b] gdzie a=K0..K1, b=L0..L1, należy podać odpowiadający mu element tablicy V1, tj należy zdefiniować V[a,b] = V1[/* tu wstaw funkcję f(a,b,K0,K1,L0,L1) */]. Dodatkowo należy określić wymiar tablicy V1.
Zadanie 44
(Wyszukiwanie proste) Dana jest tablica A[1..n], nieposortowana.
Zapisz algorytm który wyszukuje element "x" w tablicy A i podaje jego indeks w
zmiennej "ind"; jeśli takiego elementu nie ma w tablicy A to ind powinno być
równe 0.
Zadanie 45
(Wyszukiwanie binarne) Mamy posortowaną "<=" (niemalejąco) tablicę A[1..n].
Zapisz algorytm który wyszukuje element "x" w tablicy A i podaje jego indeks w
zmiennej "ind"; jeśli takiego elementu nie ma w tablicy A to ind powinno być
równe 0.
Wymaganie dodatkowe: chodzi tu o szybszy algorytm niż ten z zadania 44
(wykonujący log n operacji).
Wskazówka: wyobraź sobie że szukasz nazwiska w książce telefonicznej, jak
postępujesz ... ?,
Zadanie 46
WE: tablica A[0..n] zawierająca współczynniki wielomianu
W(x) = A[n]*x^n + A[n-1]*x^(n-1) + ... + A[1]*x + A[0]
WY: tablica B[0..n] zawierająca współczynniki wielomianu będącego pochodną W(x)
względem x.
Zadanie 47
Napisz algorytm wypełniający zawartością tablicę A[0..n, 0..n] tak aby można
było obliczać symbol Newtona "n po k" w stałym czasie, odczytując jedynie
odpowiedni element tablicy A. Pokaż też jak się oblicza symbol Newtona
korzystając z tablicy A.
Wymaganie dodatkowe: wypełnij tablicę A tak jak się tworzy tzw
trójkąt Pascala, czyli korzystając z zależności:
Newton(n+1, k+1) = Newton(n, k) + Newton(n, k+1).
Zadanie domowe 50
WE: tablice A[1..n], B[1..n] - tablice reprezentujące liczby w zapisie
dziesiętnym (każdy element tablicy zawiera jedną cyfrę);
WY: tablica C[1..n+1] = wynik dodawania liczb zapisanych w tablicach A i B.
Zadanie domowe 51
WE: A[1..n], B[1..n], C[1..n] - posortowane "<=" tablice liczb;
WY: W[1..3n] - tablica W zawiera wszystkie elementy tablic A, B i C, oraz jest
posortowana.
Wymaganie dodatkowe: algorytm powinien działać w czasie O(n);
w szczególności nie wolno po prostu przepisać tablic A, B, C do W i potem
posortować W.
Zadanie domowe 52
Zapisz algorytm który oblicza C:=A ÈB,
czyli sumę teorio-mnogościową zbiorów liczb całkowitych A i B, a wynik umieszcza
w C. Zbiory liczb są reprezentowane jako tablice w których liczby się nie
powtarzają (tablice te nie są posortowane !). Liczba elementów zbioru A jest
równa dluA, czyli używane są elementy A[1], ..., A[dluA], podobnie z pozostałymi
zbiorami. Zauważ, że wynik działania procedury, czyli C, także musi być
prawidłową reprezentacją zbioru !. Wymiary tablic A, B i C są następujące:
A[1..n], B[1..n], C[1..2n]. Nie wolno używać żadnych pomocniczych tablic.
Procedura musi działać w czasie O(n^2).
Zadanie domowe 52.5
Zapisz algorytm który oblicza C:=A ÈB.
Tym razem zbiory liczb są reprezentowane jako posortowane rosnąco tablice
w których liczby się nie powtarzają. Obowiązują oznaczenia z poprzedniego
zadania. Procedura musi działać w czasie O(n).
Wskazówka: przypomnij sobie algorytm scalania dwóch posortowanych ciągów
liczb ... .
Zadanie domowe 53
Wykonaj zadanie 36.5 jeśli nie zostało wykonane w
czasie zajęć.