Ćwiczenie programistyczne na listy:
- Lista \(n\) pierwszych liczb naturalnych.
- Zdublować elementy listy.
- Napisz procedurę
last, której wynikiem jest ostatni element listy.
-
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?
-
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}}]\).
-
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
-
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
-
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
-
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
-
Dane są dwie listy liczb całkowitych uporządkowane niemalejąco.
Oblicz ile różnych liczb występuje na tych listach.
-
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\).)
-
Napisz program wybierający \(\max\) i \(\min\) z listy i dokonujący (w miarę) jak najmniejszej liczby porównań.
-
Napisz program wybierający element dominujący z listy większościowej; uzasadnij jego poprawność.
-
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]]\).
-
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]\).
-
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\).
-
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.
-
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\).
-
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.
-
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
-
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.
-
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]] \).
- [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
-
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.
- [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.
-
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ą.
-
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\).
-
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\).
-
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].
-
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.