WDI 2022/2023

Skrypt do przedmiotu dostępny jest na stronie wykładowcy - link.

Zadanie zaliczeniowe jest dostępne tutaj.

Zadanie dodatkowe (uzupełniające brakujące punkty z prac domowych) jest dostępne tutaj.

Zadania domowe:

Będzie 10 zadań domowych, z każdego można dostać od 0 do 1 pkt, z dokładnością do 0,25 pkt. Zadania proszę wysyłać mailowo.

• Zadanie 1 (termin oddania: 26.10 23:59) - Każdą permutację zbioru n-elementowego możemy reprezentować za pomocą tablicy o długości n, w której są przechowywane wszystkie liczby całkowite od 0 do n − 1. Permutacja σ jest reprezentowana w ten sposób, że σ(i) = a[i] dla i = 0, . . . , n − 1. Napisz w języku C dwie funkcje (wraz z nagłówkami). Obie funkcje nie mogą mieć żadnych efektów ubocznych i nie mogą zmieniać zawartości tablic z danymi ciągami liczb. Należy uwzględnić wszystkie możliwe przypadki brzegowe.

  • is_permutation, która sprawdza, czy podany w tablicy ciąg liczb jest poprawną reprezentacją permutacji (tj. czy występują w nim wszystkie liczby od 0 do n − 1). Funkcja ma zwracać wartość 1, jeśli ciąg jest poprawny, albo 0 w przeciwnym razie. Funkcja może mieć dodatkowy parametr — tablicę roboczą zmiennych typu char o długości n. (0,75 pkt)
  • compose_permutations, która znajduje permutację σ będącą złożeniem dwóch permutacji danych, σ(i) = σ2(σ1(i)) dla i = 0, . . . , n − 1, reprezentowanych przez zawartość odpowiednich tablic. Wynik ma być wpisany do trzeciej tablicy przekazanej jako parametr. (0,25 pkt)

• Zadanie 2 (termin oddania: 07.11 23:59):

  • przeczytać treść materiałów do labów 3 (link poniżej),
  • zainstalować CLiona lub inny edytor kodu,
  • na podstawie kodu z labów stworzyć program, który wczytuje jedną liczbę podaną przez użytkownika (nazwijmy ją x), następnie wczytuje x liczb podanych przez użytkownika, sortuje je i wypisuje na ekran. Przykładowo, użytkownik wpisuje 7 2 8 2 -5 4 9 1, a nasz program ma wypisać -5 1 2 2 4 8 9. Można założyć, że podana liczba x będzie zawsze mniejsza od 1000.
  • Przesłać na mojego maila zrzut ekranu pokazujący uruchomiony program, który posortował 10 liczb (np zrzut ekranu edytora kodu i terminala).
  • Wskazówki:
    • można zacząć od przekopiowania kodu z labów i usunięcia zbędnych funkcji np name_easy
    • po tej operacji warto uruchomić program i upewnić się, że read_input_and_sort faktycznie wczytuje i wypisuje dane
    • były już pokazane dwa różne algorytmy sortowania liczb, można użyć dowolnego z nich, tzn przepisać go do funkcji sort
    • wiemy, że maksymalny rozmiar tablicy to 1000 elementów, więc można używać tablicy tego rozmiaru, a x liczb wpisywać do jej pierwszych x miejsc
    • wczytanie liczby x można zrobić funkcją scan_number
    • całe rozwiązanie to dodanie/modyfikacja około 5 linijek kodu plus kod sortowania
    • zależy mi przede wszystkim na tym, żeby każdy był w stanie uruchamiać u siebie proste programy - spodziewam się, że więcej czasu zajmie zainstalowanie edytora kodu niż rozwiązanie zadania

• Zadanie 3 (termin oddania: 14.11 23:59, przedłużone do 19.11 23:59) - Napisz funkcję sprawdzającą, czy w tablicy są dwa sklejone ze sobą palindromy (jeśli tak, wykonaj return 1, a jeśli nie - return 0). Jako rozwiązanie wystarczy mi sam kod funkcji. Przykładowo:

  • abbakajak - tak, bo mamy abba i kajak
  • okooko - tak, bo mamy oko i oko
  • ab - tak, bo mamy a i b
  • abba - nie, bo to jest tylko jeden palindrom
  • okoko - nie, bo palindromy nie mogą mieć części wspólnej

  • abbazzzkajak - nie, bo zzz nie należy do żadnego palindromu

    Kod może zaczynać się tak (zakładamy, że tablica t jest wypełniona literami, a size to długość tablicy):

    int is_double_palindrome(char t[], int size) {
      // tutaj powinien trafić wasz kod
    }

    Przydatny może być kod sprawdzający palindromy z ćwiczeń.

• Zadanie 4 (termin oddania: 28.11 23:59) - Przeczytaj treść zadania 3 (o choince) ze strony smurf. Tutaj znajduje się rozwiązanie tego zadania, ale niestety zawiera ono błędy.

  • Napraw je tak, żeby program działał poprawnie. Upewnij się, że wysokość choinki jest poprawna - w treści zadania narysowana jest choinka dla n=6. (0,5 pkt)

  • Dodaj ramkę wokoło choinki. Porada: zacznij od góry i dołu ramki, następnie dodaj lewy brzeg. Na samym końcu dodaj prawy brzeg. (0,5 pkt)

    Przykładowa choinka z ramką, dla n=5:

    ~~~~~~~~~~~
    |    *    |
    |   ***   |
    |  *****  |
    | ******* |
    |*********|
    |   ***   |
    |   ***   |
    |   ***   |
    ~~~~~~~~~~~

• Zadanie 5 (termin oddania: 05.12 23:59) - Przeczytaj algorytm rozwiązywania równań różnicowych z tej strony. Rozwiąż równanie: a(n) = 7 * a(n - 1) - 12 * a(n - 2) + 2 * n + 1 z warunkami początkowymi a(0) = 2 oraz a(1) = 4. Rozwiązanie możesz wysłać mailem (zdjęcie kartki lub pdf w latexu/wordzie) albo oddać napisane na kartce w poniedziałek 05.12.

• Zadanie 6 (termin oddania: 12.12 23:59) - Napisz kod funkcji liczącej pole trójkąta double triangle_area(double triangle[]). double to typ zmiennoprzecinkowy wysokiej precyzji, (dla przypomnienia float to też typ zmiennoprzecinkowy, ale niższej precyzji). Argument triangle jest tablicą 6-elementową, w której znajdują się współrzędne x i y 3 wierzchołków trójkąta (ABC), tzn w tablicy znajduje się po kolei: Ax, Ay, Bx, By, Cx, Cy. Innymi słowy, triangle[0] to współrzędna x wierzchołka A, triangle[1] to współrzędna y wierzchołka A, itp aż do triangle[5], czyli do współrzędnej y wierzchołka C. Szkielet rozwiązania jest dostępny tutaj, wystarczy uzupełnić TODO. Uruchom rozwiązanie i upewnij się, że daje poprawne wyniki. Proszę nie korzystać z żadnych dodatkowych bibliotek (w tym z biblioteki math.h).

• Zadanie 7 (termin oddania: 19.12 23:59) - Przeczytaj kod z komentarzami z labów - dostępny tutaj. Dla każdej funkcji: dict_init, dict_add, dict_contains, dict_get oraz dict_remove podaj rząd złożoności czasowej pesymistycznej (stała, logarytmiczna, liniowa, kwadratowa, itp) względem liczby elementów w słowniku (czyli względem dict_fill). Dla każdej funkcji podaj jedno zdanie uzasadnienia tej złożoności (nie formalny dowód). Dla chętnych polecam zastanowić się nad złożonościami tych operacji, gdybyśmy w tablicy trzymali elementy posortowane po kluczach.

• Zadanie 8 (termin oddania: 16.01 23:59) - W tablicy mamy dany ciąg liczb: 9, 10, 12, 4, 5, 11, 8, 2, 1, 3, 6, 7, 13. Tablica ta została posortowana przy pomocy algorytmu HeapSort (opisanego w skrypcie). Napisz zawartość tablicy po każdym przestawieniu jej elementów, możesz to zrobić na przykład w arkuszu kalkulacyjnym.

• Zadanie 9 (termin oddania: 23.01 23:59) - Napisz kod funkcji void merge_two_sorted_arrays(int t[], int dest[], int size, int middle), która jest częścią algorytmu MergeSort. Funkcja przyjmuje tablicę t o długości size, której zarówno pierwsza (elementy od 0 do middle-1) oraz druga (elementy od middle do size-1) połowa są posortowane. Funkcja ma za zadanie połączyć dwie posortowane połowy - wynik ma być wpisany do tablicy dest (która też jest o długości size). Rozwiązanie "w miejscu" tzn bez użycia dodatkowej tablicy jest znacznie trudniejsze, w tym zadaniu mi na tym nie zależy.

• Zadanie 10 (termin oddania: 26.01 23:59) - W tablicy mamy dany ciąg liczb: 9, 10, 12, 4, 5, 11, 8, 2, 1, 3, 6, 7, 13. Tablica ta została posortowana przy pomocy algorytmu QuickSort (opisanego w skrypcie). Napisz zawartość tablicy po każdym przestawieniu jej elementów, możesz to zrobić na przykład w arkuszu kalkulacyjnym. Przyjmij, że funkcja FindPivot zawsze wybiera OSTATNI element z podtablicy, a funkcja Partition działa tak, jak jest to opisane w SKRYPCIE. Wklejam tutaj kod funkcji Partition, która robi to samo co ta w skrypcie, ale jest napisana ciut inaczej:

  int Partition(int array[], int left, int right) {
    int pivot_index = FindPivot(array, left, right); // znajdujemy indeks elementu dzielącego (pivotu)
    Swap(array, left, pivot_index); // umieszczamy pivot na początku podtablicy
    pivot_index = left;
    int position_for_pivot = left; // ta zmienna będzie trzymała pozycję ostatniego elementu mniejszego od pivotu
    for (int i = left + 1; i <= right; i++) { // idziemy po wszystkich elementach podtablicy od drugiego do ostatniego
        if (array[i] < array[pivot_index]) { // jeśli znaleziony element jest mniejszy od pivotu, to zamieniamy go z pierwszym elementem większym od pivotu
            position_for_pivot++;
            Swap(array, position_for_pivot, i);
        }
        // jeśli znaleziony element jest większy/równy pivotowi, to na razie zostawiamy go w danym miejscu
    }
    Swap(array, pivot_index, position_for_pivot); // umieszczamy pivot pomiędzy elementami od niego mniejszymi i większymi (a dokładniej - zamieniamy go z ostatnim elementem mniejszym od pivotu - w ten sposób ten element mniejszy od pivotu trafia na początek tablicy, czyli jest po dobrej stronie)
    return position_for_pivot;
  }

Rozwiązania prac domowych i projektu zaliczeniowego są dostępne tutaj.

Przykładowe rozwiązanie tegorocznego kolokwium jest dostępne tutaj.

Materiały dodatkowe:

• lab 3 - Kompilacja, przykładowy program, CLion

• lab 7 - Debugowanie, rekurencja

• lab 10 - Struktury, słownik