Informatyka 2

Film omawia stosowanie algorytmów zachłannych na przykładzie wydawania reszty przy użyciu minimalnej liczby monet.

Infografika omawia różne sposoby porządkowania zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru.

W filmie umówiono trzy podstawowe algorytmy sortowania (bąbelkowe, przez wstawianie i przez prosty wybór) oraz przedstawiono ich działanie na przykładach.

 karty © Francesco Abrignani/Shutterstock.com

Film powtórzeniowy, prezentujący sortowanie przez proste wybieranie realizowane w Pythonie.

Zdefiniuj funkcję trzy(a, b, c), której wynikiem jest największa z trzech liczb podanych jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji trzy(1, 9, 12) jest 12.
• Wynikiem funkcji trzy(13, 4, 12) jest 13.

Wskazówka
Na początku za największą liczbę przyjmuje się pierwszą z trzech liczb podanych jako parametr. Następnie bada się, czy druga z liczb jest większa od niej, jeśli tak, to za największą przyjmuje się drugą liczbę. Następnie bada się, czy trzecia z liczb jest większa od niej, jeśli tak, to za największą przyjmuje się trzecią liczbę.

W filmie omówiono algorytm sprawdzający, czy dana liczba jest pierwsza, oraz pokazano jego implementację.

Film prezentuje zagadnienie złożoności czasowej algorytmu na przykładzie badania własności liczb całkowitych, a konkretnie badania sumy dzielników danej liczby.

Zdefiniuj funkcję czy_parzysta(n), której wynikiem jest True w przypadku, gdy liczba podana jako parametr jest parzysta, lub False, gdy jest nieparzysta. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji czy_parzysta(1) jest False.
• Wynikiem funkcji czy_parzysta(2) jest True.

Wskazówka
Zauważ, że algorytm sprawdzania parzystości liczby opiera się na badaniu reszty z dzielenia liczby przez 2. Jeśli ta reszta równa jest 0, to liczba jest parzysta, w przeciwnym wypadku – nieparzysta.

Filmy

Prezentacja omawia zapis algorytmu za pomocą języka naturalnego, w postaci listy kroków (pseudokodu), schematu blokowego i programu.

Prezentacja przedstawia najważniejsze konstrukcje stosowane w języku Python.

Plansza zawiera podstawowe operatory działań i porównania oraz polecenia.

Infografika pokazuje, czym pętla while różni się od pętli for.

Przećwicz posługiwanie się pętlą while. Zdefiniuj funkcję ile_cyfr(liczba), której wynikiem będzie liczba cyfr danej liczby. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji ile_cyfr(123) jest 3.
• Wynikiem funkcji ile_cyfr(17923) jest 5.

Zaopatrzeniowiec dostaje listę zakupów. Martwi się, aby nie przekroczyć dopuszczalnego udźwigu po załadowaniu samochodu. Zdefiniuj funkcję zakupy(c, m, z), której parametrami są liczby worków c – cukru, 
m – mąki i z – ziemniaków. Worki cukru ważą 2 kg, mąki 5 kg i ziemniaków 12 kg. Udźwig samochodu wynosi 500 kg. Wynikiem funkcji jest True, gdy samochód może przewieźć zakupy, lub False, gdy zostanie przekroczony udźwig. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji zakupy(4, 9, 12) jest True.
• Wynikiem funkcji zakupy(12, 34, 43) jest False.

Wskazówka
Należy znaleźć łączną wagę produktów, a potem porównać wynik z 500. Łączną wagę produktów obliczamy, mnożąc liczbę worków przez ich masy, potem poszczególne liczby dodajemy do siebie.

Zdefiniuj funkcję logiczną czy_pierwsza(n), której parametrem jest liczba naturalna n większa od 1, a wynikiem wartość True, gdy jest ona liczbą pierwszą, albo False, gdy nią nie jest. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji czy_pierwsza(11) jest True.
• Wynikiem funkcji czy_pierwsza(99) jest False.

W międzynarodowej konferencji weźmie udział określona liczba gości z różnych krajów i określona liczba gospodarzy. Zaproszeni będą siedzieć w rzędach tak, aby każdy rząd był równoliczny i w każdym siedzieli albo tylko goście, albo tylko gospodarze. Jaka jest największa możliwa liczba osób w każdym rzędzie? Zdefiniuj funkcję rzad(goscie, gospodarze), której parametrami są liczba gości i gospodarzy, a wynikiem jest liczebność rzędu. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji rzad(72, 90) jest 18.
• Wynikiem funkcji rzad(24, 36) jest 12.

Na potrzeby warsztatów należy podzielić gości i gospodarzy na możliwie małe zespoły tak, by w każdym zespole była jednakowa liczba osób (gości i gospodarzy). Zdefiniuj funkcję ile(goscie, gospodarze), której parametrami są liczba gości oraz liczba gospodarzy, a wynikiem jest liczebność każdego zespołu. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji ile(56, 42) jest 7.
• Wynikiem funkcji ile(25, 35) jest 12.

Organizacją konferencji zajmują się dwa zespoły: do spraw programowych i do spraw metodycznych. Pierwszy spotyka się co x dni, drugi co y. Dziś spotkały się oba zespoły. Zdefiniuj funkcję kiedy(x, y), w której jako parametry będziesz podawać, co ile dni spotykają się zespoły, a wynikiem będzie liczba dni, które upłyną do następnego wspólnego spotkania obu zespołów. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji kiedy(6, 4) jest 12.
• Wynikiem funkcji kiedy(9, 12) jest 36.

Każdy gość powinien dostać taką samą liczbę długopisów, ołówków i flamastrów. Zdefiniuj funkcję flamastry(x, y, z), której parametrami są liczba długopisów w paczce (x), liczba ołówków w paczce (y) i liczba sztuk flamastrów w paczce (z), a wynikiem jest najmniejsza liczba opakowań flamastrów, które gospodarze powinni kupić, aby nic nie zostało. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji flamastry(6, 8, 10) jest 12.
• Wynikiem funkcji flamastry(39, 26, 52) jest 3.

Przećwicz posługiwanie się pętlą while. Zdefiniuj funkcję suma_cyfr(liczba), której wynikiem jest suma cyfr liczby. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji suma_cyfr(123) jest 6.
• Wynikiem funkcji suma_cyfr(17923) jest 22.

Wskazówka
Zauważ, że algorytm sumowania cyfr opiera się na wyodrębnianiu cyfr od końca i kolejno ich sumowania. W każdym kroku wyliczana jest ostatnia cyfra jako reszta dzielenia przez 10 oraz liczba jest dzielona przez 10.

Przećwicz posługiwanie się pętlą while. Zdefiniuj funkcję iledo6(lista), której wynikiem jest liczba liczb, które na liście są wpisane przed liczbą 6. Przyjmij, że 6 występuje co najmniej raz. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji iledo6([1, 2, 3, 4, 5, 6, 7]) jest 5.
• Wynikiem funkcji iledo6([1, 6, 3, 5, 5, 6, 7]) jest 1.

Przećwicz posługiwanie się pętlą while. Zdefiniuj funkcję suma(lista), której wynikiem jest suma liczb, które na liście są wpisane przed liczbą 0. Przyjmij, że 0 występuje co najmniej raz. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji suma([1, 2, 3, 4, 0, 6, 7]) jest 10.
• Wynikiem funkcji suma([1, 2, 0, 4, 5, 6, 0]) jest 3.

Przećwicz posługiwanie się pętlą while. Zdefiniuj funkcję sumap(lista), której wynikiem jest suma liczb parzystych, które na liście są wypisane przed liczbą 0. Przyjmij, że 0 występuje co najmniej raz. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji sumap([1, 2, 3, 4, 0, 6, 7]) jest 6.
• Wynikiem funkcji sumap([2, 2, 2, 4, 2, 6, 0]) jest 18

Przećwicz posługiwanie się pętlą while. Zdefiniuj funkcję sumanp(lista),  której wynikiem jest suma liczb nieparzystych, które na liście są wypisane przed liczbą 0. Przyjmij, że 0 występuje co najmniej raz. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji sumanp([1, 2, 3, 4, 0, 6, 7]) jest 4.
• Wynikiem funkcji sumanp([2, 2, 2, 4, 2, 6, 0]) jest 0.

Zdefiniuj funkcję pierwsza(n), której parametrem będzie liczba naturalna n, a wynikiem – n-ta liczba pierwsza. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji pierwsza(7) jest 17.
• Wynikiem funkcji pierwsza(25) jest 97.

Liczby bliźniacze to liczby pierwsze różniące się o 2. W pierwszej setce jest osiem par takich liczb: 3 i 5, 5 i 7, 11 i 13, 17 i 19, 29 i 31, 41 i 43, 59 i 61, 71 i 73. Zdefiniuj funkcję blizniacze(n), której parametrem jest liczba naturalna n, a wynikiem pierwsza liczba z n-tej pary liczb bliźniaczych. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji blizniacze(3) jest 11.
• Wynikiem funkcji blizniacze(7) jest 59.

Zdefiniuj funkcję suma_dzielnikow(n), której parametrem jest liczba naturalna n, a wynikiem – suma dzielników tej liczby. Sformułuj dwa algorytmy i porównaj szybkość działania każdego z nich dla różnych danych. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji suma_dzielnikow(7) jest 8.
• Wynikiem funkcji suma_dzielnikow(16) jest 31.

Liczby zaprzyjaźnione to dwie liczby naturalne, z których każda jest równa sumie dzielników właściwych drugiej liczby (np. suma dzielników właściwych liczby 220 wynosi 284, a suma dzielników właściwych liczby 284 – 220). Zdefiniuj funkcję zaprzyjaznione(n), której parametrem jest liczba naturalna n, a wynikiem – mniejsza liczba z n-tej pary liczb zaprzyjaźnionych. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji zaprzyjaznione(1) jest 220.
• Wynikiem funkcji zaprzyjaznione(3) jest 2620.

Zdefiniuj funkcję parzyste(liczba1, liczba2), której parametrami są liczby całkowite dodatnie, przy czym liczba1 < liczba2, a ich różnica wynosi co najmniej 3. Wynikiem funkcji jest lista dwóch liczb – najmniejszej liczby parzystej większej od parametru liczba1 i największej liczby parzystej mniejszej od parametru liczba2. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji parzyste(4, 9) jest [6, 8].
• Wynikiem funkcji parzyste(9, 12) jest [10, 10].
• Wynikiem funkcji parzyste(14, 75) jest [16, 74].

Zdefiniuj funkcję nieparzyste(n), której wynikiem jest liczba liczb nieparzystych podzielnych przez 7 nie większych od parametru n. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji nieparzyste(30) jest 2.
• Wynikiem funkcji nieparzyste(35) jest 3.
• Wynikiem funkcji nieparzyste(100) jest 7.

Liczby lustrzane to takie dwie liczby, które są lustrzanym odbiciem, np.: 123 i 321, 79 i 97, 1245 i 5421. Jeżeli zapiszemy razem dowolną liczbę i jej lustrzane odbicie, np. 123321, to tak otrzymana liczba jest podzielna przez 11.

Na przykład:

123321 : 11 = 11211
7997 : 11 = 727
12455421 : 11 = 1132311

Zdefiniuj funkcję lustro_11(liczba), której parametrem jest liczba całkowita dodatnia, a wynikiem iloraz liczby i doklejonej do niej jej liczby lustrzanej przez 11. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji lustro_11(123) jest 11211 (ponieważ 123321 : 11 = 11211).
• Wynikiem funkcji lustro_11(893) jest 81218 (ponieważ 893398 : 11 = 81218).

Zdefiniuj funkcję dwie(liczba), której wynikiem jest suma cyfr jedności i dziesiątek danej liczby powiększona o 1, gdy suma okazała się liczbą nieparzystą, lub zmniejszona o 1, gdy suma okazała się liczbą parzystą. Parametr liczba przyjmuje wartości z zakresu od 10 do 1 000 000. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji dwie(1284456) jest 12.
• Wynikiem funkcji dwie(892339) jest 11.

Liczby czworacze to liczby pierwsze mające postać: n, n + 2, n + 6 i n + 8. Zdefiniuj funkcję czworacze(n), której parametrem jest liczba naturalna n, a wynikiem – lista takich liczb czworaczych, w których pierwsza liczba jest większa od podanego parametru. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji czworacze(9) jest [11, 13, 17, 19].
• Wynikiem funkcji czworacze(150) jest [191, 193, 197, 199].

Pierwsza liczba ciągu Collatza jest dowolną liczbą naturalną x, a każda kolejna wartość ciągu obliczana jest na podstawie poprzedniej według poniższych zasad:

• jeśli poprzednia wartość była parzysta, to należy podzielić ją przez 2;
• jeśli poprzednia wartość była nieparzysta, to należy pomnożyć ją przez 3 i dodać 1.

Przypuszcza się, że niezależnie od której liczby naturalnej zaczniemy, zawsze po pewnej skończonej liczbie kroków otrzymamy liczbę 1. (Udowodniono to dla liczb mniejszych niż kilka tryliardów).

Zdefiniuj funkcję collatz(x), której parametrem jest liczba naturalna x, czyli wartość początkowa ciągu liczb Collatza, a wynikiem – liczba kroków, po których w ciągu pojawi się liczba 1. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji collatz(10) jest 6.
• Wynikiem funkcji collatz(15) jest 17.

Polski matematyk Hugo Steinhaus zauważył, że jeśli zsumujemy kwadraty cyfr wybranej liczby naturalnej, a następnie będziemy sumować kwadraty cyfr kolejnych otrzymanych liczb, to w pewnym momencie zawsze otrzymamy 1 lub 4. Zdefiniuj funkcję suma_kwadratow(n), której wynikiem będzie suma kwadratów cyfr liczby podanej jako parametr. Przetestuj działanie dla liczby 123 i kilku innych liczb początkowych.

Przeanalizuj poniższy kod, odpowiedz na pytania, a następnie sprawdź swoje odpowiedzi
w edytorze.

1. Jaki element i gdzie dodano do listy za pomocą polecenia w wierszu 2?
2. Jak należy uzupełnić wiersz 3, aby na końcu listy wstawić liczbę –11?
3. Jak poprawić zapis w wierszu 4, aby liczba 0 została wstawiona na początku listy, a liczba 23 na jej końcu?
4. Jaki element i na której pozycji dodano do listy za pomocą polecenia w wierszu 5?
5. Jaka lista zostanie wypisana na skutek polecenia w wierszu 6?

Zdefiniuj funkcję losuj(rozmiar, od, do) służącą do generowania listy o podanej długości (rozmiar), której elementami są liczby losowe z podanego zakresu (od i do).

Porównaj kolejne pary elementów listy (pierwszy z drugim, drugi z trzecim itd.). Jeśli pierwszy z nich jest większy niż drugi, to zamień je miejscami. Przeanalizuj dane (zauważ, że największa z liczb w wyniku znalazła się na końcu) i zdefiniowaną poniżej funkcję b(t), której parametrem jest lista liczb, a wynikiem – zmodyfikowana lista. Następnie znajdź i popraw błąd w skrypcie.

• Wynikiem funkcji b([16, 5, 12, 3, 12]) jest [5, 12, 3, 12, 16].
• Wynikiem funkcji b([1, 16, 18, 3, 16, 9, 9]) jest [1, 16, 3, 16, 9, 9, 18].

Zdefiniuj funkcję sort_b(t), której wynikiem jest podana jako parametr lista t, posortowana metodą bąbelkową w porządku rosnącym. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji sort_b([6, 3, 15, 9, 2]) jest [2, 3, 6, 9, 15].
• Wynikiem funkcji sort_b([11, 16, 8, 33, 6, 8, 1]) jest [1, 6, 8, 8, 11, 16, 33].

Zdefiniuj funkcję w(t, x), której parametrami są posortowana lista liczb t oraz liczba x, a wynikiem jest lista t
z liczbą x wstawioną w odpowiednim miejscu. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji w([6, 13, 15, 19, 22], 18) jest [6, 13, 15, 18, 19, 22].
• Wynikiem funkcji w([1, 9, 12, 33, 46], 57) jest [1, 9, 12, 33, 46, 57].
• Wynikiem funkcji w([-4, -2, 0, 2, 4], 0) jest [-4, -2, 0, 0, 2, 4].

Uzupełnij definicję funkcji sort_w(t), której wynikiem jest podana jako parametr lista t, posortowana metodą przez wstawianie w porządku rosnącym. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji sort_w([6, 3, 15, 9, 2]) jest [2, 3, 6, 9, 15].
• Wynikiem funkcji sort_w([11, 16, 8, 33, 6, 8, 1]) jest [1, 6, 8, 8, 11, 16, 33].

Zdefiniuj funkcję minimum(liczba), której wynikiem będzie najmniejsza cyfra liczby podanej jako parametr. Parametrem jest co najmniej dwucyfrowa liczba całkowita dodatnia. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem minimum(19) jest 1.
• Wynikiem minimum(98989) jest 8.

Zdefiniuj funkcję ile_liczb(tab), której wynikiem jest liczba różnych liczb na liście podanej jako parametr. Parametrem jest niepusta lista co najwyżej 100 liczb z zakresu od 0 do 10. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji ile_liczb([4, 1, 1, 4]) jest 2.
• Wynikiem funkcji ile_liczb([6, 6, 3, 7, 1, 7, 4, 4, 0, 3]) jest 6.

Dysponujesz nieograniczoną liczbą monet o nominałach 5, 3 i 1 i masz wydać resztę przy użyciu minimalnej liczby monet. Zdefiniuj funkcję trzy(kwota), której wynikiem będzie minimalna liczba monet potrzebnych do wydania kwoty podanej jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji trzy(11) jest 3.
• Wynikiem funkcji trzy(99) jest 21.

Dysponujesz nieograniczoną liczbą monet o nominałach 20, 10, 5, 2 i 1 i masz wydać resztę przy użyciu minimalnej ich liczby. Zdefiniuj funkcję wiele(kwota), której wynikiem będzie minimalna liczba monet potrzebnych do wydania kwoty podanej jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji wiele(11) jest 2.
• Wynikiem funkcji wiele(99) jest 8.

Dysponujesz podaną liczbą monet o określonych nominałach i masz wydać resztę przy użyciu minimalnej ich liczby. Zdefiniuj funkcję monety(kwota, nominaly, sztuki), której wynikiem będzie minimalna liczba monet potrzebnych do wydania kwoty podanej jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji monety(11, [20, 10, 5, 2, 1], [100, 100, 100, 100, 100]) jest 2.
• Wynikiem funkcji monety(99, [20, 10, 5, 1], [1, 10, 1, 10]) jest 13.

Zaopatrzeniowiec ma kupić cukier, mąkę i ziemniaki. Chce załadować jak najwięcej do samochodu, ale tak, by nie przekroczyć jego udźwigu wynoszącego x kg i przewieźć jak najmniejszą liczbę opakowań. Zdefiniuj funkcję zakupy(x), której parametrem jest udźwig, a wynikiem – łączna liczba opakowań towarów. Worki cukru ważą
2 kg, mąki 5 kg i ziemniaków 12 kg. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji zakupy(127) jest 12.
• Wynikiem funkcji zakupy(100) jest 10.

Zaopatrzeniowiec ma kupić cukier, mąkę i ziemniaki. Chce załadować jak najwięcej do samochodu, ale tak, by nie przekroczyć jego udźwigu wynoszącego x kg i przewieźć jak najmniejszą liczbę opakowań. Dodatkowo nie może kupić więcej niż ile opakowań jednego towaru. Zdefiniuj funkcję zakupy(x, ile), której parametrami są udźwig i maksymalna liczba opakowań jednego towaru, a wynikiem jest łączna liczba opakowań towarów. Worki cukru ważą 2 kg, mąki 5 kg i ziemniaków 12 kg. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji zakupy(127, 9) jest 14.
• Wynikiem funkcji zakupy(127, 12) jest 12.