Ćwiczenia 4 - Procedury, rekurencja

1. Wyznaczyć zależność rekurencyjną określającą liczbę spójnych obszarów, na które dzieli płaszczyznę n prostych, z których żadne dwie nie są równoległe i żadne trzy nie przecinają się w jednym punkcie.
2. Znaleźć zależność rekurencyjną określającą liczbę różnych sposobów wejścia po schodach zbudowanych z n stopni, jeśli w każdym kroku można pokonać jeden lub dwa stopnie.
3. Zapisać w postaci procedury poniższy algorytm:
   

   integer a, b, k
   read(a,b)
   if a > b
   	k = b
   else
   	k = a
   while (a mod k) ≠ 0 or (b mod k) ≠ 0
   	k = k - 1
   write(k)

   .
4. Zapisać w postaci procedury algorytm wyznaczający liczbę największych elementów tablicy dwuwymiarowej.
5. Podać definicję procedury wyznaczającej najmniejszą wartość tablicy A, przy czym chcemy, aby procedura sprawdzała dowolny podciąg od d do g kolejnych elementów tablicy, gdzie 1 <= d <= g <= n.
6. W tablicy A zawierającej liczby znajdują się dwa uporządkowane (niemalejąco) ciągi na miejscach od indeksu p do indeksu q i od indeksu q + 1 do indeksu r, gdzie p <= q < r. Zapisać definicję procedury, która scali te dwa ciągi w jeden niemalejący ciąg i umieści go w tablicy A na miejscach od p do r.
7. W tablicy A zawierającej liczby znajdują się dwa uporządkowane (niemalejąco) ciągi na miejscach odpowiednio od indeksu p do indeksu q i od indeksu q + 1 do indeksu r, gdzie p <= q < r. Zapisać definicję procedury, która scali te dwa ciągi w jeden niemalejący ciąg i umieści go w tablicy A na miejscach od A[p] do A[r] bez sprawdzania za każdym razem, czy wszystkie elementy któregoś z ciągów zostały już wzięte pod uwagę.
8. Zadana jest tablica A[p..r] zawierająca liczby. Napisać definicję procedury, która dzieli tę tablicę (poprzez przestawienie jej elementów) na dwie tablice A[p..q - 1] i A[q + 1..r] w ten sposób, że każdy element z pierwszej podtablicy jest nie większy niż element A[q], który z kolei jest mniejszy od każdego elementu z drugiej podtablicy. Obliczenie indeksu q ma stanowić część tej procedury podziału.
9. Zapisać definicję funkcji wyznaczającej najmniejszy element tablicy jednowymiarowej.
10. Zapisać definicję procedury NWD w postaci procedury funkcyjnej.
11. Dane są dwa wektory A[1..n] B[1..n] zawierające liczby. Napisać definicję funkcji logicznej przyjmującej wartość true wtedy i tylko wtedy, gdy oba wektory są równe.