- Binarny ciąg Van der Corputa powstaje poprzez odwracanie zapisu binarnego kolejnych liczb naturalnych. Przed odwróceniem zapisy binarne są najpierw uzupełniane zerami do odpowiedniego miejsca. Np. jeśli rozpatrujemy ciąg trzycyfrowy (w zapisie binarnym), to przed odwróceniem mamy ciąg zapisów: [000, 001, 010, 011, 100, 101, 110, 111], co tłumaczy się na ciąg [0, 1, 2, 3, 4, 5, 6, 7]. Po odwróceniu zapisów mamy natomiast [000, 100, 010, 110, 001, 101, 011, 111], co tłumaczy się na ciąg [0, 4, 2, 6, 1, 5, 3, 7]. Napisz funkcję vdcorput(p), która dla zadanej liczby cyfr p zwróci odpowiadający jej ciąg Van der Corputa.
- Napisz iteracyjną i rekurencyjną wersję funkcji incr_segment(v), która dla zadanej listy v zwróci jej najdłuższy rosnący segment (spójny kawałek).
- Napisz funkcję prefix(s, w), która dla dwóch słów s i w zwróci najdłuższy wspólny prefix obu słów.
- Napisz funkcję ol_concat(s, w), która sklei ze sobą dwa słowa być może nakładając na siebie koniec s z początkiem w lub koniec w z początkiem s (jeśli są identyczne) aby otrzymać najkrótsze w tym sensie połączenie tych słów. Np. dla słów ol_concat(kajak, kredka) powinno być równe kredkajak, gdyż można je skleić albo do kredkajak, albo do kajakredka, ale pierwsze z tych słów jest krótsze w zapisie.
- Napisz funkcję convert(n, p1, p2), która przekształci liczbę n w systemie p1-tkowym na liczbę w systemie p2-tkowym. Można założyć, że zarówno p1 jak i p2 są z przedziału [2, 9]. Np. convert(23, 10, 2)=10111.
- Zaimplementuj funkcję bucket_sort(v), która posortuje ciąg liczb całkowitych z przedziału [-10000; 10000] używając sortowania kubełkowego.
Skip to content
@ MIM UW