Ocena końcowa

Wstęp do algorytmiki

Co to jest algorytm?

Na algorytmice będziemy posługiwać się pojęciem algorytm. Cóż, to takiego? Myślę, że można powiedzieć, że jest to przepis jak z pewnych danych uzyskać określone wyniki.

Wbrew pozorom często stosujemy algorytmy w codziennym życiu. Przykładem może być przejście przez ulicę. Danymi są: ulica, ruch na niej oraz nasze położenie początkowe na krawężniku. Oczekiwanym wynikiem będzie znalezienie się po przeciwnej stronie ulicy. Algorytm (którego nauczono nas w dzieciństwie) mówi nam, jak tego dokonać. Można go zapisać w postaci tzw. listy kroków:

  1. Spójrz w lewo.
  2. Jeśli samochód jest odpowiednio daleko przejdź do następnego punktu, w przeciwnym przypadku wróć do punktu 1.
  3. Spójrz w prawo.
  4. Jeśli samochód jest odpowiednio daleko przejdź do następnego punktu, w przeciwnym przypadku wróć do punktu 3.
  5. Spójrz w lewo.
  6. Jeśli samochód jest odpowiednio daleko przejdź do następnego punktu, w przeciwnym przypadku wróć do punktu 5.
  7. Przejdź przez ulicę.

Oczywiście algorytm ten jest mocno uproszczony, w rzeczywistości punkt 7 powinien być bardziej rozbudowany (być może w połowie trzeba będzie się zatrzymać, cofnąć albo przyśpieszyć).

Algorytmy w kuchni

Typowymi przykładami z życia codziennego są przepisy kulinarne. Nazwa przepisu mówi o końcowym produkcie, natomiast na początku podane są niezbędne składniki oraz naczynia itp. Sam przepis jest algorytmem. Przypomnij sobie jak należy ugotować jajko na miękko. Przepis mówi, co należy zrobić, z czym i w jakiej kolejności.

Algorytmy w matematyce

Z algorytmami miałeś do czynienia na matematyce. Typowym przykładem jest rozwiązanie równania kwadratowego. Dane w tym przypadku to współczynniki a, b, c równania ax2+bx+c=0, a wynikiem - pierwiastki, ewentualnie stwierdzenie, że nie ma takowych.

Algorytmy w innych naukach

Także na innych przedmiotach mogłeś spotkać się z algorytmami. Na chemii uzyskiwałeś pewne związki chemiczne mając inne substancje oraz laboratorium. Na fizyce ważyłeś ciała stałe, a na biologii przygotowywałeś preparaty do oglądania ich pod mikroskopem.

Definicja algorytmu

We wszystkich tych przypadkach postępowałeś wg pewnej instrukcji, która od stanu początkowego prowadziła do stanu końcowego. Ten zestaw instrukcji wraz z stanem początkowym i efektem końcowym - od dzisiaj - będziemy nazywać algorytmem.

Zadania

  1. Podaj kilka przykładów algorytmów z życia codziennego.
  2. Zapisz w postaci listy kroków jeden z nich.
  3. Podaj kilka algorytmów, które poznałeś na matematyce.
  4. Zapisz w postaci listy kroków jeden z nich.

Zapis algorytmu w postaci schematu blokowego

Już wiemy z pierwszej lekcji, że algorytm można zapisać w postaci listy kroków. Jest też inny zapis - schemat blokowy. Jest on dużo czytelniejszy i taki spotyka się najczęściej. Najprościej jego ideę można przedstawić na przykładzie algorytmu z pierwszej lekcji (przechodzenie przez jezdnię) zapisanego w postaci schematu blokowego.

Przejście przez jezdnię

Integralną częścią algorytmu jest jego specyfikacja, czyli co jest dane (Wejście), a co należy uzyskać (Wyjście).

Specyfikacja

  • Wejście: Stoimy na krawężniku
  • Wyjście: Jesteśmy po przeciwnej stronie

Schemat blokowy

Jak widać taka prezentacja algorytmu jest bardziej czytelna i dlatego większość algorytmów będzie pokazana w tej postaci.

Skrzynki

Algorytm zaczyna się od tej skrzynki. Musi wystąpić w schemacie dokładnie raz!

Algorytm kończy się tą skrzynką. Musi występować choć jeden raz.
Skrzynka wejścia, czyli pobieranie danych od użytkownika.
W podanym przykładzie dana zostanie zapisana w zmiennej x.
Zamiast We: można użyć Podaj, Wpisz itp.
Skrzynka wyjścia, czyli wypisywanie wyników działania algorytmu.
W podanym przykładzie dana zostanie wypisana wartość zmiennej x.
Zamiast Wy: można użyć Wypisz, Wyświetl itp.
Skrzynka instrukcji. Tu realizowane są wszelkie obliczenia.
W podanym przykładzie wartość zmiennej zwiększy się o 1.
Znak := należy czytać staje się.
Skrzynka warunkowa. Tu następuje rozgałęzienie algorytmu w zależności od logicznej wartości warunku.
Jeśli jest prawdziwy algorytm pójdzie w lewo (tam gdzie jest litera T jak Tak lub True), w przeciwnym przypadku uda się w prawo.

Pozostałe symbole tworzą stanowią drogi, które łączą skrzynki. W niektórych sytuacjach dodatkowe strzałki precyzują kierunek ruchu.

W zasadzie powinno się wchodzić do skrzynki od góry. Nie jest to jednak zasada bezwzględna. Czasem warto ją złamać, by uzyskać lepiej wyglądający schemat blokowy.

Zmienne

O zmiennych była już mowa przy okazji skrzynek wejścia, wyjścia oraz wykonawczej. Cóż to takiego? Zmienna przypomina niewiadomą z matematyki. W niej właśnie komputer przechowuje dane np. liczbowe.

Jej nazwa może być w zasadzie dowolna, o ile będzie się zaczynać od litery. Powinna jednak być znacząca. Dlatego pole trójkąta należy przechowywać w zmiennej PoleTrojkata, a nie w p lub pt. Mogą w niej wystąpić cyfry, np. licznik1, licznik2, a nawet znak podkreślenia. W nazwie nie może wystąpić spacja. Dobrym zwyczajem (wymuszonym przez większość języków programowania) jest nieużywanie polskich liter.

Przykłady poprawnych nazw zmiennych:

  • i
  • Srednica
  • wspolczynnik_1
  • WspolczynnikA
  • Szerokosc

Przykłady niepoprawnych nazw zmiennych:

  • 9j
  • Średnica
  • wspolczynnik 1
  • Wspolczynnik+A

Operatory arytmetyczne

Jeden z nich już poznałeś - znak dodawania (+). Na początek wystarczy, że poznasz jeszcze trzy: odejmowania (-), mnożenia (*) oraz dzielenia (/). Wszystkie one łączą zmienne oraz stałe (czyli liczby np. 0.5). W przypadku instrukcji przypisania komputer najpierw oblicza wartość tego wyrażenia, a potem zmienia wartość odpowiedniej zmiennej.

W przypadku bardziej skomplikowanych wyrażeń należy użyć nawiasów, ale wyłącznie zwykłych ().

Przykłady poprawnego użycia operatorów arytmetycznych:

  • KwadratA:=A*A
  • PoleTrojkata:=0.5*a*h
  • RoznicaKwadratow:=a*a-b*b
  • PolowaObwoduTrojkata:=(a+b+c)/2
  • delta:=b*b-4*a*c

Przykłady niepoprawnego użycia operatorów arytmetycznych:

  • KwadratA*2:=A*A
  • PoleTrojkata:=0.5ah
  • RoznicaKwadratow:=a*-b*b
  • PolowaObwoduTrojkata:=(a+b+c/2

Operatory porównania

Jeden z nich już poznałeś - znak większe (>). Inne to: równe (=), mniejsze (<), większe lub równe (>=), mniejsze lub równe (<=) oraz różne (<>). Wykorzystuje się je w skrzynce warunkowej. Wynikiem ich zastosowania w połączeniu ze zmiennymi i stałymi jest zdanie logiczne. Zdania te można łączyć spójnikami And (i), Or (lub) oraz nawiasami.

Przykłady poprawnego użycia operatorów porównania:

  • Kwadrat=a
  • PoleTrojkata=7
  • RoznicaKwadratow+1=2*a
  • (PolowaObwoduTrojkata=3) Or (Pole=7)

Przykłady niepoprawnego użycia operatorów porównania:

  • Kwadrat=A=B
  • PoleTrojkata=>0.5
  • RoznicaKwadratow<a<b

Nazwy zmiennych są bardzo istotne w przypadków dłuższych algorytmów!

Zadania

  1. Zaproponuj nazwy zmiennych dla zmiennych przechowujących:
    1. promień koła,
    2. długość okręgu,
    3. pole koła,
    4. liczbę boków wielokąta,
    5. obwód wielokąta,
    6. liczbę przekątnych wielokąta.
  2. Podaj kilka przykładów algorytmów z życia codziennego.
  3. Zapisz w postaci schematu blokowego jeden z nich.
  4. Podaj kilka algorytmów, które poznałeś na matematyce.
  5. Zapisz w postaci schematu blokowego jeden z nich.

Pierwszy algorytm

Pierwszy algorytm powinien być możliwie jak najprostszy. Obliczenie pola kwadratu wydaje się wystarczającym problemem na pierwszy raz.

Na początek zastanówmy się nad specyfikacją algorytmu. Jedyną daną jest długość boku. Niech zmienna, która będzie przechowywać tę wartość, nazywa się bok. Jaki ma być wynik? Oczywiście pole kwadratu, które policzymy w zmiennej Pole. Dlaczego nie PoleKwadratu? W tym algorytmie nie będzie innego pola w związku z czym wystarczy tak nazwać tę zmienną.

Zaczynamy oczywiście od skrzynki początkowej.

Na początek należy wczytać długość podstawy kwadratu, korzystając ze zmiennej bok.

Skoro już wiemy ile wynosi podstawa kwadratu to możemy obliczyć jego pole.

Teraz wystarczy poinformować użytkownika o wyniku.

I algorytm gotowy.

Cały algorytm wygląda następująco:

Pole kwadratu

Specyfikacja

  • Wejście: bok - długość podstawy kwadratu
  • Wyjście: Pole - pole kwadratu

Schemat blokowy

Mimo, że algorytm ten jest bardzo prosty ilustruje jak wyglądają wszystkie - nawet najbardziej skomplikowane. Można w nim wyróżnić 3 fazy:

  1. Wczytanie danych
  2. Obróbka danych
  3. Wypisanie wyników

W przypadku bardziej złożonych algorytmów najwięcej miejsca zajmuje obróbka danych.

Zadania

  1. Stwórz algorytm obliczający pole trójkąta.
  2. Stwórz algorytm obliczający pole trapezu.
  3. Stwórz algorytm obliczający pole koła.
  4. Stwórz algorytm obliczający pole trójkąta równobocznego.
    Rozwiązanie
  5. Stwórz algorytm obliczający długość przeciwprostokątnej w trójkącie prostokątnym.

Program ELI

Algorytmy można rysować odręcznie, ale również zapisywać je w edytorze tekstowym np. Word. Najwygodniejszym jednak sposobem jest użycie programu ELI.

Program ELI służy do tworzenia i testowania algorytmów w dość przyjemnym środowisku. Wersję instalacyjną znajdziesz w zasobach internetowych. Niestety jest to wersja demo, która nie pozwala m. in. na zapisywanie swoich algorytmów. III LO dysponuje pełną wersją, która nie ma tej wady.

Instalacja

Instalacja jest prosta. Wystarczy skopiować zipa, rozpakować go gdziekolwiek i uruchomić Instaluj.exe. Potem naciskamy domyślne przyciski. System ponownie się uruchomi i program jest gotowy do użytku.

Uruchomienie

Na początek widzimy szare okno. Należy wybrać Plik/Nowy projekt... Pojawi się okno Nowy projekt:

Nowy projekt

Pola, które musimy wypełnić zaznaczone zostały na zielono. Oczywiście nazwę projektu należy wpisać stosowną do tego, co mamy zamiar zrobić (8 pierwszych liter będzie wyświetlonych na pasku tytułowym). W ten sposób otrzymaliśmy zieloną planszę, na której możemy układać algorytm, z dostępnych po lewej stronie skrzynek (w ELI nazywane są klockami).

Klocki

Niestety klocki wyglądają nieco inaczej niż te używane przez nas skrzynki. W poniższej tabeli są przedstawione kolejno: skrzynka, klocek, przykład wypełnienia klocka (okno dostępne po kliknięciu prawym przyciskiem w klocek, żółty kolor oznacza, że dane pole nie musi być wypełnione).

Testowanie algorytmu

Kiedy już poskładamy z klocków algorytm należy go przetestować. Najwygodniej robi się to za pomocą następujących przycisków:

Rozpoczęcie testowania

Przejście do następnego klocka

Uruchomienie algorytmu

Zatrzymanie testowania

Przerwanie testowania

W czasie pracy algorytmu może dojść do powstania błędów. Typowe z nich to:

  • dzielenie przez zero,
  • nieoczekiwany koniec algorytmu,
  • użycie = zamiast :=,
  • literówki w nazwach zmiennych (dla ELI zmienne pole oraz Pole są różnymi zmiennymi),
  • wejście do klocka z boku.

Wszystkie te błędy można stosunkowo prosto poprawić. ELI zawsze pokazuje, który klocek spowodował błąd. Najtrudniej poprawić błędy logiczne w algorytmie. Żeby wykryć wszystkie błędy należy wielokrotnie przetestować algorytm dla różnych danych.

Zadania

  1. Stwórz algorytm obliczający pole trójkąta.
  2. Stwórz algorytm obliczający pole trapezu.
  3. Stwórz algorytm obliczający pole koła.
  4. Stwórz algorytm obliczający pole trójkąta równobocznego.
  5. Stwórz algorytm obliczający długość przeciwprostokątnej w trójkącie prostokątnym.

Pierwszy algorytm bis

Przypomnijmy sobie pierwszy algorytm obliczający pole kwadratu.

Pole kwadratu

Specyfikacja

  • Wejście: bok - długość podstawy kwadratu
  • Wyjście: Pole - pole kwadratu

Schemat blokowy

Wydaje się, że jest on doskonały. Gdy wprowadzimy 5, otrzymamy pole równe 25. Jeśli 1.1, to 1.21. Działa! Owszem, ale tylko dla liczb dodatnich. Wprowadź liczbę -3, algorytm wypisze, że pole wynosi 9, co oczywiście nie jest prawdą. Zapewne powiesz, że nie jest to uczciwe, bo nie ma boku o długości -3. To prawda, ale nasz algorytm nie wie o tym. Trzeba go tego nauczyć.

Tak więc, naszym zadaniem jest stworzenie takiego algorytmu, który dla dodatnich długości boków będzie zachowywać się po staremu wypisując pole kwadratu, a dla nieujemnych (czyli również dla 0) stwierdzi błąd w danych.

Początek wygląda tak jak poprzednio.

Potrzebujemy teraz klocka, dzięki któremu rozdzielimy 2 przypadki: bok dodatni, bok niedodatni. Osiągniemy to za pomocą klocka warunkowego. Musimy sprawdzić, czy bok jest większy od 0.

Jeśli warunek ten będzie prawdziwy, to skręcamy w lewo i przepisujemy starą wersję algorytmu.

Jeśli jednak warunek będzie fałszywy (bok<=0), to należy wypisać komunikat o błędzie.

W programie ELI komunikat o błędzie powinien być nieco bardziej precyzyjny. Powinien informować, że długość boku musi być liczbą dodatnią. Oto cały nasz algorytm:

Pole kwadratu ze sprawdzeniem poprawności danej

Specyfikacja

  • Wejście: bok - długość podstawy kwadratu
  • Wyjście: Pole - pole kwadratu lub komunikat "Błędny bok"

Schemat blokowy

Algorytm ten można zmodyfikować tak, by po komunikacie o błędzie algorytm umożliwiał wprowadzenie poprawnego boku.

Pole kwadratu ze sprawdzeniem poprawności danej i pętlą

Specyfikacja

  • Wejście: bok - długość podstawy kwadratu
  • Wyjście: Pole - pole kwadratu

Schemat blokowy

Zauważ, że powstała pętla. Użytkownik może wprowadzać ujemne długości boków, aż w końcu wprowadzi liczbę dodatnią. Te trzy skrzynki tworzą pętlę, jedno z podstawowych pojęć w algorytmice oraz programowaniu. Zastosowanie pętli znacznie skraca długość algorytmu, podnosi jego efektywność i generuje mniej potencjalnych błędów przy tworzeniu algorytmów.

Zadania

  1. Stwórz algorytm obliczający pole trójkąta.
  2. Stwórz algorytm obliczający pole trapezu.
  3. Stwórz algorytm obliczający pole koła.
  4. Stwórz algorytm obliczający pole trójkąta równobocznego.
  5. Stwórz algorytm obliczający długość przeciwprostokątnej w trójkącie prostokątnym.

Równanie liniowe

Spróbujmy napisać algorytm, który rozwiąże równanie liniowe ax+b=0. Użytkownik wprowadzi współczynniki a oraz b (dane), natomiast algorytm na wypisać x (wynik). Skoro mamy już specyfikację algorytmu, to możemy zająć się właściwym algorytmem.

Na początek wczytamy współczynniki:

Teraz trzeba wyznaczyć x. W tym celu należy rozwiązać równanie liniowe.

ax+b=0

ax=-b |:a

x=-b/a

Uzbrojeni w tę wiedzę kończymy algorytm:

Nasz algorytm wygląda następująco:

Równanie liniowe

Specyfikacja

  • Wejście: a, b - współczynniki równania liniowego ax+b=0
  • Wyjście: x - rozwiązanie równania liniowego

Schemat blokowy

Testowanie

Korzystając z programu ELI testujemy nasz algorytm wpisując współczynniki a, b, dla których znamy rozwiązanie, by sprawdzić czy wyniki są zgodne z naszymi oczekiwaniami. Należy wpisywać możliwie różne dane i obserwować wyniki.

Już po chwili zauważamy, że zarówno dla dodatnich a jak i ujemnych oraz dla dowolnych b algorytm oblicza prawidłowe wyniki. Wpiszmy jednak a=0 oraz dowolne b.

ELI zgłosi błąd dzielenia przez zero w klocku, w którym próbował obliczyć x. Rzeczywiście jest tam dzielenie przez a. Algorytm nie jest odporny na taką wartość a.

Poprawienie algorytmu

Wracamy do przekształceń równania liniowego. Ale tym razem wiemy coś nowego: a=0.

x+b=0, a=0

0x+b=0

b=0

Ostatnie równanie oznacza, że rozwiązanie równania liniowego, gdy a=0 zależy od wartości współczynnika b. Jeśli b=0, to równanie liniowe ma nieskończenie wiele rozwiązań, w przeciwnym przypadku - rozwiązaniem jest zbiór pusty.

Co to oznacza dla naszego algorytmu? Po wprowadzeniu współczynników należy sprawdzić, czy a=0. Jeśli warunek nie będzie spełniony, to mamy do czynienia z jednym rozwiązaniem, które wyznaczyliśmy we wcześniejszej wersji algorytmu.

W przypadku, gdy warunek jest spełniony, trzeba sprawdzić wartość współczynnika b i odpowiednio zareagować.

W programie ELI można skrócić nieco algorytm, korzystając z faktu, że przy zakończeniu algorytmu można podać dowolny komunikat końcowy. Skrzynki wyjścia niezbyt się nadają do wypisywania komunikatów bez wartości liczbowych. Warte użycia są skrzynki z dzwoneczkiem, które również umożliwiają podanie samego komunikatu.

Tak wygląda nasz algorytm w pełnej wersji:

Równanie liniowe

Specyfikacja

  • Wejście: a, b - współczynniki równania liniowego ax+b=0
  • Wyjście: x - rozwiązanie równania liniowego lub komunikat "Nieskończenie wiele rozwiązań" lub komunikat "Brak rozwiązań"

Schemat blokowy

Jak widać dociekliwe testowanie doprowadziło do wykrycia błędu w algorytmie. Dlatego poważne oprogramowanie jest testowane przez długi czas wewnątrz firmy. Potem wypuszczana jest tzw. wersja Beta, by sprawdzić program na realnych użytkownikach. Po tych testach i ponownych poprawkach publikowana jest ostateczna wersja.

Zadania

  1. Stwórz algorytm obliczający pierwiastki równania kwadratowego ax2+bx+c=0 (a<>0).
  2. Rozwiąż układ dwóch równań liniowych a1x+b1=c1 i a2x+b2=c2.
  3. Stwórz algorytm obliczający pierwiastki równania ax2+bx+c=0 (a dowolne).

Boki trójkąta

Postawmy sobie następujący problem: Mamy długości trzech odcinków (a>0, b>0, c>0). Czy da się z nich zbudować trójkąt?

Z lekcji matematyki wiadomo, że długości boków muszą spełniać następujące nierówności:

a+b>c

b+c>a

c+a>b

Oczywiście warunki te muszą być spełnione jednocześnie. Jeśli są spełnione - trójkąt można zbudować, w przeciwnym przypadku nie można.

Początek algorytmu jest oczywisty:

Teraz musimy zapisać te trzy warunki w jednym

W skrzynce tej zapisany jest warunek: (a+b>c) and (b+c>a) and (c+a>b). Jeśli warunek ten jest spełniony to da się zbudować trójkąt, w przeciwnym przypadku - nie. W poniższym algorytmie końcowe komunikaty z braku miejsca są lakoniczne. W programie ELI należy je rozbudować do pełnych zdań.

Cały algorytm przedstawia się następująco:

Boki trójkąta

Specyfikacja

  • Wejście: a, b, c - długości odcinków (a>0, b>0, c>0)
  • Wyjście: komunikat "Z tych odcinków można zbudować trójkąt" lub komunikat "Z tych odcinków nie można zbudować trójkąt"

Schemat blokowy

Zadania

  1. Stwórz algorytm stwierdzający, że z odcinków o danych długościach zbuduje się lub nie zbuduje się trójkąt prostokątny.
  2. Stwórz algorytm stwierdzający, że z odcinków o danych długościach zbuduje się trójkąt równoboczny, równoramienny, dowolny
  3. Połącz algorytmy z zadania 1 i zadania 2.

Pętle

Pierwszą pętlę już widziałeś w algorytmie, który umożliwiał wpisanie poprawnej długości boku w przypadku wpisania niedodatniej liczby. Wtedy też poznałeś zalety pętli - przynajmniej teoretycznie. Czas na praktykę!

Na początek coś prostego: sumowanie dwóch liczb:

Proste! To jeszcze: sumowanie trzech liczb:

Nadal: proste! Wierzę, że cierpliwości starczyłoby Ci nawet dla dziesięciu liczb, algorytm nie byłby bardziej skomplikowany, tyle że dłuższy. Co by było jednak, gdybyśmy nie widzieli z góry, ile liczb trzeba zsumować? Użytkownik najpierw wprowadzałby ile liczb chce zsumować, a następnie - liczby.

Być może myślisz o czymś w stylu:

Ten algorytm ma tylko jedną zaletę: działa dla dwóch, trzech, czterech składników. Niestety poza tym ma same wady: poprawienie go dla pięciu składników jest czasochłonne (wyobraź sobie sumowanie 100 liczb), w dwóch miejscach jest mało elegancki (niezależnie do n wczytanie a oraz b zawsze następuje, podobnie jak sumowanie). Tę ostatnią wadę można naprawić otrzymując ładniejszą wersję:

Niewątpliwie algorytm ten jest krótszy, poprawny oraz bardziej efektywny. Zwróć uwagę, że tylko raz występuje klocek z dodawaniem, podobnie rzecz ma się z wprowadzaniem składników. Spróbuj się domyśleć dlaczego na początku algorytmu inicjowane są zmienne c oraz d.

Co trzeba zrobić, żeby móc dodawać 5 lub więcej składników? Niestety - bardziej rozbudować algorytm. Gdybyśmy jednak zastosowali pętlę ten sam algorytm dodałby dwie liczby jak i sto.

W pętli jaką zastosujemy ważną rolę będzie odgrywać zmienna, która będzie liczyła ile razy jeszcze trzeba wykonać pętlę. W naszym przypadku rolę tę będzie pełnić n. Pętlę będziemy powtarzać, zmniejszając za każdym razem n o 1, aż w końcu osiągnie wartość 0, co będzie znaczyło, że pętlę należy zakończyć. Oto nasz algorytm:

Sumowanie n liczb (n>0)

Specyfikacja

  • Wejście: n - liczba składników (n>0), s1..sn - ciąg n składników
  • Wyjście: Suma - suma n składników

Schemat blokowy

Jak widać przed wejściem do pętli inicjujemy zmienną (n), która będzie pamiętała ile razy jeszcze trzeba wywołać pętlę. W pętli zaś wczytujemy kolejny składnik (s - lepsza nazwa: skladnik), następnie zmniejszamy liczbę składników, które jeszcze trzeba wczytać i dodajemy ten wczytany do aktualnej sumy. Na koniec pętli sprawdzamy, czy został jeszcze jakiś składnik do wczytania. Jeśli tak, to pętlę wykonujemy jeszcze raz, w przeciwnym przypadku kończymy pętlę i wypisujemy sumę.

Zauważ, że podany algorytm jest skuteczny zarówno dla jednego składnika jak i dla stu - jest uniwersalny.

Jest jeszcze jedna ciekawa rzecz: warunek jest sprawdzany na końcu pętli. Oznacza to, że pętla wykona się co najmniej raz. Czasami nie jest to wygodne. W naszym przypadku można byłoby dopuścić sytuację, w której n=0 i przyjąć, że wtedy Suma=0. W taki przypadku jednak pętla nie powinna nawet raz się wykonać. Żeby to osiągnąć należałoby sprawdzić warunek na początku pętli jak w poniższym algorytmie.

Sumowanie n liczb (n>=0)

Specyfikacja

  • Wejście: n - liczba składników (n>=0), s1..sn - ciąg n składników
  • Wyjście: Suma - suma n składników

Schemat blokowy

Zadania

  1. Stwórz algorytm, który policzy średnią z n liczb (n>0).
  2. Stwórz algorytm, który policzy liczby dodatnie wprowadzone przez użytkownika (użytkownik wprowadza dowolne liczby nieujemne, aż do wprowadzenia liczby 0, która kończy wprowadzenie danych).
    Rozwiązanie
  3. Stwórz algorytm, który policzy liczby podzielne przez 5 wprowadzone przez użytkownika (użytkownik wprowadza dowolne liczby całkowite, aż do wprowadzenia liczby 0, liczba "0" nie wpływa na wynik).

Maksimum

Na początek coś prostego. Spróbujmy z dwóch liczb a, b wyznaczyć większą (max).

A teraz to samo dla trzech liczb a, b, c.

Należy zauważyć, że po wczytaniu danych przyjmujemy (przynajmniej na chwilę), że pierwsza z wprowadzonych liczb jest największa. Następnie sprawdzamy, czy druga jest większa od naszego maksimum. Jeśli tak, to zmieniamy wartość największą na sprawdzaną liczbę, w przeciwnym przypadku nic nie robimy. Na koniec tak samo postępujemy z trzecią liczbą.

Postępowanie to da się uogólnić dla dowolnej liczby danych.

Wyznaczenie największej liczby z n liczb (n>0)

Specyfikacja

  • Wejście: n - liczba liczb (n>0), s1..sn - ciąg n liczb
  • Wyjście: max - największa z n liczb

Schemat blokowy

Zauważ, że pierwsza liczba jest od razu podstawiona jako max.

Zadania

  1. Stwórz algorytm, który wyznaczy liczbę najmniejszą z wprowadzonych n liczb (n>0).
  2. Stwórz algorytm, który wyznaczy liczbę drugą z największych z wprowadzonych n liczb (n>1).
  3. Stwórz algorytm, który wyznaczy liczbę drugą z najmniejszych z wprowadzonych n liczb (n>1).

Liczby pierwsze

Na początek przypomnijmy sobie co to jest liczba pierwsza. Liczba naturalna większa od 1, która ma dokładnie dwa dzielniki: 1 oraz samą siebie jest liczbą pierwszą. Pozostałe liczby naturalne większe od 1 są złożone. Liczby 0 oraz 1 nie są ani złożone ani pierwsze.

Z definicji wynika, że n jest liczbą pierwszą, gdy żadna z liczb 2, 3, ..., n-1 nie jest dzielnikiem liczby n. Jeśli zaś choć jedna z liczb 2, 3, ..., n-1 jest dzielnikiem liczby n to liczba ta jest złożona. Należy więc sprawdzić (oczywiście w pętli) podzielność liczby n przez kolejne liczby od 2 do n. Jeśli któraś z nich okaże się czynnikiem n, to będzie oznaczać, że n jest liczbą złożoną. Jeśli zaś żadna z nich nie będzie dzielnikiem n, to liczba jest liczbą pierwszą.

Poza oczywistą zmienną n użyjemy pomocniczej zmiennej dziel (skrót od dzielnik). Będziemy przechowywać w niej liczbę przez którą będziemy dzielić liczbę n.

Na początku zainicjujemy zmienną dziel wartością 2 (podzielności przez 1 nie ma sensu sprawdzać) oraz wczytamy liczbę n.

Dalej zasadnicza część algorytmu odbywa się w pętli. Na początku sprawdzamy, czy już wyczerpaliśmy dzielniki. Jeśli tak, to musi to być liczba pierwsza. Jeśli nie, to sprawdzamy podzielność n przez dziel. Jeśli reszta z dzielenia liczby n przez dziel będzie rożna od 0 (a więc większa od 0), to zwiększymy dzielnik o 1 i ponownie wykonamy pętlę. Jeśli zaś reszta będzie równa 0 znaczy to, że liczba jest liczbą złożoną i kończymy pętlę.

Sprawdzenie czy liczba jest liczbą pierwszą

Specyfikacja

  • Wejście: n - liczba naturalna (n>1)
  • Wyjście: "Liczba pierwsza" albo Liczba złożona"

Schemat blokowy

Sprawdź działanie algorytmu dla liczb pierwszych 2, 3, 5, 23, 101 oraz złożonych 4, 9, 12, 25, 99, 40001.

Optymalizacja

Po pierwsze

Sprawdź działanie algorytmu dla liczby 4001.

Po pewnym czasie zmienna dziel osiągnie wartość 200. Zastanówmy się, czy dalsze obliczenia mają sens. Jeśli liczba 4001 jest złożona, to jej dzielnik musi być większy od 200, czyli co najmniej 201. Policzmy 201*201=40401, a to jest liczba większa od 4001. Oznacza to, że 4001 nie ma dzielników większych od 200, czyli (dla mniejszych sprawdził nasz algorytm) 4001 jest liczbą pierwszą.

Zmodyfikuj warunek dziel<n? uwzględniając powyższą obserwację.

Po drugie

Załóżmy, że pętla wykonała się już jeden raz. Oznacza to, że liczba nie jest podzielna przez 2. Czy jest więc sens sprawdzać podzielność tej liczby przez 4, 6, 8 itd?

Zmodyfikuj przypisania dziel:=2 oraz dziel:=dziel+1 uwzględniając powyższą obserwację.

Czy algorytm działa do liczb parzystych? Zmodyfikuj go tak, aby działał prawidłowo dla wszystkich liczb naturalnych większych od 1.

Po trzecie

Na podobnej zasadzie: jeśli liczba nie dzieli się przez 3, to nie dzieli się przez wielokrotności liczby 3 tj: 6, 9, 12 itd. Uwzględniając poprzedni punkt można zauważyć, że wszystkie ewentualne dzielniki można zapisać w postaci: 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5. Z tych liczb tych tylko 6k+1 oraz 6k+5 nie są podzielne, ani przez 2, ani przez 3. Przez pozostałe nie ma sensu sprawdzać podzielności, jeśli wcześniej sprawdziliśmy podzielność przez 2 oraz przez 3.

Algorytm będzie składał się z trzech części.

  1. Sprawdzenie, czy n jest równe 2 lub 3. Jeśli tak to: Liczba pierwsza. Koniec algorytmu.
  2. Sprawdzenie, czy n jest podzielne przez 2 lub 3. Jeśli tak to: Liczba złożona. Koniec algorytmu.
  3. Sprawdzenie w pętli podzielności dla pozostałych liczb. W każdej pętli po dwie (maksymalnie) liczby: 6k+1, 6k+5.

co prowadzi nas do...

Sprawdzenie czy liczba jest liczbą pierwszą (z "małym" błędem)

Specyfikacja

  • Wejście: n - liczba naturalna (n>1)
  • Wyjście: "Liczba pierwsza" albo Liczba złożona"

Schemat blokowy

Sprawdź działanie algorytmu dla różnych liczb. Znajdź liczbę złożoną, którą algorytm klasyfikuje jako liczbę pierwszą. Popraw algorytm!

Po czwarte

Uogólniając powyższe rozumowanie otrzymujemy algorytm zwanym Sitem Eratostenesa. Opisu poszukaj na Wikipedii.

Zadania

  1. Stwórz algorytm, który wypisze wszystkie dzielniki liczby naturalnej n (n>0).
  2. Stwórz algorytm, który sprawdzi czy liczba naturalna n (n>0) jest liczbą doskonałą.
  3. Stwórz algorytm, który wypisze liczby pierwsze z przedziału [min, max], gdzie min>1.

Algorytm Euklidesa

Z lekcji matematyki zapewne pamiętasz algorytm Euklidesa pozwalający w stosunkowo szybki sposób wyznaczyć największy wspólny dzielnik dwóch liczb naturalnych tam, gdzie metoda rozkładu na czynniki pierwsze wydaje się zbyt długa.

Mamy dwie dodatnie liczby naturalne x oraz y (x>=y). NWD(x,y) można wyznaczyć wykonując następujący algorytm (x mod y oznacza resztę z dzielenia x przez y):

  1. Wczytaj x.
  2. Wczytaj y.
  3. Przypisz reszta:=x mod y.
  4. Jeśli reszta=0, to wynikiem działania algorytmu jest y.
  5. W przeciwnym przypadku przypisz x:=y oraz y:=reszta
  6. Skocz do punktu 3

Powyżej algorytm Euklidesa został zapisany w postaci znanej Ci listy kroków. Algorytmy można zapisywać jeszcze w innej postaci: pseudokod. Algorytm Euklidesa w pseudokodzie mógłby wyglądać następująco:

  wczytaj x
  wczytaj y
  reszta:=x mod y
  dopóki reszta<>0 powtarzaj
      x:=y
      y:=reszta
      reszta:=x mod y
  wypisz y

Postać ta jest już bliska językom programowania. Wcięcie trzech linijek nie jest przypadkowe. Wskazuje na to, co jest powtarzane w pętli.

Zadania

  1. Stwórz algorytm, który wyznaczy wyznaczyć największy wspólny dzielnik dwóch liczb naturalnych różnych od 0.
  2. Stwórz algorytm, który skróci ułamek a/b (obie liczby dodatnie). Podaj go w najprostszej postaci.

Tablice w algorytmach

Porządkowanie dwóch liczb jest proste. Także trzech liczb, a może nawet czterech, a już pięciu... A przecież komputery potrafią sortować znacznie większe ilości danych. Jak to zrobić? Używanie zmiennych a1, a2, a3, ... an nie wchodzi w rachubę. I tu pojawiają się tablice.

Tablica to jedna zmienna, która przechowuje n liczb (lub innych obiektów). W odróżnieniu od innych typów danych po nazwie zmiennej w nawiasie kwadratowym należy określić, którą liczbę z tablicy chcemy użyć.

Przykłady poprawnego użycia tablic:

  • t[0]:= 3
  • t[5]:= 2*n+1
  • skladnik:=a[3]+a[4]
  • a[i+2]:=3*a[i]+a[i+1]

Przykłady niepoprawnego użycia tablic (przy założeniu, że elementy w tablicy numerujemy od 0 do n-1):

  • t[1.5]:=5
  • w[4]:=2*w
  • tab[-1]:=3+tab[0]
  • tab[n+1]:=tab[n]

Nie wolno odwoływać się do elementów o nieistniejących numerach! Takie działanie spowoduje błąd. Niebezpieczne jest również korzystanie elementów tablicy, które wcześniej nie zostały zainicjowane.

Sumowanie elementów tablicy

Specyfikacja

  • Wejście: n - długość tablicy (n>0)
  • tab[0], tab[1], ..., tab[n-1] - liczby
  • Wyjście: suma - suma liczb z tablicy tab

Lista kroków

  1. Przypisz suma:=0
  2. Przypisz k:=0
  3. Jeżeli k=n to skocz do punktu 7
  4. Przypisz suma:=suma+tab[k]
  5. Przypisz k:=k+1
  6. Skocz do punktu 3
  7. Wypisz suma
  8. Koniec

W tablicy wygodnie jest trzymać współczynniki wielomianu. Wystarczy założyć, że wyraz wolny przechowywany jest w w[0], współczynnik przy x w w[1], współczynnik przy x2 w w[2] itd.

Wyznaczanie wartości wielomianu dla danego x (z BŁĘDEM)

Specyfikacja

  • Wejście: n - stopień wielomianu (n>=0)
  • w[0], w[1], ..., w[n] - współczynniki wielomianu
  • x - argument, dla którego policzona zostanie wartość wielomianu
  • Wyjście: y - wartość wielomianu w dla x

Lista kroków

  1. Przypisz y:=w[0]
  2. Przypisz k:=1
  3. Jeżeli k>n skocz do punktu 8
  4. Przypisz y:=y+w[k]*x
  5. Przypisz x:=x*x
  6. Przypisz k:=k+1
  7. Skocz do punktu 3
  8. Wypisz y
  9. Koniec

Zadania

  1. Zrealizuj algorytm sumujący dwa wielomiany (oba stopnia n, w których współczynniki przy najwyższych potęgach nie są przeciwne; użyj trzech tablic).
  2. Zrealizuj algorytm sumujący dwa wielomiany (oba stopnia n).
  3. Zrealizuj algorytm sumujący dwa wielomiany (stopnia n1 oraz n2).
  4. Zrealizuj algorytm wyznaczający resztę z dzielenia wielomianu stopnia n (n>0) przez wymian x-a.

Tablice w ELI

Niestety w ELI nie możemy używać tablic w sposób ogólnie przyjęty w niemal wszystkich językach programowania. W dodatku mamy do dyspozycji tylko jedną tablicę, choć dwuwymiarową (dotąd posługiwaliśmy się tablicami jednowymiarowymi, w przypadku tablic dwuwymiarowych należy używać ich np. t[1,5]=7 - pierwsza liczba w nawiasie oznacza numer wiersza, a druga kolumny, można też ten napis interpretować odwrotnie - najpierw kolumna, a potem wiersz).

Porównanie operacji na tablicach w algorytmach i ELI

Algorytm Klocek Uzupełnienie pól Komentarz
skladnik:=tablica[i]

Numer kolumny może być w zasadzie dowolny. Warto jednak ustalić jeden i ten sam dla określonej tablicy.

Dla innych tabel należy użyć innych numerów kolumn. Jest to sposób na użycie wielu tabel jednowymiarowych w ELI.

tablica[i]:=liczba

Objaśnienie "Kolumna" patrz wyżej.

Zamiast liczby może być dowolne wyrażenie np. sqrt(i).

 

tablica[0]:=4
tablica[1]:=1
tablica[2]:=7
tablica[3]:=4
tablica[4]:=1
tablica[5]:=0
tablica[6]:=8
tablica[7]:=9
tablica[8]:=5
tablica[9]:=5

Wczytywanie do tablicy kolejnych liczb jest męczące.

Dane można wczytać z pliku, który w ELI nazywa się taśmą.

Należy określić, które liczby mają być wczytane (w przykładzie 10 pierwszych liczby z taśmy - numeruje się od 0) oraz kolumnę tablicy i pierwszy wiersz tablicy, od którego liczby zostaną zapisane.

Taśma

Pozostaje pytanie skąd wziąć taśmę? Oto przepis:

  1. W Notatniku napisz kilka (-naście) liczb - każda w osobnej linii.
  2. Zapisz dokument w formacie TXT na dysku.
  3. W ELI z menu Plik wybierz Taśma / Import.
  4. Wskaż plik, który utworzyłeś w punkcie nr 2.

Można też wczytać plik z rozszerzeniem TAP.

Zadania

  1. Zrealizuj algorytm sumujący liczby z tablicy.
  2. Zrealizuj algorytm obliczający średnią liczb z tablicy.
  3. Zrealizuj algorytm wyznaczający największą liczbę w tablicy.
  4. Zrealizuj algorytm wyznaczający drugą największą liczbę w tablicy.

Wielomiany

Przygotowanie taśmy ze współczynnikami wielomianów

Przed przystąpieniem do zadań przygotuj plik tekstowy ze współczynnikami dwóch wielomianów według poniższego przykładu dwóch wielomianów stopnia 5:

5
5
1
2
3
4
5
6
-1
2
-3
4
-5
6

Oznacza to następujący porządek:

  1. Stopień pierwszego wielomianu
  2. Stopień drugiego wielomianu
  3. Współczynniki pierwszego wielomianu począwszy od wyrazu wolnego
  4. Współczynniki drugiego wielomianu począwszy od wyrazu wolnego

Wczytanie wielomianów

Należy wykorzystać następujące klocki:

brak Na początek należy ustawić przestawić znacznik taśmy na początkowy (o numerze 0) element. Jeśli tego nie zrobimy pierwszym elementem taśmy będzie pierwszy element z poprzedniego uruchomienia algorytmu.

Z taśmy można odczytać:

  • jedną liczbę i przypisać ją do zmiennej (w przykładzie x),
  • kilka (i więcej) liczb i umieścić je w tablicy (patrz poniżej).

Po odczycie liczby znacznik automatycznie ustawia się na następnym elemencie.

W przypadku zapisu z taśmy do tablicy nie jest brany pod uwagę znacznik taśmy.

Należy określić numer pierwszego oraz ostatniego elementu na taśmie oraz numer kolumny i pierwszego wiersza w tablicy.

Zadania

  1. Zrealizuj algorytm sumujący dwa wielomiany (oba stopnia n, w których współczynniki przy najwyższych potęgach nie są przeciwne; użyj trzech tablic).
  2. Zrealizuj algorytm sumujący dwa wielomiany (oba stopnia n).
  3. Zrealizuj algorytm sumujący dwa wielomiany (stopnia n1 oraz n2).
  4. Zrealizuj algorytm wyznaczający resztę z dzielenia wielomianu stopnia n (n>0) przez wymian x-a.

Klasówka z e-matematyki III

Klasówka będzie obejmować następujące zagadnienia:

Lp Wymaganie Umiejętność Status
1 1.4 Uczeń oblicza potęgi o wykładnikach wymiernych i stosuje prawa działań na potęgach o wykładnikach wymiernych Test
1.5 Uczeń wykorzystuje podstawowe własności potęg (również w zagadnieniach związanych z innymi dziedzinami wiedzy, np. fizyką, chemią, informatyką) ?
2 1.6 Uczeń wykorzystuje definicję logarytmu i stosuje w obliczeniach wzory na logarytm iloczynu, logarytm ilorazu i logarytm potęgi o wykładniku naturalnym

Test

3 1.9 Uczeń wykonuje obliczenia procentowe, oblicza podatki, zysk z lokat (również złożonych na procent składany i na okres krótszy niż rok)

Test

4 4.14 Uczeń szkicuje wykresy funkcji wykładniczych dla różnych podstaw

Test

5 4.15 Uczeń posługuje się funkcjami wykładniczymi do opisu zjawisk fizycznych, chemicznych, a także w zagadnieniach osadzonych w kontekście praktycznym

Test

6 7.1 Uczeń stosuje zależności między kątem środkowym i kątem wpisanym

Test

7 7.2 Uczeń korzysta z własności stycznej do okręgu i własności okręgów stycznych

Test

8 7.3 Uczeń rozpoznaje trójkąty podobne i wykorzystuje (także w kontekstach praktycznych) cechy podobieństwa trójkątów

Test

9 7.4 Uczeń korzysta z własności funkcji trygonometrycznych w łatwych obliczeniach geometrycznych, w tym ze wzoru na pole trójkąta ostrokątnego o danych dwóch bokach i kącie między nimi Zadania
6.1 Uczeń wykorzystuje definicje i wyznacza wartości funkcji sinus, cosinus i tangens kątów o miarach od 0° do 180° Zadania
6.5 Uczeń znając wartość jednej z funkcji: sinus lub cosinus, wyznacza wartości pozostałych funkcji tego samego kąta ostrego Test

Status

Lp Status Objaśnienie
1 ? Pusty dokument lub parę zadań
2 Zadania Kilka (-naście zadań). Test w przygotowaniu (?)
3 Test Kilka (-naście zadań). Test gotowy. Możliwe niewielkie zmiany

Sposoby radzenia sobie w trudnych sytuacjach – bibliografia (uczeń)

Bocheńska Katarzyna: Mówię do ciebie, człowieku. Warszawa: WSiP, cop. 2003

Zawiera m.in.: czym jest komunikowanie między ludźmi?, komunikowanie „twarzą w twarz”, asertywność w komunikacji międzyludzkiej.

Eichelberger Wojciech, Szczawiński Wojciech: Alchemia „Alchemika”. Warszawa: „Drzewo Babel”, 2001

W. Eichelberger  w rozmowie z W. Szczawińskim poruszają tematy : kondycja psychiczna, lęki, pragnienia, pokora, negatywne emocje, agresja, przemoc, gniew, współczucie. Refleksje dotyczące psychiki człowieka.

Gęsicki Janusz: Jak nie zwariować w szkole. Warszawa: WSiP, 1999 Poradnik dla uczniów.

Kołakowski Leszek: Mini wykłady o maxi sprawach. Kraków: Wydawnictwo „Znak”, 2008

M.in.: o tolerancji, o przemocy, o wolności, o wybaczeniu, o zawiści, o sprawiedliwości, o wrogu i o przyjacielu.

Moneta-Malewska Maria: Dla siebie i dla innych. Warszawa: WSiP, cop. 2003

Zawiera m.in.: akceptacja, tolerancja, wolność, przyjaźń,  partnerstwo, stres.

Szyszkowska Maria: Zagubieni w codzienności. Wyd. 3 uzup. Warszawa: Wydawnictwo Książkowe „Twój Styl”, 2000

Zawiera m.in.: poczucie zagubienia, poczucie odrębności, poczucie sprawiedliwości, pozory prawdy, przełamywanie nieszczerości, trudności w porozumiewaniu się.

Szyszkowska Maria: W poszukiwaniu sensu życia. Warszawa: Wydawnictwo Książkowe „Twój Styl”, 1997

Zawiera m.in.: lęki i osamotnienie, wartość kontaktów z drugim człowiekiem, więzi ogólnoludzkie, chorzy, wolność.

Zimbardo Philip G.: Nieśmiałość. Co to jest? Jak sobie z nią radzić? Wyd. 2 popr. Warszawa: Wydawnictwo Naukowe PWN, 2000

Gościmy

Odwiedza nas 67 gości oraz 0 użytkowników.

(c) 1998-2017 III Liceum Ogólnokształcące im. Żołnierzy Obwodu Łomżyńskiego AK w Łomży, ul. Senatorska 13, 18-400 Łomża, tel 86-216-6720