Algorytm. Obliczanie pola trójkąta

Stworzymy algorytm obliczający pole trójkąta.

Rozpoczniemy od zapisania specyfikacji problemu.

Specyfikacja algorytmu obliczającego pole trójkąta

Problem: Obliczanie pola trójkąta.
Dane: a, b, c – trzy dowolne liczby
Wynik:
Jeśli liczby a, b, c są długościami boków trójkąta to wyznaczamy – pole tego trójkąta. Jeśli liczby a,b,c nie tworzą trójkąta wyprowadź komunikat, że dane liczby nie są długościami boków żadnego trójkąta.

Metoda obliczania pola trójkąta

Do obliczania pola trójkąta wykorzystamy wzór zwany wzorem Herona.

gdzie p oznacza połowę długości obwodu trójkąta, czyli p=(a+b+c)/2

Zastanowimy się teraz jakie warunki muszą spełnić liczby a, b i c aby były długościami boków trójkąta. Otóż aby a, b, c były długościamy boków trójkąta muszą być spełnione warunki:

p-a>0
p-b>0
p-c>0
gdzie p – obwód trójkąta

Zatem zanim przystąpimy do obliczania pola trójkąta musimy zbadać czy a,b,c tworzą trójkąt. W tym celu najpierw musimy obliczyć obwód trójkąta. Następnie zbadać jak powyżej …….

Posiadamy zatem już wszystkie informacje, niezbędne do stworzenia algorytmu.

Jak przedstawić nasz algorytm? Pamiętamy, iż istnieją różne sposoby zapisywania algorytmów. My przedstawimy teraz nasz algorytm w postaci listy kroków.

Lista kroków

Krok 1. Oblicz wartość wyrażenia p:=(a+b+c)/2
Krok 2. Jeśli p-a>0 i p-b>0 i p-c> 0 to przejdź do Kroku 3. Jeśli warunki nie są spełnione wyprowadź komunikat, że liczby a,b,c nie są długościami boków trójkąta i zakończ wykonywanie algorytmu.
Krok 3. Oblicz i wypisz wartość wyrażenia S= …..

Schemat blokowy algorytmu

Algorytmy. Tablice jednowymiarowe

 

ALGORYTMY OBSŁUGI TABLIC

Tablicą nazywamy złożoną strukturę danych, która zawiera zbiór elementów tego samego typu.Wyróżniamy:
tablice jednowymiarowe
tablice wielowymiarowe

TABLICE JEDNOWYMIAROWE

Tablica jest to zbiór elementów tego samego typu. Każdy element tablicy jest identyfikowany przez jego numer (indeks). Każdy element tablicy posiada swoją wartość.
Oto tablica o nazwie „t” zawierająca 5 elementów, liczby 5, 11, 8, 3, 2:

Do poszczególnych elementów tablicy uzyskujemy dostęp poprzez podanie nazwy tablicy oraz w nawiasach kwadratowych wartość indeksu (numer żądanego elementu). W naszej tablicy o nazwie t:

t[1] = 5
 t[2] = 11
 t[3] = 8
 t[4] = 3
 t[5] = 2
Element t[i] dla i równego 4 wynosi 3, dla i równego 2 wynosi 11.

Przykład

Opracuj algorytm wypełniający tablicę k – elementową.

Ponieważ tablica ma k- elementów, a więc k- razy nastąpi wczytywanie elementu, stąd zastosowanie iteracji.

Schemat blokowy algorytmu wypełniania tablicy elementami podanymi przez użytkownika:

Przykład
Opracuj algorytm wypisujący elementy tablicy k- elementowej.

Przykład
Zbuduj algorytm sumujący elementy tablicy n- elementowej.

Przykład
Zbuduj algorytm liczący średnią arytmetyczną elementów tablicy.

Przykład
Do tablicy wczytano k-elementów. Wydrukuj położenie i wartość elementu najmniejszego (zakładamy, że elementy są różne).
Przykład
Wczytaj elementy do tablicy k- elementowej, a następnie wypisz je w odwrotnej kolejności.

Przykład
Z tablicy zawierającej k-elementów wybierz elementy podzielne przez 3. Oblicz ich ilość, sumę i średnią.

Przykład
Wczytaj elementy do tablicy k- elementowej. Wydrukuj tę tablicę. Zamień pierwszy z ostatnim i wydrukuj tablicę po modyfikacji.

Przykład
Uporządkuj elementy tablicy k- elementowej, w kolejności od najmniejszego do największego.Aby uporządkować tablicę należy posłużyc się jedną z metod sortowania. My wykorzysamy sortowanie bąbelkowe.

ZADANIA DO SAMODZIELNEGO ROZWIĄZANIA:



Ćwiczenie 1
Opracowany w ćwiczeniu 3 algorytm zmodyfikuj tak, by wynikiem była suma elementów większych od 10.


Ćwiczenie 2
Opracuj algorytm liczący średnią arytmetyczną elementów dodatnich tablicy.


Ćwiczenie 3
Zbuduj algorytm wyszukiwania elementu maksymalnego w tablicy.
Ćwiczenie 4
Opracuj algorytm
wczytujący elementy tablicy k-elementowej
wyszukujący element minimalny
wypisujący elementy tablicy i element minimalny

PL/SQL. Rodzaje bloków

WSTĘP DO PL/SQL

Rodzaje bloków PL/SQL:

1. bloki anomimowe (nienazwane)

  • declared inline

2. bloki nazwane (podprogramy)

Blok anonimowy

Uruchamiamy program Oracle SQL Developer. Wpisujemy poniższy kod:

BEGINDBMS_OUTPUT.PUT_LINE(‚Hello World!’);END;
By wykonać kod wciskamy przycisk Run Script (zielona strzałka z kartką) lub wciskamy klawisz F5. Zobaczymy informację:


PL/SQL procedure successfully completed.

Aby wyświetlić efekt działania programu w oknie konsoli trzeba ustawić zmienną SERVEROUTPUT. W związku z tym przed BEGIN dodajemy

SET SERVEROUTPUT ON

Nasz program powinien wyglądać teraz tak:
SET SERVEROUTPUT ON
BEGINDBMS_OUTPUT.PUT_LINE(‚Hello World!’);
END;



W dolnym oknie Script Output powyżej informacji PL/SQL procedure successfully completed powinniśmy zobaczyć nasz napis Hello World!

SQL. Pobieranie danych z kilku tabel: natural join, join, using, using on



Tabele:
pracownicy
pracownik_id
imie
nazwisko
stanowisko_id
kierownik_id

stanowiska
stanowisko_id
nazwa_stanowiska
kierownik_id
lokalizacja

Zadanie 1
Przygotuj raport o wszystkich pracownikach pracujących w firmie i  ich stanowiskach.

Informacje o pracownikach i ich stanowiskach są umieszczone są w rożnych tabelach. Należy napisać zapytanie SQL pobierające dane z dwóch różnych tabel używając połączeń JOINS. To zapytanie będzie pobierało dane stanowisko_id z tabeli pracownicy a nazwa_stanowiska z tabeli Stanowiska używając stanowisko_id jak kolumnę wspólną.

Wynikiem zapytania będzie pojedynczy raport zawierający następujące kolumny: pracownik_id, stanowisko_id, nazwa_stanowiska

Istnieje kilka typów połączeń JOINS, których możemy używać:

  1. połączenia naturalne z klauzulą NATURAL JOIN
  2. Samopołączenia
  3. Non equijon
  4. outer joins:
    left outer joins
    right outer joins
    pelne outer joins
  5. cross joins

NATURAL JOIN

SELECT pracownik_id, imie, stanowisko_id, nazwa_stanowiska

FROM pracownicy NATURAL JOIN stanowiska;

Zauważmy iż tabela stanowiska jest połaczona z pracownicy poprzez stanowisko_id, które jest jedyną kolumną o tej samej nazwie w obu tabelach. Jeśli są inne wspólne pola połaczenie użyje ich wszystkich.
Możemy dodać ograniczenie używając klauzuli WHERE.

Zadanie 2
Raport nazw wydziału, w których zatrudnieni są pracownicy.

 

USING

Tabele:
pracownicy
pracownik_id
imie
nazwisko
stanowisko_id
kierownik_id

wydzialy
wydzial_id
wydzial_nazwa
kierownik_id
lokalizacja

Chcemy stalenić wydziały pracowników. Aby to wykonac należy porównać wartości w kolumnie stanowisko_id w tabeli stanowiska ze stanowisko_id w tabeli pracownicy. Jeśli wspólnymi kolumnami są dwie kolumny stanowisko_id oraz kierownik_id, naturalne połączenie użyje obuj tych kolumn do pokazania wyniku. Ale my chcemy połączyć te tabele za pomocą tylko kolumny stanowisko_id. Aby to wykonać musimy użyć klauzuli USING by podać tylko jedną kolumnę, która ma zostac użyta do połączenia.
Relacja pomiędzy tabelą pracownicy i stanowiska to wiele-do-jednego. Wartość w stanowisko_id kolulmnie w obu tabelach musi być taka sama. Częśto taki typ połączeń obejmuje klucz głóny i obcy.


SELECT pracownik_id, nazwisko, nazwa_wydzialu, wydzial_id
FROM  pracownicy JOIN wydzialy USING (wydzial_id)

W tym zapytaniu kolumna wydzial_id w tabelach pracownicy i wydziały są połączone, a zatem nazwa_wydzialu gdzi epracownik pracuje zostala wyświetlona.
Kolumny pracownik_id i nazwisko należą do tabeli pracownicy, podczas gdy nazwa_wydzialu należy do tabeli wydziału – i wydzial_id należy do obu tych tabel. Dlatego używanie przedrostka z nazwą tabel  rozwiązuje niejednoznaczność i zwiększa szybkość wykonywania zapytania – gdyż mówi serverowi Oracle gdzie znajdzie kolumnę. Jednak określanie nazw kolumn używając nazw tabel może być czasochołonee, szczególnie gdy nazwy tabel są długie np


zbyt_dluga_nazwa_tabeli.nazwa_kolumny

Zamiast tego można używać aliasów tabel. tak jak alias kolumny daje kolumnie nowa nazwę, tak alias tabeli daje tabeli inną nazwę np

t.nazwa_klumny

Aliasy tabel pomagają zmiejszyć kod SQL.

Pamiętaj że nie możesz określić kolumny, która jest użwana w klauzuli USING. Na przykład to zapytanie spowoduje wyświetlenie błędu:

SELECT l.miasto.d.nazwa_wydzialu
FROM lokalizacje l JOIN wydziały d
USING (lokalizacja_id)
WHERE d.lokalizacja_id =1400;

Nie można użyć aliasu  kolumny lokalizacja_id  w klauzui WHERE ponieważ kolumna jest użyta w klauzuli USING. Zapytanie powinno wyglądać tak:

SELECT l.miasto.d.nazwa_wydzialu, d.kierownik_id
FROM lokalizacje l JOIN wydziały d
USING (lokalizacja_id)
WHERE lokalizacja_id =1400;


Zauważ, że kierownik_id jest obecne w obu tabelach zarówno pracownicy jak i wydzialy. Jeśli kierownik_id nie będzie miał prefixu tabeli to server wyświetli błąd.



USING ON

Można zastąpić klauzulę USING na klauzulę ON  by uszczegółowić warunek połączenia. Zaletą używania klauzuli ON jest możliwość uszczegółowienia bezwzględnego warunku lub sprecyzowania kolumn do połączenia.


Na przykład, aby złączyć taelę pracownicy i wydziały poprzez kolumnę wydzial_id można napisać takie zapytanie SQL:

SELECT p.pracownicy, p.nazwisko,p.wydzial_id. w. wydzial_id, w.lokazliacja_id
FROM pracownicy p JOIN wydzialy d
ON (p.wydzial_id=w.wydzial_id);

W zapytaniu jeśli wydzial_id w tabeli pracownicy jestrówny z wydział_id w tabeli wydziały, wiersz jest zwracany


ON (p.wydzial_id=w.wydzial_id);


Użycie aliasu tabeli jest konieczne aby określić pasujące kolumny.  


Zadanie 3
Wyświetl raport o wszystkich pracownikach, ich wydziałach i miastach w których się mieszczą.


W tym celu musimy połączyć trzy tabele: pracownicy, wydzialy, lokalizacje


SELECT pracownik_id, city, nazwa_wydzialu
FROM pracownicy p
JOIN wydzialy w
ON w.wydzial_id = p.wydzial_id
JOIN lokalizacje l
ON w.lokalizacja_id = l.lokalizacja_id;


Pierwsze połączenie, ktore jest wykonywane to : pracownicy JOIN wydzialy:


FROM pracownicy p
JOIN wydzialy w
ON w.wydzial_id = p.wydzial_id


Pierwszy warunek połaczenia może odnosić się do kolumn w tabelach pracownicy i wydzialu al enie może odnosić się do kolumn z tabeli lokalizacje.

Drugie połączenie może odnosić się do kolumn z wszsytkich trzech tabel:

JOIN lokalizacje l
ON w.lokalizacja_id = l.lokalizacja_id;

Uwaga. Przykładowy kod można również napisać za pomocą klauzuli USING.

Zadanie 4
Przygotuj raport o numerach lokazlizacji wszystkich pracowników których kirownik ma numer 12.

SELECT p.pracownik_id, p.nazwisko, p.wydzial_id, w.wydzial_id, w.lokazacja_id
FROM pracownicy p JOIN wydzialy w
ON (p.wydzial_id = w.wydzial_id)
AND p.kierownik_id=12;

Do połączenia dodane zostały dodatkowe warunki. Zapytanie pokazuje wykonane połączenie na tabeli pracownicy i wydziały i dodatkowo wyświetla

FROM pracownicy p JOIN wydzialy tylko pracowników których kierowniki ma numer 12

Jako alternatywę możesz też użyć WHERE aby zastosować dodatkowe warunki. Wynik zapytania będzie taki sam

SELECT p.pracownik_id, p.nazwisko, p.wydzial_id, w.wydzial_id, w.lokazacja_id
FROM pracownicy p JOIN wydzialy w
ON (p.wydzial_id = w.wydzial_id)
WHERE p.kierownik_id=12;


















Algorytm Euklidesa

Algorytm Euklidesa czyli algorytm wyznaczania  NWD – największego wspólnego dzielnika dwóch liczb całkowitych.

Zadanie:
Wyznacz największy wspólny dzielnik dwóch liczb naturalnych: a,b.

Przeanalizujmy zadanie. Dane mamy dwie liczby oznaczone jako a i b. Musimy odnaleźć liczbę przez którą dzielą się nasze obie liczby, zarówno a i b. Takich liczb może być wiele – my mamy odszukać największą.

Przykłady
Dane mamy dwie liczby: 4 i 6.
Dla tych liczb wspólnym dzielnikiem będą: 1, 2. Zatem największym wspólnym dzielnikiem obu tych liczb jest liczba 2.

Dane:  12, 9
Wynik: 3

Dane: 304, 304
Wynik: 304

Dane: 700, 21
Wynik:  7

Dane: 11, 76
Wynik: 1

Na tym etapie możemy zastanowić jak wyznaczyliśmy wspólny dzielnik i opracować algorytm. Możemy jednak skorzystać z gotowego rozwiązania, które opracował Euklides.

Algorytm Euklidesa

Wyznaczanie NWD, a więc największego wspólnego podzielnika dwóch liczb naturalnych
zrealizujemy za pomocą algorytmu Euklidesa. Opiera się on na
spostrzeżeniu, że jeśli odejmiemy od większej liczby mniejszą, to ta
mniejsza liczba i otrzymana różnica będą miały taki sam największy
wspólny dzielnik jak pierwotne liczby. Jeśli w wyniku kolejnego
odejmowania otrzymamy parę równych liczb, oznacza to, że znaleźliśmy NWD.

 

Algorytm Euklidesa: schemat blokowy

Przedstawimy teraz algorytm w postaci schematu blokowego. Na początku następuje wczytanie dwóch liczb. Następnie sprawdzamy czy są to takie same liczby. Jeśli bowiem liczby są równe to od razu wiemy iż ich wspólnym dzielnikiem jest ta sama liczba (przykład 3).
Jeśli liczby są różne sprawdzamy która z nich jest większa, by od większej liczby odjąć mniejszą.

 

Schemat blokowy algorytmu Euklidesa
Algorytm Euklidesa. Schemat blokowy

—————–
Powyższy materiał pochodzi z pracy „Algorytmika w gimnazjum”, którą wykonałam podczas studiów. Materiały te przez długi czas były dostępne na stronie kasia315.republika.pl. Strona ta obecnie nie istnieje, a cała jej zawartość została przeniesiona tutaj, czyli pod adres kaluska.pl.

 

Algorytmy. Przykłady i zadania

Poznałeś już kilka przykładów algorytmów. Przeanalizuj je ponownie, a następnie przejdź do wykonywania poniższych zadań.

Zachęcam Cię, abyś po przeczytaniu treści zadania zastanowił się nad rozwiązaniem, a następnie przedstawił algorytm w postaci listy (ciągu) kroków oraz zbudował schemat blokowy. Dopiero po samodzielnej pracy porównaj i dokonaj analizy gotowego schematu przedstawionego na stronie.

Zadanie

Opracuj algorytm obliczający sumę 3 wprowadzonych z klawiatury liczb.Przedstawmy najpierw algorytm w postaci ciągu kroków do wykonania:

  1. Podaj pierwszą liczbę
  2. Podaj drugą liczbę
  3. Podaj trzecią liczbę
  4. Dodaj do siebie liczby i wynik zapamiętaj
  5. Wypisz otrzymany wynik


Algorytm dodawania liczb 1


Czy zwróciłeś uwagę na operację Suma := a+b+c ?
Przypomnijmy, iż jest to znak przypisania i oznacza nadanie zmiennej znajdującej się po jego lewej stronie wartości określonej po prawej stronie.


Algorytm dodawania liczb 2



Działanie algorytmu dodawania liczb

Zadanie
Dane są dwie liczby. Opracuj algorytm wybierający większą z nich, w przypadku gdy są równe wypisz stosowny komunikat.Algorytm wyboru większej liczby



ZadanieZbuduj algorytm obliczający sumę 5 kolejnych liczb naturalnych.Algorytm sumujący 5 kolejnych liczb naturalnych

Zadanie:

Wyznacz NWD- największy wspólny podzielnik dwóch liczb naturalnych a,b. Algorytm EuklidesaWyznaczanie największego wspólnego podzielnika dwóch liczb naturalnych zrealizujemy za pomocą algorytmu Euklidesa. Opiera się on na spostrzeżeniu, że jeśli odejmiemy od większej liczby mniejszą, to ta mniejsza liczba i otrzymana różnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Jeśli w wyniku kolejnego odejmowania otrzymamy parę równych liczb, oznacza to, że znalazłeś NWD.Algorytm Euklidesa. Wyznaczanie NWD- największego wspólnego podzielnika dwóch liczb naturalnych

Algorytm Euklidesa: NWD

Zadanie
Narysuj algorytm sumujący liczby większe od 5 spośród 10 wprowadzonych.


Algorytm sumujący liczby


Zadania

Więcej przykładów i zadań do wykonania znajdziesz tu:

Zadania do samodzielnego wykonania:

  • Opracuj algorytm obliczający kwadrat i sześcian wprowadzonej liczby.
  • Opracuj schemat obliczania średniej n liczb naturalnych.

Rodzaje algorytmów

Rodzaje algorytmów

  • Algorytmy liniowe, czyli  algorytmy sekwencyjne
  • Algorytmy warunkowe, czyli algorytmy z rozgałęzieniami
  • Algorytmy interacyjne, czyli algorytmy z pętlą

Algorytm liniowy, czyli inaczej algorytm sekwencyjny

Algorytm sekwencyjny to algorytm, w którym kolejność wykonywanych czynności jest zawsze taka sama i niezależna od wartości danych wejściowych.

Algorytm warunkowy. Algorytm z rozgałęzieniem

….

Algorytmy. Kurs algorytmiki dla uczniów

Kurs algorytmy dla uczniów, został przygotowany jako wstęp do algorytmiki.

kasia315.republika.pl

Powyższy materiał pochodzi z pracy „Algorytmika w gimnazjum”, którą wykonałam podczas studiów. Materiały te przez długi czas były dostępne na stronie kasia315.republika.pl. Strona ta obecnie nie istnieje, a cała jej zawartość została przeniesiona tutaj, czyli pod adres kaluska.pl.

Kurs zawierał również krókie wizualne prezentacje sposobu wykonania algorytmów (aplety Java). Obecnie większość nowoczesnych przeglądarek domyślnie nie pozwala na  wyświetlenie apletów Java. Jeśi chcesz je zobaczyć i w pełni korzystać ze strony, zmień opcje w swojej przeglądarce.

Kurs algorytmiki dla uczniów

Na kurs składa się kilka lekcji. Całość będzie dostępna już niedługo

Lekcja 1:

 

Algorytmy. Tablice dwuwymiarowe

Algorytmy obsługi tablic dwuwymiarowych
Przykład tablicy dwuwymiarowej:

Do poszczególnych elementów tablicy uzyskujemy dostęp poprzez podanie nazwy tablicy oraz w nawiasach kwadratowych wartość indeksu ( numer żądanego elementu).
I tak w naszej tablicy o nazwie t zapis t[3,4] oznacza element w trzecim wierszu i czwartej kolumnie, czyli element o wartości =3.
   t [1,1] = 2
   t [1,2] =6
   t [1,3] =11
   t [1,4] =0
   t [2,1] =7

 Element t [i, j]  dla i równego 2 i j równego 2 wynosi 5.

Ćwiczenie 1

Opracuj algorytm wypełniający tablicę kwadratową k x k.

Ćwiczenie 2

Odszukaj w tablicy m x n element maksymalny. Wypisz jego położenie i wartość.

 Schemat blokowy

Ćwiczenie 3

Tablica kwadratowa m x n składa się z zer i jedynek. Podaj algorytm wypisujący ile jest zer i ile jedynek.

 Schemat blokowy

Ćwiczenie 4
Zbuduj algorytm sumujący elementy na przekątnej tablicy k x k.

Ćwiczenie 5
Podaj algorytm obliczający sumę i ilość elementów nad przekątną tablicy kwadratowej.

Rozwiąż samodzielnie:

Ćwiczenie 1
Zbuduj algorytm wyznaczania elementu minimalnego tablicy kwadratowej.

Ćwiczenie 2
Narysuj schemat blokowy algorytmu wypisującego z tablicy k x k elementy parzyste. Podaj ilość takich elementów.

Ćwiczenie 3
Zbuduj algorytm podający ilość i średnią arytmetyczną elementów tablicy m x n podzielnych przez 10.

Ćwiczenie 4
Opracuj algorytm wyznaczania elementu minimalnego tablicy kwadratowej.

Specyfikacja algorytmu, czyli specyfikacja problemu algorytmicznego

Wiemy już, co to są algorytmy i jak można je zapisywać.

Specyfikacja algorytmu

Specyfikacja algorytmu [specyfikacja problemu algorytmicznego] to dokładny opis problemu algorytmicznego, który ma zostać rozwiązany, oraz podanie danych wejściowych [dane] i danych wyjściowych [wynik].

Problem: Obliczanie pola trójkąta o danych długościach jego boków
Dane: Trzy liczby: a, b i c, będące długościami boków trójkąta.
Wynik: P – pole trójkąta o bokach o długości a, b,c.

Problem: Obliczanie potęgi liczby naturalnej o wykładniku naturalnym.
Dane:
a – liczba naturalna, podstawa potęgi
b – liczba naturalna, wykładnik potęgi
Wynik:
w – liczba naturalna, wartość a do potęgi b
Problem: Obliczanie średniej arytmetycznej dwóch liczb rzeczywistych.
Dane:
a – liczba rzeczywista
b – liczba rzeczywista
Wynik:
sr – liczba rzeczywista, średnia liczb a, bProblem: Obliczanie wartości wielomianu: Schemat Hornera
Dane wejściowe:
n – nieujemna liczba całkowita – stopień wielomianu
a0, a1, a2, ….,an – n+1 współczynników wielomianu
z – wartość argumentu
Dane wyjściowe:
Wartość wielomianu stopnia n dla wartości argumentu x=z
Problem: Obliczanie wartości bezwzględnej (modułu) danej liczby całkowitej.
Dane:
a – wprowadzana liczba całkowita;
Wynik:
M – obliczana wartość bezwzględna.