Ćwiczenia 13: Zastosowanie sortowania

W poniższych zadaniach istotne jest posortowanie odpowiednich list:

  1. 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.

  2. 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.
  3. [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.)

  4. 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

  5. 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
  6. [*]
    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.