klasa 1Cp 2019/20 - informatyka - część M.Ś.

o bloku olimp. (z inf.!)

mój system oceniania lista zadań kartkówki, sprawdziany, poprawy, ... fajne imprezy (Polecam!!)

online C++ compiler (W okienku wpisuje się / wkleja program (wystarczy oczywiście zmieniać tylko to, co w nawiasach klamrowych) i... naciska "Execute" pod spodem (w razie potrzeby podając to, ma wprowadzić użytkownik, w okienku "Stdin Inputs")).

Obu grupom polecam niezmiennie zadania na Solvie!

materiały z pozalekcyjnych spotkań (minionych i ew. dalszych): lingwistycznych (stały termin - piątki 15.15 - ale czy 26.6 również?) matematycznych (najbliższe spotkanie - ??)

śpiewający krab (Kliknij na zieloną flagę nad skorupiakiem, pooglądaj kod, dopisz, zmieniaj, eksperymentuj!)

zadanka z arytm. modularnej do poćwiczenia (specjalnie dla...! :)) A tutaj jeszcze jedno opisanie własności Z_n!

Obie grupy zachęcam do robienia zadanek z https://themis.ii.uni.wroc.pl/JAG20A#2 (hasło to słowo "mod" z dołączonym nrem bieżącego roku bez spacji), konkretnie zad. BUYCUR, CTABLES6 i ACPP124 powinny być już w zasięgu wszystkich, a grupa 1 powinna powalczyć również z ACPP126, ACPP128, SPR2014_5 i CTABLES2D4, REVMOD_EZ to zaś nasz programik z lekcji i zadania dom. - możecie sprawdzić, czy wejdzie na Themisa (ale na pewno potrzebne są instrukcje wejścia-wyjścia z C).

Gr. 1 na 15 VI miała:

zapisać (w C++) procedury:
- Merge (przypominam po raz kolejny - taką, że jej parametrami (oprócz tablicy, której fragmenty scalamy) są liczby a, b i c mówiące, że scalamy (z założenia posortowane) fragmenty o nrach od a do b-1 i od b do c-1 - czyli np. wywołanie Merge(t, 1, 3, 8) dla t={9, 4, 7, 1, 2, 5, 6, 8, 3} powoduje, że tablica przyjmie postać {9, 1, 2, 4, 5, 6, 7, 8, 3});
- MergeSortR (sortującą przez rekurencyjne scalanie);
- MergeSortW (sortującą przez scalanie wstępująco);
dokonać analizy obu wariantów MergeSorta dla tablic długości 10 i 11 (analiza = ustalenie kolejnych scaleń (w wypadku wersji rekurencyjnej - na podstawie drzewka) i liczb przepisywanych elementów) ORAZ wypisać kolejne scalenia z filmiku stąd i przemyśleć, czy równie dobrze w ukazanym tam wariancie algorytmu mogłyby być wykonywane nieco inaczej;
przemyśleć złożoności (pesymistyczne) Merge'a i obu wersji MergeSorta;
wrzucić do zadań na MS Teams plik cpp z trzema procedurami z pktu 1 i ładnie zapisaną odpowiedź do pktu 2 (powinno łatwo dać się odczytać, jakie są kolejne scalenia i ile przepisań elementów jest potrzebnych w każdym z 4 przypadków oraz jakie scalenia wykonują kolejno tancerze).

Nadal zachęcam także do zapisania sortowania przez jednoczesny wybór min. i maks.

Dla przypomnienia - już dawno temu należało:

zapisać algorytm Merge jako procedurę, której argumentami będą: jednowym. tablica i dwa jej indeksy p i k (p≤k), przy czym fragmenty tej tablicy od nru p do nru [(p+k)/2] oraz od [(p+k)/2]+1 do k są posortowane, a w wyniku jej działania posortowany będzie cały fragment od nru p do nru k; przykład dla tablicy (4, 5, 1, 2, 3, 8, 4, 7, 7, 4), p=2 i k=8 tablica zmieni się na (4, 5, 1, 2, 3, 4, 7, 7, 8, 4);

zastanowić się, jak można by zapisać (a może nawet zapisać?) rekurencyjnie któreś z elementarnych sortowań.

Na 11 V zadane było:

napisać procedury: InsertSort w wariancie liniowym i binarnym (obowiązkowo - ustaliliśmy z Panią Prof., że powinniście to przećwiczyć!) oraz SelectSort (przykładowa tablica do przetestowania wstawiania: {4, 3, 2, 3, 4, 1, 5}; przypominam, że ew. problemy z binsearchem może pomóc rozwiązać video z wykładem p. Milczka);

zastanowić się, czy w SelectSorcie da coś wyszukanie w każdym przebiegu minimum i maksimum (i oczywiście ustawienie ich na właściwych pozycjach);

zastanowić się, jak bez sortowania stwierdzić, ile zamian wykonana bubble sort (w dowolnej wersji); chodzi o wymyślenie sposobu, takiego żeby patrząc np. na ciąg (9, 4, 3, 7, 5, 6, 2, 4, 8, 1, 3, 5, 1, 7) oczami, podać tę liczbę, no i jak zawsze interesuje mnie też analiza złożoności; fajnie by było, gdyby ktoś zapisał to (jako funkcję?) w C++;

odgadnąć w miarę prosty wzorek na ost. sumę cyfr (bez żadnej rekurencji, tylko kilka matematycznych działań), a jakby ktoś udowodnił... :)

Wszyscy powinni mieć gotowy do okazania i wyjaśnienia program z sort. bąbelkowym po pierwszym ulepszeniu, a zachęcam do zmierzenia się z Ultimate Bubble Sort (Ⓒ M$) - czyli sort. mieszanego.

Wciąż można ponadto (i wciąż polecam!):

pomyśleć rekurencyjnie o naszych sortowaniach (ktoś coś?),

napisać szybkie potęgowanie bez rekurencji (à la schemat Hornera lub z algorytmem div-mod),

pomyśleć o możliwie sprawiedliwym generowaniu liczb [pseudo]losowych z zakresu większego niż [0, 32767],

pobadać własności ostatecznej sumy cyfr,

udowodnić hipotezę Collatza (to raczej żart!).

Grupa 2 na 15 VI powinna:

wypełnić wielokropki w tej procedurze sortującej, tak żeby algorytm działał optymalnie, i dopisać zliczanie porównań i zamian;

mieć sprawdzone (teoretycznie oraz empirycznie - programem lub ręcznie), jaka jest minimalna, a jaka maksymalna liczba porównań i zamian wykonywanych w sorcie bąbelkowym (jak zwykle - n elementów): O)ryginalnym, jaka 1) po ulepszeniu w powyższej procedurze, a jaka 2) po ulepszeniu, które ukazane jest w filmiku stąd;

mieć jakiś pomysł, jak bez sortowania stwierdzić, ile zamian wykona BubbleSort (w dowolnym wariancie) dla danego ciągu (chodzi o wymyślenie sposobu, takiego żeby patrząc np. na ciąg (9, 4, 3, 7, 5, 6, 2, 4, 8, 1, 3, 5, 1, 7) oczami, podać tę liczbę, nie próbując sortować);

zastanowić się, jak zrealizować sortowanie bąbelkowe (w wariancie bez żadnych ulepszeń) rekurencyjnie.

Można też postarać się ustalić, jaki jest najgorszy układ danych dla sortowania przez wybór. Możemy zrobić konkurs na przykład tablicy (długości n), która będzie sortowana najdłużej.

Tutaj, w jaki sposób pracujemy do 17 VI.

Na 20.04 mieliście (i proszę to nadrobić, kto się jeszcze nie wywiązał, wrzucając do zadań w MŚ Teams wszystko, co jest fuksją, czyli programik (plik cpp) z funkcją c (obliczającą wyraz ciągu C.) oraz plik (z jakiegoś edytora lub zdjęcie) z oboma drzewkami wywołań):
- zrobić zad. ŁÓŚ stąd;
- sprawdzić (teoretycznie, na papierze, rysując drzewko wywołań, oraz na komputerze - tak, jak robiliśmy to na lekcji), ilu wywołań wymaga obliczenie własnej szczęśliwej cyfry.
No i nadal chciałbym, żebyście umieli szybkie potęgowanie, czyli w szczególności wiedzieli, jak uzupełnić definicje wszystkich czterech podanych tu funkcji obliczających potęgę o wykładniku nat. (dla wygody definicji zakładamy, że 0⁰ to...), i potrafili narysować drzewka wywołań każdej z nich przy obliczaniu 2⁹).
Gdyby wciąż były z tym trudności, proszę koniecznie o kontakt!

Nadal też zachęcam, żeby:
- pomyśleć, jaka jest najmniejsza liczba wymagająca 3, 4, 5, 6 wywołań, aby rekurencyjnie obliczyć jej osc;
- zaprogramować odpowiednią pętlę, która dla wczytanej daty powie, jaka jest szczęśliwą cyfra osoby, która się wtedy urodzi[ła], oraz osoby urodzonej o 1, 2, ..., 33 dni później; powiedzmy, że wystarczy, żeby program działał dla dat z XX i XXI wieku, ale można zrobić go jeszcze ogólniejszym, a może sobie trochę ułatwić, np, założyć, że podana data będzie z Waszego rocznika;
- spróbować zapisać w miarę prosty wzór na osc (bez rekurencji!), może również (*) spróbować go udowodnić?

Więcej ciekawych(!) materiałów (dla obu grup!) wkrótce.
Jak zawsze można pisać, gdyby ktoś potrzebował pomocy, wyjaśnień, zadań itp. - W zasadzie w dowolnej sprawie można pisać! :)

PRZED NASTANIEM WIRUSA:

Grupa poniedziałkowa na 9 III miała:

zrobić/dokończyć zad. 36, 37 i 42 z www.math.uni.wroc.pl/~msliw/lista2e1718.pdf;

umieć już Z34 i 40-43 z www.math.uni.wroc.pl/~msliw/lista2e1718.pdf (Uwaga: Z43 nie jest na programowanie, a samo myślenie (rozumienie rekurencji)! Komputerem można (i warto!) sprawdzać tylko swe przypuszczenia) oraz rozumieć przykłady rekurencji, które podawałem przed feriami, oraz treści z https://inf.ug.edu.pl/~piotao/old/manta/Programowanie/rekurencja.htm.

Może wrócimy jeszcze do tego, co zadawałem przed feriami, czyli:

przemyśleć, jak użyć gotowych funkcji silnia i potęga do rozwiązania ZF z listy oraz czy ich użycie wpłynie na czas działania programu (tzn. czy nie okaże czasem, że używając funkcji, zmuszamy komputer do niepotrzebnych w danym zadaniu obliczeń;

napisać funkcję (czy procdurę?) wypisującą wszystkie naturalne dzielniki argumentu (uwaga: algorytm powinien mieć złożoność pierwiastkową, więc trudno będzie wypisać je w kolejności rosnącej - ale da się - masz pomysł jak?).

Na liście jest dużo nowych zadanek, z których nie wszystkie przerobimy wspólnie, więc można (i warto!) ćwiczyć samemu - ze stron 3-4 w Waszym zasięgu powinny już być Z14.e-f, i, k, m-n.

No i wciąż można zabłysnąć pomysłem na jakiś lepszy algorytm dla wypisywania w kolejności malejącej wszystkich liczb czterocyfrowych podzielnych przez podane n (czyli np. dla n=2019 wypisującego 8076, 6057, 4038 i 2019).

Tutaj jedno z pierwszych zad. dom. A tu zadanka z listy: Z6, Z7 (w wersji dającej błędny wynik - wszyscy wiedzą już chyba dlaczego i jak to poprawić? :>), Z14.ł, funkcja licząca dzielniki.

Grupa środowa na 11 III miała:

spróbować zapisać szybkie potęgowanie iteracyjnie;

nadal mieć napisany programik, który dla zadanego c₀ (początkowego wyrazu ciągu Collatza) stwierdzi, jaki numer ma pierwsza występująca w tym ciągu jedynka, i zastanowić się, czy opłaca się tu użyć zdefiniowanej przez nas funkcji c.

zapisać rekurencyjnie funkcję sumacyfr, która dla podanej jako argument liczby naturalnej obliczy... sumę jej cyfr, ALE REKURENCYJNIE! Wskazówka i cd. zadania.

Przypominam, że już przed feriami powinniście byli:

umieć i mieć zrobione Z34 i 36-43 z www.math.uni.wroc.pl/~msliw/lista2e1718.pdf, wszystko z https://eduinf.waw.pl/inf/utils/010_2010/0215.php oraz https://inf.ug.edu.pl/~piotao/old/manta/Programowanie/rekurencja.htm i stworzyć (w C++) tablicę złożoną z kolejnych liczb Fibonacciego (wiadomo, że szybko przekroczą wszelkie zakresy, więc można brać je mod 1234567890); jakie są wady, a jakie zalety takiego ich zapisania w stosunku do rozwiązania iteracyjnego z artykułu?

dokończyć programik znajdujący odwrotność danego a modulo dane n (rozszerzonym) algorytmem E. (Wszystko jest tam OK, tylko trzeba się wczytać!... :)) oraz zastanowić się, a NASTĘPNIE sprawdzić, jak (i dlaczego) zadziała dla liczby nieodwracalnej;

pomyśleć nad dowodem poprawności użytego przez siebie algorytmu obliczania NWD wielu liczb;

zrobić 1D (oczywiście z próbą udowodnienia odpowiedzi!);

dostrzec, że ta piosenka przedstawia ten sam problem co stwierdzenie: Aby zrozumieć rekurencję, trzeba najpierw zrozumieć rekurencję.

Program o skalowaniu obrazu omówimy już wspólnie, bo nie warto chyba tracić na niego więcej czasu, ALE proszę zastanowić się (przeliczyć?), jaka powinna być odpowiedź dla danych 100000000000000000 100000000000000001 249999999999999999 987654321987654321.
Na lekcji planuję omówić jeszcze Z13c, a pozostałe zadanka do nru 27 można (warto) sobie przejrzeć (przemyśleć, napisać?), w ramach treningu - powinny być już w Waszym zasięgu (chociaż są wśród nich łatwiejsze i trudniejsze, a niektórych nie wiem, czy zrozumiecie polecenie).

Zabawy ze zmiennymi na kartkówkę: zmienne1 i zmienne2. (Przypominam, że tablicę w C++ przekazuje się funkcjom, podając samą jej nazwę, a mimo to jest to przekazywanie przez zmienną, taka ciekawostka!) A tutaj to, na czym ćwiczyliśmy na lekcji.