W poniższych zadaniach istotne jest posortowanie odpowiednich list:
-
Tomek ma zabawkę, z której wystają drewniane słupki różnej wysokości.
Jednym uderzeniem młotka może wbić lub wysunąć wybrany słupek o 1.
Napisz procedurę słupki : int list → int, która dla danej listy początkowych wysokości słupków
obliczy minimalną liczbę uderzeń młotka potrzebnych do wyrównania wysokości słupków.
-
Napisz funkcję
elementy : α list → int list → α list, która dla list \([x_1; x_2; \ldots, x_n]\) i
\([y_1; y_2; \ldots; y_m]\) zwraca listę \([x_{y_1}; x_{y_2}; \ldots; x_{y_m}]\).
Możesz założyć, że liczby całkowite \(y_i\) w drugiej liście są z przedziału \([1, n]\), gdzie \(n\) oznacza długość pierwszej listy.
- [II OI]
Napisz procedurę trójkąt : int list → bool, która dla danej listy \([x_1; x_2; \dots; x_n]\) dodatnich liczb
całkowitych sprawdzi, czy taka lista zawiera trójkę elementów \(x_i, x_j, x_k\) (dla \(i \neq j\), \(j \neq k\), \(i \neq k\))
spełniających nierówność trójkąta, tzn.:
\[2 \cdot \max(x_i, x_j, x_k) \le x_i + x_j + x_k\]
Podaj złożoność czasową i pamięciową swojego rozwiązania.
(Uwaga: Jeżeli liczby całkowite mają ograniczony zakres, to można to zadanie rozwiązać w stałym czasie.)
-
Napisz procedurę
przedział : int list → int → int, która dla danej listy \([x_1;\dots; x_n]\), oraz dla liczby całkowitej
\(r \ge 0\) obliczy taką liczbę całkowitą \(c\), że \(\left| \left\{i : |x_i - c| \le r \right\}\right|\) jest maksymalne.
Przykład: przedział [2; -2; 5; -1; 11; 8; 4; 5; 8; 7] 2 = 6.
Rozwiązania
-
Dana jest lista liczb rzeczywistych \([x_1; x_2; \dots; x_n]\).
Napisz procedurę przekładaniec, której wynikiem jest taka permutacja \([x_{p_1}; x_{p_2}; \dots; x_{p_n}]\) danej listy,
dla której suma
\[\sum_{i=1}^{n-1} |x_{p_{i+1}} - x_{p_i}|\]
jest największa.
Rozwiązania
- [*]
Dana jest lista liczb całkowitych \([x_1; \dots; x_n]\).
Napisz procedurę pierwsze : int list → int list, która zwróci taką jej spójną podlistę, że:
- każde dwa elementy podlisty są względnie pierwsze,
- zawiera ona maksymalną możliwą liczbę elementów.