Informatyka 2

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(int n), której wynikiem jest 1 w przypadku, gdy liczba podana jako parametr jest parzysta, lub 0, gdy jest nieparzysta. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji czy_parzysta(1) jest 0.
• Wynikiem funkcji czy_parzysta(2) jest 1.

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(int n), której parametrem jest liczba naturalna n większa od 1, a wynikiem wartość 1, gdy jest ona liczbą pierwszą, albo 0, gdy nią nie jest. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji czy_pierwsza(11) jest 1.
• Wynikiem funkcji czy_pierwsza(99) jest 0.

Zdefiniuj funkcję pierwsza(int 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(int 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(int 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(25) 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. 220 i 284, 1184 i 1210, 2620 i 2924. Zdefiniuj funkcję zaprzyjaznione(int n), której parametrem będzie 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.

Liczby czworacze to liczby pierwsze mające postać: n, n + 2, n + 6 i n + 8, np. 5, 7, 11, 13 i 11, 13, 17, 19 i 101, 103, 107, 109. Zdefiniuj funkcję czworacze(int n), której parametrem będzie liczba naturalna n, a wynikiem – pierwsza liczba z liczb czworaczych, większa od podanego parametru. Sprawdź działanie funkcji dla podanych poniżej parametrów.

• Wynikiem funkcji czworacze(9) jest 11.
• Wynikiem funkcji czworacze(150) jest 191.

Ciąg liczb Collatza zdefiniowany jest następująco: pierwsza liczba ciągu 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.

Wobec tego dla wartości początkowej x = 10 kolejne liczby to: 5, 16, 8, 4, 2, 1. Zdefiniuj funkcję collatz(int x), której parametrem będzie 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.

Zdefiniuj funkcję parzyste(int liczba1, int liczba2), której parametrami są liczby całkowite dodatnie, przy czym liczba1 < liczba2, a ich różnica wynosi co najmniej 3. Wynikiem funkcji jest suma 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 14.
• Wynikiem funkcji parzyste (9, 12) jest 20.
• Wynikiem funkcji parzyste (14, 75) jest 90.

Zdefiniuj funkcję nieparzyste(int 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.

Zdefiniuj funkcję dwie(int liczba), której wynikiem jest suma cyfry jedności i dziesiątek powiększona o 1, gdy jest liczbą nieparzystą, lub zmniejszona o 1, gdy jest 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.