Informatyka 2

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.

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.

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.