Algorytm i schemat blokowy

Algorytm –jest to skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Sposób postępowania prowadzący do rozwiązania problemu.

Zadaniem algorytmu jest przeprowadzenie systemu z pewnego stanu początkowego do pożądanego stanu końcowego. Istnieje szeroko rozbudowana teoria algorytmów zajmująca się ich konstrukcją i badaniem.   Algorytm może zostać zaimplementowany w postaci programu komputerowego.

Przez implementację (inaczej: wdrożenie, przystosowanie, realizacja) rozumiemy– w informatyce – proces przekształcania abstrakcyjnego opisu systemu lub programu na obiekt fizyczny: komputer lub działający program zapisany w konkretnym języku programowania.

 

Schemat blokowy jest graficzną prezentacją kolejnych czynności w projektowanym algorytmie. Schemat blokowy pozwala dostrzec istotne etapy algorytmu i logiczne zależności między nimi.

Do głównych elementów budowy schematów blokowych należą:

strzałka – wskazuje jednoznacznie powiązania i ich kierunek,

operand – prostokąt, do którego wpisywane są wszystkie operacje z wyjątkiem instrukcji wyboru,

predykat – romb, do którego wpisywane są wyłącznie instrukcje wyboru,

etykieta – owal służący do oznaczania początku bądź końca sekwencji schematu (kończy, zaczyna lub przerywa/przenosi schemat).

Poniżej przykładowy schemat blokowy algorytmu znajdowania liczb pierwszych metodą tzw. sita Eratostenesa.

Przyjrzyjmy się jak działa  ten algorytm.

Niech N = 100. Tworzymy ciąg A[i] dla i=2,3,…,100 (jedynka nie jest liczbą pierwszą, więc jej nie bierzemy pod uwagę)

Wszystkim wartościom tego ciągu nadajemy wartość True (można także nadać wartość 1).

Bierzemy liczbę pierwszą i=2 (o niej wiemy, że jest liczbą pierwszą, zaś o pozostałych nie musimy nic wiedzieć!)

Mnożymy ją przez dwa {j:=2*i} i wynik wykreślamy z listy tzn. nadajemy elementowi A[4] wartość False.(zamiast wartości False można nadać wartość 0)

Do powstałej liczby 4 dodajemy kolejno wartości 2 otrzymując j = 6,8,10,…..100 i wszystkie te liczby usuwamy z listy ( tzn. dla wszystkich tych j nadajemy elementom ciągu A[j] wartość False.)

Zakończywszy wyrzucanie wielokrotności 2, zwiększamy liczbę dwa o jeden {i:=i+1} otrzymując 3. Znowu mnożymy ją przez dwa i A[6] nadajemy wartość false.

Uwaga 1. Zauważmy, że wartości A[6] została już nadana poprzednio wartość false.

Do powstałej liczby 6 dodajemy kolejno wartości 3 otrzymując j = 9,12,15,…..99 i wszystkie te liczby usuwamy z listy ( tzn. dla wszystkich tych j nadajemy elementom ciągu A[j] wartość False.)

Zakończywszy wyrzucanie wielokrotności 3, zwiększamy liczbę 3 o jeden {i:=i+1}  

otrzymując 4. Znowu mnożymy ją przez dwa i A[8] nadajemy wartość false.

Do powstałej liczby 8 dodajemy kolejno wartości 4 otrzymując j = 12,16,…,100 i wszystkie te liczby usuwamy z listy ( tzn. dla wszystkich tych j nadajemy elementom ciągu A[j] wartość False.)

Uwaga 2. Zauważmy, że wartościom A[j] dla j parzystych (bo podzielnych przez 4)  została już nadana poprzednio wartość false, a zatem cala praca dla i=4 jest zupełnie zbędna. Jest to duża wada naszego programu!

Zakończywszy wyrzucanie wielokrotności 4, zwiększamy liczbę 4 o jeden {i:=i+1}  

otrzymując 5. Znowu mnożymy ją przez dwa i A[10] nadajemy wartość false.

Uwaga 3. Zauważmy, że wartości A[10] została już nadana poprzednio wartość false.

Do powstałej liczby 10 dodajemy kolejno wartości 5 otrzymując j = 15,20,25,…,100 i wszystkie te liczby usuwamy z listy ( tzn. dla wszystkich tych j nadajemy elementom ciągu A[j] wartość False.)

Zakończywszy wyrzucanie wielokrotności 5, zwiększamy liczbę 5 o jeden {i:=i+1}  

otrzymując 6. Znowu mnożymy ją przez dwa i A[12] nadajemy wartość false.

Uwaga 4. Ponieważ liczba 6 jest liczbą złożoną 6=2∙3, zatem była już poprzednio wyrzucana dwukrotnie, podobnie jest z jej wielokrotnościami. A zatem cala praca dla i=6 jest zupełnie zbędna. Jest to duża wada naszego programu!

Zakończywszy wyrzucanie wielokrotności 6, zwiększamy liczbę 6 o jeden {i:=i+1}  

otrzymując 7. Znowu mnożymy ją przez dwa i A[14] nadajemy wartość false.

Do powstałej liczby 14 dodajemy kolejno wartości 7 otrzymując j = 21,28,35,…,98 i wszystkie te liczby usuwamy z listy (tzn. dla wszystkich tych j nadajemy elementom ciągu A[j] wartość False.)

Procedurę kontynuujemy aż do osiągnięcia wartości i = 101, która nie spełnia warunku i≤100.

Wówczas następuje wypisanie wszystkich wartości liczb naturalnych i, dla których A[i] mają niezmienioną wartość true. Są to wszystkie liczby pierwsze mniejsze od 100.

Oczywiście, łatwo poprawić procedurę w taki sposób, aby nie liczyła niepotrzebnie wielokrotności liczb złożonych i nadawała im wartości false. Zwiększy to bardzo efektywność procedury zmniejszając znacznie czas obliczeń.

Wystarczy bezpośrednio po instrukcji {i:=i+1} sprawdzić czy aktualna wartość i jest liczbą złożoną {w schemacie blokowym odpowiada to instrukcja wyboru: Czy A[i] = false?} i jeżeli tak jest przechodzimy do kolejnej wartości {i:=i+1}.

Odpowiednią poprawkę do schematu blokowego prezentujemy poniżej:

I tu pytanie do Czytelnika: Czy taka poprawka nie stwarza nowych kłopotów w działaniu procedury?

Odpowiedź: Łatwo można wskazać takie kłopoty. Liczba i=97 jest liczbą pierwszą.

 Po instrukcji i:=i+1= 97+1= 98 dostaliśmy liczbę złożoną. Zgodnie z poprawioną procedurą znowu przechodzimy do instrukcji i:=i+1=98+1=99 dostając liczbę złożoną. Po dodaniu kolejnej jedynki otrzymamy liczbę złożoną 100. Przechodząc dalej otrzymamy liczbę pierwszą 101, ale ona jest już większa od 100 i program może nie wiedzieć co z tym faktem począć.

Oczywiście łatwo na różne sposoby wyeliminować tę pułapkę.

Można np. przyjąć za N liczbę pierwszą; w naszym przypadku N =101. Ale chwaliliśmy się, że w tym programie nie musimy znać żadnej liczby pierwszej oprócz 2.

Można skorzystać z wyników rozdziału 3.2. Pokazaliśmy tam, że po liczbie n! mamy kolejno (n-1) liczb złożonych: n!+2, n!+3,    …  , n!+(n-1), n!+n

 Zatem dla liczby N=121=5!+1 dopiero 127 ma szanse być liczbą pierwsza i nią jest!

Można też skorzystać ze znanego twierdzenia z teorii liczb, że między liczbami n i 2n jest przynajmniej jedna liczba pierwsza. Poniżej podaję odpowiednie twierdzenia:
Postulat Bertranda – Twierdzenie Czebyszewa
Twierdzenie 1
Dla każdej liczby naturalnej n∈ℕ większej lub równej 1 istnieje przynajmniej jedna liczba pierwsza większa od n i mniejsza lub równa 2n.
Uwaga moja: oczywiście równa dotyczy tylko  n=1.
Słynny Paul Erdős wzmocnił to twierdzenie dowodząc:
Twierdzenie 2
Dla dowolnej liczby naturalnej n>6, między liczbami n, a 2n, znajdują się co najmniej dwie liczby pierwsze – co najmniej jedna postaci 4m+1, oraz co najmniej jedna postaci 4m+3.

 

Oczywiście, rozważania powyższe były czysto teoretyczne i trochę niepotrzebne. Poprawiony algorytm poradzi sobie z tym bez trudu…(vide poniżej)

Kolejne usprawnienie będzie dotyczyło pierwszej usuwanej ze zbioru wielokrotności. Obecnie jest to:          {j:= 2*i}                                                                                                                     Rozważmy: i=3. Wielokrotność 6 jest podzielna przez 2 i została już usunięta wcześniej ze zbioru. Pierwszą nieusuniętą wielokrotnością jest 9, czyli 32.
Rozważmy: i=5. Wielokrotności już usunięte to: 10, 15, 20. Pierwsza nieusunięta wielokrotność to 25, czyli 52.
Rozważmy: i=7. Wielokrotności już usunięte to: 14, 21, 28, 35, 42. Pierwsza nieusunięta wielokrotność to 49, czyli 72.

 Z podanych przykładów widzimy jasno, że pierwszą wielokrotnością, od której należy rozpocząć usuwanie jest i2. Powód jest bardzo prosty. Mniejsze wielokrotności rozkładają się na dwa czynniki, z których jednym jest i, a drugim liczba mniejsza od i.  Skoro tak, to ta mniejsza liczba już wcześniej usunęła taką wielokrotność.

Zatem w programie zmieniamy: zamiast { j:=2*i} na {j:= i*i}.

 Skoro pierwszą usuwaną wielokrotnością jest i2, to gdy i przekroczy wartość pierwiastka z n, wielokrotność ta znajdzie się poza przedziałem <2,n>. Zatem wystarczy, aby i przebiegało wartości od 2 do pierwiastka z n. Ale to w algorytmie wychodzi automatycznie…

Poniżej fragment schematu blokowego poprawionego algorytmu….