# Informatyka Maturalna BBE XIV LO # Lekcja 0 (12.09.2024) ### Zasady zaliczenia * 12 kartkówek w ciągu semestru (liczy się 8 najlepszych); * 12 zadań domowych w ciągu semestru (liczby się 8 najlepszych); * 12 ocen z pracy na lekcji (liczby się 8 najlepszych); * Z powodów czasowych: brak możliwości odrabiania ocen. * Zadania domowe wysyłamy zawsze (o ile nie jest powiedziane inaczej) do środy 23.59 na bartek@cs.uni.wroc.pl, a w tytule maila podajemy "[Klasa XYZ][IMIĘ NAZWISKO] Zadanie domowe NR", gdzie XYZ to nazwa twojej klasy, IMIĘ to twoje imię, NAZWISKO to twoje nazwisko, a NR to numer lekcji. ### Podstawy C++ * Przypomnieliśmy sobie podstawy programowania w C++. Warto przeczytać: * Pierwsze trzy poziomy stąd: https://cpp0x.pl/kursy/Kurs-C++/1 * Wektory: https://eduinf.waw.pl/inf/utils/001_2008/0700.php * Stringi https://www.algorytm.edu.pl/biblioteki/string.html * Przerobiliśmy zadania z podstawowych matur: * ??? * ??? ### Przypomnienie: Wczytywanie danych z pliku ```cpp #include <fstream> // dodajemy do main // ... // w main piszemy ifstream plik("dane.txt"); // gdzie "plik" to nasza ulubiona nazwa zmiennej, a "dane.txt" to nazwa pliku którego zawartość chcemy wczytać. // UWAGA! Plik "dane.txt" powinien być w tym samym miejscu co main.cpp // Od teraz zamiast pisać "cin" piszemy "plik". ``` ### Przykład rozwiązania zadania: Matura 2024 Czerwiec (Zad 3) ```cpp #include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <map> using namespace std; //---------- POM ------------------ vector<string> wczytaj_dane() { ifstream plik("slowa.txt"); vector<string> v(1000); for(int i = 0; i < v.size(); i++) plik >> v[i]; return v; } void wypisz(vector<string> v) { for(auto s: v) cout << s << "\n"; } //---------- ZAD 1 ------------------ bool czy_zawiera_kcost(string s) { for(int i = 0; i < s.size()-2; i++) { if(s[i] == 'k' && s[i+2] == 't') return true; } return false; } int zad1(vector<string> dane) { /*int licz = 0; for(auto s : dane) { if(czy_zawiera_kcost(s)) licz++; } return licz;*/ return count_if(dane.begin(), dane.end(), czy_zawiera_kcost); } //---------- ZAD 2 ------------------ string zakoduj(string s) { string w = ""; for(int i = 0; i < s.size(); i++) { int kod = s[i] + 13; if(kod > 'z') kod -= 26; w += (char) kod; } return w; } bool czy_ciekawa(string s) { string x = zakoduj(s); reverse(x.begin(), x.end()); return (s == x); } void zad2(vector<string> &dane) { string odp = ""; int licz = 0; for(auto s: dane) { if(czy_ciekawa(s)) { licz++; if(s.size() > odp.size()) odp = s; } } cout << "3.2) Jest ich " << licz << " a najdluzsze to " << odp << "\n"; } //---------- ZAD 3 ------------------ map<char, int> slownik_wystapien_liter(string s) { map<char, int> mapa; for(auto litera: s) mapa[litera]++; return mapa; } bool pewna_litera_przynajmniej_pol(string s) { map<char,int> mapa = slownik_wystapien_liter(s); for(char litera = 'a'; litera <= 'z'; litera++) { if(mapa[litera] * 2 >= s.size()) return true; } return false; } void zad3(vector<string> &dane) { cout << "Zad 3.3)\n"; for(auto s: dane) { if(pewna_litera_przynajmniej_pol(s)) cout << s << "\n"; } } int main() { vector<string> dane = wczytaj_dane(); cout << "Zad 3.1) " << zad1(dane) << "\n"; zad2(dane); zad3(dane); return 0; } ``` # Lekcja 1 (19.09.2024) ### Przypomnienie: Algorytm Euklidesa Przypomnieliśmy sobie jak działa algorytm Euklidesa: ```cpp int nwd(int x, int y) { if(y == 0) return x; // bo nwd jakiejś liczby i 0 to zawsze ta liczba else return nwd(y, x%y); // korzystamy z własności nwd(x,y) = nwd(y, x mod y); patrz wikipedia } ``` Warto pamiętać o tym, że jego złożoność jest *logarytmiczna* względem x+y. Dowód poprawności działania: https://pl.wikipedia.org/wiki/Algorytm_Euklidesa ### Przypomnienie: Suma cyfr * Przypomnieliśmy sobie jak obliczać sumę cyfr danej liczby ```cpp int suma_cyfr(int n) { int s = 0; // początkowa suma cyfr to 0 while(n > 0) { // dopóki mamy jeszcze jakieś cyfry do przetworzenia to... s += n % 10; // dodaj ostatnią cyfrę n do wyniku n /= 10; // skróć n o ostatnią cyfrę } return s; // zwróć odp. } ``` * Przypomnieliśmy sobie jak pisać funkcje w C++ * https://cpp0x.pl/kursy/Kurs-C++/Poziom-2/Funkcje-pierwsze-starcie/291 * https://drzewniak.slupsk.pl/~ks/c/c_033.html * https://technikprogramista.pl/kurs/cpp/lekcja/cpp-funkcje/ ### Testowanie programów w C++ Przypomnieliśmy sobie jak pisać proste testy w C++ (asserty). Przykład: ```cpp // funkcja do przetestowania int czy_parzysta(int n) { return n % 2 == 0; } // niżej w main piszemy kilka przypadków testowych assert(czy_parzysta(2) == true); assert(czy_parzysta(4) == true); assert(czy_parzysta(3) == false); // mozna po prostu assert(czy_parzysta(2)); // oraz assert(!czy_parzysta(3)); ``` Testy pomagają sprawdzać poprawność kodu (ale nie gwaratują jej w 100%) i to czy w trakcie modyfikacji programu nie poprawiliśmy czegoś co działa dobrze na kod który działa źle (co się często zdarza w stresie i upale na maturze). Tu inny przykład: ```cpp int ostatnia_cyfra(int n) { return n % 10; } // ... niżej w mainie ... assert(ostatnia_cyfra(123) == 3); assert(ostatnia_cyfra(42) == 2); assert(ostatnia_cyfra(69) == 9); ``` Tu jeszcze inny przykład: ```cpp // Uwaga: kod nie działa dla napisów o dłg < 2 string pierwsze_dwie_litery(string s) { string odp = ""; odp += s[0]; odp += s[1]; return odp; } // ... niżej w mainie ... assert(pierwsze_dwie_litery("kajak") == "ka"); ``` ### Zadania maturalne z lekcji * Rozwiązaliśmy zad 5 stąd: https://arkusze.pl/matura-informatyka-2014-maj-poziom-podstawowy/ ```cpp #include <bits/stdc++.h> using namespace std; bool wielokrotnosci(int x, int y) { return (x % y == 0 || y % x == 0); } void zad1(vector<int> A, vector<int> B) { int ile = 0; for(int i = 0; i < A.size(); i++) { if(wielokrotnosci(A[i], B[i])) ile++; } cout << "a) " << ile << "\n"; } int nwd(int x, int y) { if(y == 0) return x; else return nwd(y, x % y); } void zad2(vector<int> A, vector<int> B) { int ile = 0; for(int i = 0; i < A.size(); i++) { if(nwd(A[i], B[i]) == 1) ile++; } cout << "b) " << ile << "\n"; } int sumacyfr(int x) { int s = 0; while(x > 0) { s += x % 10; x /= 10; } return s; } void zad3(vector<int> A, vector<int> B) { int ile = 0; for(int i = 0; i < A.size(); i++) { if(sumacyfr(A[i]) == sumacyfr(B[i])) ile++; } cout << "c) " << ile << "\n"; } int main() { assert( wielokrotnosci(7, 5) == false ); assert( wielokrotnosci(7, 14) == true ); assert( wielokrotnosci(14, 7) == true ); assert( nwd(3,5) == 1 ); assert( nwd(2, 6) == 2 ); assert( nwd(4, 10) == 2); assert( sumacyfr(123) == 6); assert( sumacyfr(42) == 6); assert( sumacyfr(0) == 0); vector<int> A(1000), B(1000); ifstream plik("PARY_LICZB.TXT"); for(int i = 0; i < 1000; i++) plik >> A[i] >> B[i]; zad1(A, B); zad2(A, B); zad3(A, B); return 0; } ``` * Rozwiązaliśmy zad 4 stąd: https://arkusze.pl/matura-informatyka-2013-maj-poziom-podstawowy/ ```cpp #include <bits/stdc++.h> using namespace std; int ile_parzystych_napisow(vector<string> v) { int ile = 0; for(int i = 0; i < v.size(); i++) { if(v[i].size() % 2 == 0) ile++; } return ile; } int ile_jedynek(string s) { int ile = 0; for(int i = 0; i < s.size(); i++) { if(s[i] == '1') ile++; } return ile; } int ile_napisow_tyle_zer_co_jeden(vector<string> dane) { int ile = 0; for(int i = 0; i < dane.size(); i++) { int j = ile_jedynek(dane[i]); if(j == (dane[i].size() - j)) ile++; } return ile; } void zad3(vector<string> dane) { int same_zera = 0, same_jedynki = 0; for(int i = 0; i < dane.size(); i++) { int j = ile_jedynek(dane[i]); if(j == dane[i].size()) same_jedynki++; if(j == 0) same_zera++; } cout << "C) same zera " << same_zera << " same jedynki " << same_jedynki << "\n"; } int ile_napisow_dlg_k(vector<string> dane, int k) { int ile = 0; for(int i = 0; i < dane.size(); i++) { if(dane[i].size() == k) ile++; } return ile; } int main() { vector<string> dane(1000); ifstream plik("napisy.txt"); for(int i = 0; i < 1000; i++) plik >> dane[i]; cout << "A) " << ile_parzystych_napisow(dane) << "\n"; cout << "B) " << ile_napisow_tyle_zer_co_jeden(dane) << "\n"; zad3(dane); for(int i = 2; i <= 16; i++) { cout << "Napisow o dlg " << i << " jest " << ile_napisow_dlg_k(dane, i) << "\n"; } return 0; } ``` Uwagi do zadania z matury 2013: * Zamiast pisać kod w stylu ```cpp int ile = 0; for(int i = 0; i < dane.size(); i++) { if(warunek(dane[i])) ile++; } return ile; ``` można użyć funkcji count_if (https://en.cppreference.com/w/cpp/algorithm/count) i napisać ```cpp return count_if(dane.begin(), dane.end(), warunek); ``` * Zamiast przechodzić 16 razy przez tablicę i liczyć ile jest napisów długości k, można by było rozwiązać to w ten sposób: ```cpp int tab[17] = {0}; for(int i = 0; i < dane.size(); i++) { tab[ dane[i].size() ]++; } for(int i = 2; i <= 16; i++) { cout << "Napisow o dlg " << i << " "; cout << "jest " << tab[i] } ``` Jest to sporo szybsze, ale na maturalne potrzeby nie ma to znaczenia. ### Ogłoszenie: Zadania domowe + Kartkówka * **Zadanie domowe** do 25.09.2024 23:59. * Zadanie 5. https://arkusze.pl/matura-informatyka-2009-maj-poziom-podstawowy/ (ok 12min roboty) ```cpp #include <bits/stdc++.h> using namespace std; int czy_pierwsza(int n) { if(n < 2) return false; else if(n == 2) return true; for(int i = 2; i*i <= n; i++) { if(n % i == 0) return false; } return true; } bool czy_kwadrat_pierwszej(int n) { int p = (int) sqrt(n); return (p*p == n) && czy_pierwsza(p); } vector<int> wczytaj_dane() { ifstream plik("liczby.txt"); vector<int> dane(500); for(int i = 0; i < 500; i++) plik >> dane[i]; return dane; } void rozw(vector<int> dane) { ofstream plik("zad_5.txt"); for(int n : dane) { if(czy_kwadrat_pierwszej(n)) plik << n << "\n"; } } int main() { vector<int> dane = wczytaj_dane(); rozw(dane); return 0; } ``` * Zadanie 4. https://arkusze.pl/matura-informatyka-2010-maj-poziom-podstawowy/ (ok 12min roboty) ```cpp #include <bits/stdc++.h> using namespace std; vector<string> wczytaj_dane() { ifstream plik("dane.txt"); vector<string> dane(1000); for(int i = 0; i < 1000; i++) plik >> dane[i]; return dane; } bool czy_palindrom(string a) { string b = a; reverse(b.begin(), b.end()); return a == b; } void rozw(vector<string> dane) { ofstream plik("zadanie4.txt"); for(string s : dane) { if(czy_palindrom(s)) plik << s << "\n"; } } int main() { vector<string> dane = wczytaj_dane(); rozw(dane); return 0; } ``` * Zadanie 4. https://arkusze.pl/matura-informatyka-2011-maj-poziom-podstawowy/ (ok 25min roboty) ```cpp #include <bits/stdc++.h> using namespace std; vector<string> wczytaj_dane() { ifstream plik("hasla.txt"); vector<string> dane(200); for(int i = 0; i < dane.size(); i++) plik >> dane[i]; return dane; } bool czy_palindrom(string a) { string b = a; reverse(b.begin(), b.end()); return a == b; } void rozw_a(vector<string> dane) { int parz = 0, nparz = 0; for(string s : dane) { if(s.size() % 2 == 0) parz++; else nparz++; } ofstream plik("wynik4a.txt"); plik << "Napisow o parzystej dlg jest " << parz << "\n"; plik << "Napisow o nieparzystej dlg jest " << nparz << "\n"; plik.close(); } void rozw_b(vector<string> dane) { ofstream plik("wynik4b.txt"); for(string s: dane) { if(czy_palindrom(s)) plik << s << "\n"; } plik.close(); } bool czy_dwa_sasiednie_kody_220(string s) { for(int i = 0; i < s.size()-1; i++) { if((s[i]+s[i+1]) == 220) return true; } return false; } void rozw_c(vector<string> dane) { ofstream plik("wynik4c.txt"); for(string s: dane) { if(czy_dwa_sasiednie_kody_220(s)) plik << s << "\n"; } plik.close(); } int main() { vector<string> dane = wczytaj_dane(); rozw_a(dane); rozw_b(dane); rozw_c(dane); return 0; } ``` * Zadanie 4. https://arkusze.pl/matura-informatyka-2012-maj-poziom-podstawowy/ (ok 25min roboty) ```cpp #include <bits/stdc++.h> using namespace std; vector<int> wczytaj_dane() { ifstream plik("cyfry.txt"); vector<int> dane(1000); for(int i = 0; i < dane.size(); i++) plik >> dane[i]; return dane; } bool czy_parzysta(int n) { return n % 2 == 0; } int zad_a(vector<int> dane) { return count_if(dane.begin(), dane.end(), czy_parzysta); } int suma_cyfr(int n) { int s = 0; while(n > 0) { s += n % 10; n /= 10; } return s; } bool mniejsza_suma_cyfr(int x, int y) { return suma_cyfr(x) < suma_cyfr(y); } void zad_b(vector<int> dane) { cout << "b) Liczba o najmniejszej sumie cyfr to "; cout << *min_element(dane.begin(), dane.end(), mniejsza_suma_cyfr); cout << "\nLiczba o najwiekszej sumie cyfr to "; cout << *max_element(dane.begin(), dane.end(), mniejsza_suma_cyfr); } bool czy_rosnaca(int n) { if(n < 10) return true; else { int ostatnia_cyfra = n % 10; int przedostatnia = (n / 10) % 10; if(przedostatnia >= ostatnia_cyfra) return false; else return czy_rosnaca(n / 10); } } void zad_c(vector<int> dane) { cout << "\nc)\n"; for(int n: dane) { if(czy_rosnaca(n)) cout << n << "\n"; } } int main() { vector<int> dane = wczytaj_dane(); cout << "a) " << zad_a(dane) << "\n"; zad_b(dane); zad_c(dane); return 0; } ``` * Na kolejnej lekcji będzie nasza pierwsza kartkówka. Warto przypomnieć sobie algorytm Euklidesa oraz jak obliczać sumę cyfr dalej liczby. # Lekcja 2 (26.09.2024) ### Przypomnienie: Czy dane słowo jest palindromem? ```cpp bool czy_palindrom(string a) { for(int i = 0; i <= a.size()/2; i++) { if(a[i] != a[a.size()-i-1]) return false; } return true; } ``` Alternatywnym rozwiązaniem jest użyć wbudowanej funkcji reverse. ```cpp bool czy_palindrom(string a) { string b = a; reverse(b.begin(), b.end()); return a == b; } ``` ### Przypomnienie: Czy dane słowa są anagramami? Kluczowa jest obserwacja, że a i b są anagramami wtedy i tylko wtedy gdy mają dokładnie tyle samo tych samych liter. Pierwsze rozwiązanie jest trochę wolniejsze, ale dużo szybsze do napisania. Wystarczy że posortujemy a i b i je przyrównamy. ```cpp bool czy_anagramy(string a, string b) { sort(a.begin(), a.end()); sort(b.begin(), b.end()); return a==b; } ``` Innym, efektywniejszym, ale dłuższym do napisania rozwiązaniem jest użycie ,,tablicy zliczeń''. Tworząc tablicę na 26 znaków (rozmiar alfabetu łacińskiego), będziemy przechodzić po napisach a i b, oraz stopniowo aktualizować wpis na odpowiednim miejscu tablicy zliczeń (zwiększając go o 1 czytając litery napisu a oraz zmniejsząc o 1 czytając litery napisu b). Jeżeli na samym końcu tablica zliczeń będzie wypełniona samymi zerami, możemy być pewni, że a i b mają tyle samo tych samych liter, więc są anagramami. ```cpp bool czy_anagramy(string a, string b) { int tab[26] = {0}; // tablica zliczeń for(int i = 0; i < a.size(); i++) { // przechodzimy po słowie a... int nr = a[i] - 'a'; // numer i-tej litery w a tab[nr]++; // zwiększamy odpowiednią pozycję o jeden } for(int i = 0; i < b.size(); i++) { // przechodzimy po słowie b... int nr = b[i] - 'a'; // numer i-tej litery w b tab[nr]--; // zmiejszamy odpowiednią pozycję o jeden } // sprawdzamy czy tablica tab jest wypelniona samymi zerami for(int i = 0; i < 26; i++) { if(tab[i] != 0) return false; // znalezlismy blad! } return true; // jesli sa same zera to zwroc true } ``` ### Przypomnienie: Czy podana liczba jest pierwsza? ```cpp bool czy_pierwsza(int n) { if(n < 2) return false; // liczby mniejsze od 2 nie sa pierwsze // szukamy nietrywialnego dzielnika n, wiemy ze jesli taki jest to jest <= pierwiastek(n) for(int i = 2; i*i <= n; i++) { if(n % i == 0) return false; // znalezlismy nietrywialny dzielnik wiec n nie jest pierwsza } return true; // jesli tutaj doszlismy to zadnych nietrywialnych dzielnikow nie bylo, zatem liczba n jest pierwsza } ``` Czemu wystarczy szukać dzielników tylko do $\sqrt{n}$? Załóżmy, że n nie jest pierwsza. Wtedy mogę zapisać ją jako $a \cdot b$ dla pewnych a i b (gdzie obie te liczby są różne od 1 oraz od n). Twierdzę, że któraś z tych liczb jest mniejsza równa pierwiastkowi z $n$. Gdyby tak nie było to wtedy zarówno $a$ oraz $b$ są $> \sqrt{n}$. Ale wtedy $a \cdot b > \sqrt{n} \cdot \sqrt{n} = n$, co przeczy temu, że $n = a \cdot b$. ### Przypomnienie: Sumowanie kodów ascii danego napisu. Sumowanie kodów ascii podanego napisu. ```cpp bool suma_kodow_ascii_liter(string a) { int suma = 0; for(int i = 0; i < a.size(); i++) { suma += a[i]; } return suma; } ``` Obliczanie numeru danej litery w alfabecie. ```cpp bool nr_litery(char literka) { return (int) literka - 'a'; } ``` ### Praca na lekcji: Zadanie ,,Ciekawe Napisy'' z Maja 2014. ```cpp #include <bits/stdc++.h> using namespace std; vector<string> wczytaj_dane() { ifstream plik("NAPIS.TXT"); vector<string> dane(1000); for(int i = 0; i < dane.size(); i++) plik >> dane[i]; return dane; } bool czy_pierwsza(int n) { if(n < 2) return false; for(int i = 2; i * i <= n; i++) { if(n % i == 0) return false; } return true; } int suma_kodow_ascii(string s) { int suma = 0; for(char c: s) suma += c; return suma; } bool czy_napis_pierwszy(string s) { return czy_pierwsza(suma_kodow_ascii(s)); } void zadA(vector<string> &dane) { cout << "A) " << count_if(dane.begin(), dane.end(), czy_napis_pierwszy) << "\n"; } bool czy_napis_rosnacy(string s) { for(int i = 0; i < s.size()-1; i++) { if(s[i+1] <= s[i]) return false; } return true; } void zadB(vector<string> &dane) { cout << "\nB)\n"; for(string s: dane) { if(czy_napis_rosnacy(s)) cout << s << "\n"; } } void zadC(vector<string> &dane) { unordered_map<string, int> zlicz; cout << "\nC)\n"; for(string s: dane) { if(zlicz[s] == 1) cout << s << "\n"; zlicz[s]++; } } int main() { vector<string> dane = wczytaj_dane(); zadA(dane); zadB(dane); zadC(dane); return 0; } ``` ### Kartkówka 1 Kartkówka 1 z rozwiązaniem: https://www.dropbox.com/scl/fi/6h7u2jzgmw714yrynb131/kartk-wka-1-rozwi-zana.pdf?rlkey=xa5sofgkwenx2tcukf92eawop&dl=0 ### Ogłoszenia: Zadania domowe i kolejna kartkówka * Przypomnieć sobie jak działał szyfr Cezara i rozwiązać następujące trzy zadania (tam gdzie jest napisać pseudokod, napisz kod w C++). * Szyfr Skokowy: http://code.kopernik-leszno.pl/data/files/442/31.pdf * Szyfr Beaufora: http://code.kopernik-leszno.pl/data/files/461/12.pdf * Szyfr kolumnowy https://arkusze.pl/maturalne/informatyka-2019-czerwiec-matura-rozszerzona.pdf Z racji tego, że klasa 4B ma wycieczkę, termin zadania przedłużam do niedzieli 06.10.2024 23:59. Zadania wysyłamy jak zwykle mailem, na bartek@cs.uni.wroc.pl (w tytule maila dopisz swoje imię, nazwisko oraz "Zadanie domowe 2"). Kartkówka (co warto umieć): * Przypomnij sobie w jaki sposób sprawdzać czy liczba jest pierwsza w czasie O(pierwiastek(n)) * Przypomnij sobie w jaki sposób sprawdzić czy dwa napisy są anagramami. # Lekcja 2 (4A2, 4B) Umówiliśmy licencje freeware, shareware, adware, GNU GPL. Rozwiązaliśmy kilka zadań maturalnych na ten temat i napisaliśmy kartkówkę. ![461261655_550027510720710_1424268175585559284_n_11zon](https://hackmd.io/_uploads/r18W6S2A0.jpg) Przerobiliśmy zadania maturalne stąd: https://www.dropbox.com/scl/fi/lbigj41mtxvpbe4qip0kg/Licencje.zip?rlkey=pfcnqaw8skb1tlxud7gyuzj2t&dl=0 # Lekcja 3 (Na razie tylko 4A2) Przerobiliśmy sobie zadanie Szyfr Beaforta. http://code.kopernik-leszno.pl/data/files/461/12.pdf ![462550243_424774593622614_4773106610788092031_n](https://hackmd.io/_uploads/BJLJsfHkJx.jpg) ![462368128_1231753448029823_5079641732316863875_n](https://hackmd.io/_uploads/SJ1lsMHk1x.jpg) W trakcie lekcji robiliśmy zadanie Szyfr Cezara z matury 2016 PR (Zad 6). ## Zadanie domowe Zadania domowe. Oba do napisania w C++ i do wysłania do mnie mailowo. Zadanie 3 Kodowanie https://arkusze.pl/maturalne/informatyka-2015-przykladowy-arkusz-cke-rozszerzona.pdf Zadanie 4 Szyfr https://arkusze.pl/maturalne/informatyka-2012-maj-matura-rozszerzona-2.pdf Termin oddania: niedziela 20.10.2024 23:59