Lekcja 4
procedury i funkcje

Zadanie 80
Sortowanie macierzy metodą "sortowania przez selekcje" używając minimum.
Macierz  M[1..n, 1..m]:

M[1,1] M[1,2] M[1,3] ... M[1,m]
M[2,1] M[2,2] M[2,3] ... M[2,m]
...........................
M[n,1] M[n,2] M[n,3] ... M[n,m]

ma być posortowana "wierszami", tj:

M[1,1]<=M[1,2]<= ... <=M[1,m]<= 
M[2,1]<=M[2,2]<=     <=M[2,m]<=
...........................
M[n,1]<=...          <=M[n,m]

Koniecznie użyj procedury pomocniczej aby uprościć zapis tego algorytmu!. Pamiętaj tez ze procedura (funkcja) może "zwracać" więcej niż jedną wartość  (w Pascalu służą do tego parametry przekazywane przez zmienna oznaczane słowem var), my będziemy to zapisywać podobnie:

procedura ZwracamyDwaWyniki(a, b, var suma, var iloczyn) 
  suma<- a+b
  iloczyn<- a*b

procedurę taka wywołujemy następująco:

ZwracamyDwaWyniki(123, 321, x, y)
pisz x, y

Uwagi co do procedur:

• Wszystkie zmienne używane wewnątrz procedury (nie parametry!) są "lokalne" czyli dostępne tylko wewnątrz procedury.
• Dane z zewnątrz (np zmienne "globalne") muszą być przekazywane do procedury przez parametry; można także przekazywać dane w drugą stronę (słowo var).

Zadanie 81
WE: M[1..n, 1..m] - macierz prostokątna; wiersze macierzy są posortowane "<=" (niemalejąco).
WY: posortuj "<=" elementy macierzy M i umieść wynik w W[1..n*m];
Wymaganie: czas działania musi wynosić O(n^2*m), czyli liczba operacji musi być < stała*n^2*m - dlatego nie można po prostu przepisać M do tablicy W i posortować ...
Wskazówka: scalaj wiersze macierzy tak jak w zadaniu domowym 51; koniecznie użyj pomocniczej procedury scalającej!.

Zadanie 81.5 (*)
Wykonaj zadanie 81, ale podaj algorytm działający w czasie O(n*m*log₂n)

........................................................................

Zadanie 82
Odwróć kolejność elementów:
1) tablicy A[1..n]
2) macierzy B[1..n, 1..m]; chodzi o kolejność rozumianą "wierszami"
Wymagania: (1) wykonaj używając dwóch zmiennych L i P, zainicjowanych przez 1 i n, które zbliżają się ku sobie.
(2) wykonaj analogicznie jak (1), definiując funkcje/procedury pomocnicze:
    plus(var w, var k) - odpowiednik zwiększania zmiennej L z (1)
    minus(var w, var k) - odpowiednik zmniejszania zmiennej P z (1)
    mniejsze(w1, k1, w2, k2): Boolean - odpowiednik sprawdzania czy L<P z (1)

Uwaga: W jaki sposób funkcja "zwraca" wartość ? Odp:

funkcja Potega(a,b) 
  x<- 1
  for i<- 1 to b do
    x<- x*a
  Potega<- x

Zadanie 83
Oblicz wartość wielomianu:
1) wielomianu jednej zmiennej: $ y(x) = \sum_{i=0..n}A_i * x^i $ (wzór zapisany w formacie LaTeX);
    współczynniki wielomianu są przechowywane w tablicy A[0..n]
2) wielomianu dwóch zmiennych: $ z(x,y) = \sum_{i=0..n, j=0..n}A_{i,j} * x^i * y^j $;
    współczynniki wielomianu są przechowywane w tablicy A[0..n, 0..n].
Wymagania: (2) zrób używając procedury pomocniczej;
postaraj się żeby czas działania algorytmów był jak najkrótszy;
można używać tzw schematu Hornera.

Zadanie 84
Wyznacz najdłuższy podciąg rosnący, ciągu przechowywanego w tablicy A[1..n].

Zadanie 84.5 (*)
Wyznacz najdłuższy podciąg rosnący, ciągu przechowywanego w tablicy A[1..n].
Wymaganie dodatkowe: czas działania algorytmu powinien wynosić O(n * log n).

Zadanie 85
Znajdź k-ty element minimalny tablicy A[1..n].
Precyzacja: pierwszy element minimalny to po prostu "zwykły" element minimalny, drugi element minimalny to element minimalny gdybyśmy usunęli z tablicy pierwszy element minimalny itd.
 

Zadania domowe [na piśmie !!!]

Zadanie domowe 86
Wykonaj zadanie 81.5 jeśli nie zostało wykonane w czasie zajęć.

Zadanie domowe 87
Wykonaj zadanie 84.5 jeśli nie zostało wykonane w czasie zajęć.