Informatyka MIMUW

Ćwiczenie programistyczne na listy:

1. Lista $n$ pierwszych liczb naturalnych.
2. Zdublować elementy listy.
3. Napisz procedurę last, której wynikiem jest ostatni element listy.
4. Napisz procedury head i tail, które dla zadanej listy $l$ i liczby całkowitej $n$
   zwracają pierwsze/ostatnie $n$ elementów listy $l$.
   Jeśli lista $l$ ma mniej elementów niż $n$, to wynikiem powinna być cała lista $l$.
   (Nazwy pochodzą od programów head i tail w Uniksie.)
   Co jest wynikiem tail (head l n) 1?
5. Napisz procedurę, która listę par postaci $[(n_1, x_1); (n_2, x_2); \dots; (n_k, x_k)]$ przekształca w listę postaci
   $[\underbrace{x_1; \dots; x_1}_{n_1 \mathrm{\ razy}}; \underbrace{x_2; \dots; x_2}_{n_2 \mathrm{\ razy}}; \dots; \underbrace{x_k; \dots; x_k}_{n_k \mathrm{\ razy}}]$.
6. Napisz procedurę shuffle: α list → α list → α list, która dla danych dwóch list postaci $[x_1; x_2; \dots; x_n]$ oraz $[y_1; y_2; \dots; y_m]$ wyznaczy listę postaci $[x_1; y_1; x_2; y_2; \dots]$. Jeżeli jedna z list jest dłuższa, to jej końcowe elementy trafiają na koniec listy wyikowej.
   Na przykład: shuffle [3; 2; 8; 1; 9; 3; 6] [5; 7; 0] = [3; 5; 2; 7; 8; 0; 1; 9; 3; 6].
   
   Rozwiązania
7. Załóżmy, że dana jest lista $[x_1; x_2; \dots; x_n]$.
   Sufiksem tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do $n$) jej początkowych elementów.
   Tak więc, sufiksami danej listy będzie n.p. ona sama, pusta lista, a także $[x_3; x_4; \dots; x_n]$.

   Napisz procedurę tails : α list → α list list,
   która dla danej listy tworzy listę wszystkich jej sufiksów, uporządkowaną wg ich długości (wybrać, czy rosnąco, czy malejąco).

   Rozwiązania

8. Napisz funkcję wysun : int list -> int list, która dla danej listy posortowanej niemalejąco wybierze wszystkie jej elementy występujące
   więcej niż raz i umieści w liście wynikowej przed elementami występującymi tylko raz. Kolejność oraz liczba poszczególnych elementów występujących wiele razy ma pozostać taka sama jak w liście wejściowej. Podobnie dla elementów występujących raz.
   Na przykład: wysun [1;2;2;3;4;5;5;6;6;6;7] = [2;2;5;5;6;6;6;1;3;4;7]

   Rozwiązania

9. Ciąg liczb naturalnych $x_0, x_1, \dots$ nazwiemy ciągiem Bonifacego wyznaczonym przez skończony niepusty ciąg zerojedynkowy $[b_0; \dots; b_{k−1}]$, jeśli $x_0 = 0$, $x_1 = 1$, $x_2 = 1$, a dla $i \ge 3$ zachodzi $x_i = x_{i−1} + x_{i−2}$ jeśli $b_i \mod k = 0$ oraz $x_i = x_{i−1} + x_{i−3}$ dla $b_i \mod k = 1$ (albo inaczej $x_i = x_{i−1} + x_{i−2−b_{i \mod k}}$).
   Na przykład ciąg $[1; 1; 0; 1]$ wyznacza ciąg Bonifacego: 0, 1, 1, 1, 2, 3, 5, 7, 10, 15, 25, 35, 50, ...
   Napisz funkcję bonifacy : int -> int list -> int, która dla liczby naturalnej n (n ≥ 0) oraz co najmniej trzyelementowej zerojedynkowej listy $[b_0; \dots; b_{k−1}]$ obliczy n-tą liczbę wyznaczonego przez tę listę ciągu Bonifacego.

   Rozwiązania

10. Dane są dwie listy liczb całkowitych uporządkowane niemalejąco.
    Oblicz ile różnych liczb występuje na tych listach.
11. Napisz procedurę zsumuj, która dla danej niemalejącej listy dodatnich liczb całkowitych
    $(a_1 \dots a_n)$ obliczy listę $(b_1 \dots b_n)$, gdzie $b_i = \sum_{k=a_i}^n a_k$.
    (Pamiętaj o tym, że jeśli $m>n$, $\sum_{k=m}^n a_k = 0$.)
12. Napisz program wybierający $\max$ i $\min$ z listy i dokonujący (w miarę) jak najmniejszej liczby porównań.
13. Napisz program wybierający element dominujący z listy większościowej; uzasadnij jego poprawność.
14. Napisz procedurę podziel : int list → int list list, która dla danej listy postaci
    $[a_1; a_2; \dots; a_n]$, zawierającej permutację zbioru $\{1, 2, \dots, n\}$ znajdzie jej podział na jak najliczniejszą listę list postaci:
    $$[[a_1; a_2; \dots; a_{k_1}]; [a_{{k_1}+1}; a_{{k_1}+2}; \dots; a_{k_2}]; \dots; [a_{{k_{m-1}}+1}; a_{{k_{m-1}}+2}; \dots; a_{k_m}]]$$
    taką że:
    $$\begin{eqnarray*} \{a_1, a_2, \dots, a_{k_1}\} &=& \{1, 2, \dots, k_1\} \quad\mbox{(równość zbiorów)},\\ \{a_{{k_1}+1}, a_{{k_1}+2}, \dots, a_{k_2}\} &=& \{k_1+1, k_1+2, \dots, k_2\},\\ &\vdots& \\ \{a_{{k_{m-1}}+1}, a_{{k_{m-1}}+2}, \dots, a_{k_m}\} &=& \{k_{m-1}+1, k_{m-1}+2, \dots, k_m\}. \end{eqnarray*}$$
    Przyjmujemy, że wynikiem dla listy pustej jest lista pusta.

    Przykład: $\mathtt{podziel}\, [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] = [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]]$.

15. Napisz procedurę mieszaj, która wywołana dla danej listy, obliczy listę powstałą przez
    następujące przestawienie elementów: na pozycjach nieparzystych mają kolejno znajdować się $\lceil \frac{n}{2} \rceil$
    początkowe elementy danej listy, a na pozycjach parzystych mają znajdować się pozostałe elementy danej listy, w odwrotnej kolejności.
    Na przykład: $\mathtt{mieszaj}\ [1;2;3;4;5] = [1;5;2;4;3]$.
16. Napisz procedurę trojki : int list → (int} * int * int) list,
    która dla zadanej listy dodatnich liczb całkowitych, uporządkowanej rosnąco, stworzy listę takich trójek $(a, b, c)$ liczb z danej listy, że:
    • $a < b < c$,
    • liczby $a$, $b$ i $c$ spełniają nierówność trójkąta, czyli $c < a + b$.
17. Dana jest lista liczb całkowitych $l = [x_1; \dots ; x_n]$ uporządkowana niemalejąco.
    Napisz procedurę: $\mathtt{malo} : \mathtt{int~list} \to \mathtt{int}$, która dla danej listy $l$ oblicza:
    $$\min \left\{|x_i + x_j| : 1 \le i < j \le n \right\}$$
    Na przykład, malo [-42, -12, -8, -1, -1, 5, 15, 60] = 2.

    Możesz założyć, że dana lista $l$ zawiera przynajmniej dwa elementy.

18. Dana jest niepusta, rosnąca lista liczb całkowitych $l = [x_1; \dots ; x_n]$.
    Napisz procedurę: $\mathtt{fit} : \mathtt{int} \to \mathtt{int~list} \to \mathtt{int}$, która dla danej liczby $c$ i listy $l$ obliczy:
    $$\min \left\{|c + x_i + x_j| : 1 \le i, j \le n \right\}$$
    Na przykład, fit 42 [-28, -25, -15, -1, 4, 8, 15, 60] = 1, ponieważ $|42 - 28 - 15| = 1$.
19. Prostokątną tabelę wypełnioną liczbami całkowitymi reprezentujemy jako listę list liczb całkowitych -- każdy wiersz
    to lista liczb, a tabela to lista wierszy.
    Oczywiście wszystkie listy reprezentujące wiersze są równej długości.

    Rozpatrujemy tabele, których wiersze są uporządkowane ściśle rosnąco, a kolumny ściśle malejąco.
    Napisz procedurę znajdz : int list list → int → (int * int) list, która znajduje wszystkie pozycje, na
    jakich w takiej tabeli znajduje się podana liczba.

20. Rozważmy następującą metodę kompresji ciągów liczb całkowitych:
    Jeżeli w oryginalnym ciągu ta sama liczba powtarza się kilka razy z rzędu, to jej kolejne wystąpienia reprezentujemy za pomocą jednej tylko liczby.
    Konkretnie, $i$ powtórzeń liczby $k$ reprezentujemy w ciągu skompresowanym jako $2^{i-1} \cdot (2 \cdot k - 1)$.

    Napisz procedurę dekompresuj : int list → int list dekompresującą zadaną listę.
    Możesz założyć, że lista skompresowana nie zawiera zer.

    Podaj specyfikację (warunek początkowy i końcowy) wszystkich definiowanych procedur i uzasadnij zwięźle ich pełną poprawność.
    W przypadku rekurencyjnych procedur iteracyjnych warunek początkowy musi zawierać niezmiennik iteracji.

     
          dekompresuj [1; 3; 3; 9; 42; 3];;
          - : int list = [1; 2; 2; 5; 11; 11; 2]
     

    Rozwiązania

21. Palindrom, to taka lista $p$, że $p = \mathtt{rev}\ p$.
    Napisz procedurę palindrom : α list → int,
    która dla danej listy obliczy długość jej najdłuższego spójnego fragmentu, który jest palindromem.
22. Napisz procedurę podziel : int → α list → α list list,
    która dla $k > 0$ i listy $[x_1; \dots; x_n]$ podzieli ją na listę list postaci:
    $$[ [x_1; x_{k+1}; x_{2k+1}; \dots]; [x_2; x_{k+2}; x_{2k+2}; \dots]; \dots; [x_k; x_{2k}; x_{3k}; \dots] ]$$

    Przykład: $\mathtt{podziel}\ 3\ [1;2;3;4;5;6;7] = [[1; 4; 7]; [2; 5]; [3; 6]]$.

23. [XIII OI]
    Mały Jaś dostał od rodziców na urodziny nową zabawkę, w której skład wchodzą rurka i krążki.
    Rurka ma nietypowy kształt -- mianowicie jest to połączenie pewnej liczby walców (o takiej samej grubości)
    z wyciętymi w środku (współosiowo) okrągłymi otworami różnej średnicy.
    Rurka jest zamknięta od dołu, a otwarta od góry.
    Krążki w zabawce Jasia są walcami o różnych średnicach i takiej samej grubości co walce tworzące rurkę.

    Jaś wymyślił sobie następującą zabawę.
    Mając do dyspozycji pewien zestaw krążków zastanawia się, na jakiej głębokości zatrzymałby się ostatni z nich,
    gdyby wrzucać je kolejno do rurki centralnie (czyli dokładnie w jej środek).
    Każdy kolejny krążek po wrzuceniu spada dopóki się nie zaklinuje (czyli nie oprze się o walec, w którym wycięty jest
    otwór o mniejszej średnicy niż średnica krążka), albo nie natrafi na przeszkodę w postaci innego krążka lub dna rurki.

    Napisz procedurę krążki : int list → int list → int, która na podstawie listy średnic
    otworów w kolejnych walcach tworzących rurkę, oraz listy średnic kolejno wrzucanych krążków obliczy głębokość, na której zatrzyma się
    ostatni wrzucony krążek (lub 0 jeśli nie wszystkie krążki zmieszczą się w rurce).
    
    Rozwiązania

24. System $-2$-kowy jest podobny do systemu binarnego, ale podstawą tego systemu jest liczba $-2$.
    Są dwie możliwe cyfry: 0 i 1.
    Ciąg cyfr postaci $c_k c_{k-1} \dots c_1 c_0$ reprezentuje liczbę $\sum_{i=0}^k c_i(-2)^i$.
    Na przykład, liczbę 42 reprezentujemy jako $1111110_{-2}$.
    Kolejne cyfry, od mniej do bardziej znaczących, tworzą listę.
    Przyjmujemy, że lista pusta reprezentuje 0.
    1. [V OI, zadanie Bankomaty]
       Napisz procedurę $\mathtt{neg2\_of\_int} : \mathtt{int} \to \mathtt{int~list}$, która przekształca daną liczbę całkowitą
       w jej reprezentację w systemie $-2$-kowym.
    2. Napisz procedurę $\mathtt{int\_of\_neg2} : \mathtt{int} \to \mathtt{int~list}$, która przekształca reprezentację
       w systemie $-2$-kowym w liczbę całkowitą.
    3. Napisz procedurę $\mathtt{inc} : \mathtt{int~list} \to \mathtt{int~list}$, która dla
       danej listy będącej reprezentacją liczby $x$, wyznaczy reprezentację liczby $x+1$.
    4. Napisz procedurę $\mathtt{inv} : \mathtt{int~list} \to \mathtt{int~list}$, która dla
       danej listy będącej reprezentacją liczby $x$, wyznaczy reprezentację liczby $-x$.
    5. Napisz procedurę $\mathtt{dodawanie} : \mathtt{int~list} \to \mathtt{int~list} \to \mathtt{int~list}$, która dla
       danych dwóch reprezentacji liczb całkowitych w systemie $-2$-ym obliczy reprezentację ich sumy.
       Na przykład: dodawanie [1;0;1;0;0;1;1] [1;0;1] = [0;1;1;1;1;1;1].
25. Wielomian postaci $a_0 \cdot x^0 + a_1 \cdot x^1 + \cdots + a_n \cdot x^n$ reprezentujemy w postaci listy $[a_0; a_1; \dots; a_n]$.
    Napisz procedurę mnóż : float list → float list → float list mnożącą wielomiany.

    Uwaga: Pusta lista reprezentuje zerowy wielomian.