ALG10

310 Rozdział 14. Zadania różne

Algorytm ten można nieco uprościć, wiedząc że jeśli liczba n nie jest pierwsza, wówczas jest ona podzielna przez pew ną liczbę pierwszą, taką że jest ona mniejsza

lub równia całkowitej części \fn (oznaczane dalej jako sqri_int(nj).

Proszę napisać program, który:

•    sprawdza metodą brute-force), czy dana liczba jest liczbą pierwszą;

•    wykorzystując metodę sita Erastotenesa, liczy wszystkie liczby pierwsze mniejsze od 100:

•    wykorzystując metodę uproszczoną, liczy wszystkie liczby pierwsze mniejsze od 100.

Zad. 14-2

Napisać funkcję, która otrzymując na wejściu datę zakodowaną w postaci liczby całkowitej (np. 220744) wypisze słownie jej znaczenie (tutaj: „22 lipca 1944”).

Zad. 14-3

W operacjach macierzowych często są używane tablice z dużą ilością zer. Reprezentowanie ich w postaci dwuwymiarowej wydaje się marnotrawstwem pamięci. Spróbuj zaproponować strukturę danych, która będzie zawierała tylko informację o „współrzędnych” elementów niezerowych. Zakładamy, że wszystkie pozostałe liczby, nie zaprezentowane w niej, są zerowe. Zaproponuj funkcje obsługujące taką strukturę danych: wypisujące macierz w formie „odkodowanej”, dodające i mnożące dwie macierze etc.

Spróbuj określić w przybliżeniu, do jakiego stopnia zapełnienia tablicy zerami taka struktura danych jest opłacalna, jeśli chodzi o zużycie pamięci.

Zad. 14-4

Zaproponuj dwie wersje rekurencyjnego algorytmu obliczania funkcji x' (reku-rcncja „naturalna” i rekurencja „z parametrem dodatkowym”).

Zad. 14-5

Spróbuj stworzyć nierekurericyjną funkcję, która na podstawie dwóch list posortowanych zwróci jako wynik listę posortowaną, zawierającą wszystkie ich elementy. Wymóg: nie wolno tworzyć nowych komórek pamięci, jedyne, co jest dozwolone, to manipulacja wskaźnikami.