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:

 

Sposoby zapisu algorytmu

Algorytmy powinny być tak przedstawiane, aby było możliwe ich jednoznaczne odczytanie i zastosowanie. Niektóre algorytmy można opisać słownie korzystając z języka potocznego. Jest to proste zwłaszcza wtedy, gdy wykonawcą algorytmów ma być człowiek. Pamiętajmy jednak, iż informatyka zajmuje się opracowywaniem algorytmów, których wykonanie powierzone zostaje komputerom.

Z czego składa się algorytm? 
Algorytm zawiera opis danych, opis wyników oraz plan działania, czyli przetworzenia danych. Plan ten można przedstawić w postaci ciągu czynności, które muszą być wykonane w określonej kolejności. Opis czynności występujących w algorytmie nazywamy instrukcjami.

Algorytm =  opis danych+- opis wyników+ plan działania, przetworzenia danych

Sposoby zapisu algorytmów:

  • opis słowny
  • lista kroków
  • pseudojęzyk, pseudokod
  • schemat blokowy
  • drzewo (drzewo algorytmu)
  • język programowania 

Opis słowny

Przykład. Algorytm znajdujący średnią arytmetyczną dwóch liczb rzeczywistych
Weź dwie liczby i dodaj je do siebie. Otrzymany wynik  przez 2.

Lista kroków

Lista kroków  to najprostszy i jednocześnie najbardziej naturalny  sposób zapisywania algorytmu. Polega na opisie reguł postępowania za pomocą kolejnych kroków, punktów. Sposób często stosowany chociażby na lekcjach matematyki, na których nauczyciel podaje schemat rozwiązania zadania danego typu.

Elementem charakterystycznym w tym sposobie zapisu jest numeracja poszczególnych kroków (wierszy).
 
Przykład. Algorytm znajdujący średnią arytmetyczną dwóch liczb rzeczywistych

Krok 1. Pobierz pierwszą liczbę.
Krok 2. Pobierz drugą liczbę.
Krok 3. Dodaj liczby do siebie.
Krok 4. Wynik sumowania podziel przez 2.
Krok 5. Wyświetl wynik.
Krok 6. Zakończ

Powyższy algorytm możemy zapisać również za pomocą listy kroków pomijając słowa krok:
1. Pobierz pierwszą liczbę.
2. Pobierz drugą liczbę.
3. Dodaj liczby do siebie.
4. Wynik sumowania podziel przez 2.
5. Wyświetl wynik.
6. Zakończ

Pseudojęzyk, pseudokod

Pseudojęzyk to sposób  pośredni między listą kroków a językiem programowania. Zwykle zapis podobny jest do któregoś z popularnych jezyków programowania, ale jest mniej formalny.

Schemat blokowy

    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.

    Kurs SQL na przykładzie Oracle: zaczynamy

    Aby nauczyć się SQL musimy go używać.

    Ja proponuję szybki start przy pomocy Virtualnej Maszyny. Instalujemy program Virtual Box i na nim gotową maszynę wirtualną przygotowaną przez Oracle:

    1. Oracle VM VirtualBox
    2. Oracle DB Developer VM (DeveloperDaysVM.ova – ponad 7GB)

    Oba narzędzia pobieramy ze strony firmy Oracle: https://www.oracle.com/technetwork/database/enterprise-edition/databaseappdev-vm-161299.html wcześniej akceptując na stronie licencję.

    Dalej postępujemy zgodnie z opisem, czyli instalujemy VirtualBox i importujemy pobrany plik:

    Plik / Importuj urządzenie wirtualne / wybieramy pobrany plik .ova

    Utworzona zostanie maszyna o nazwie Oracle DB Developer VM, którą możemy teraz uruchomić.

    Użytkownik: oracle

    Hasło: oracle

    Na pulpicie mamy skrót do narzędzia SQL Developer, uruchamiamy.

    New Connection …..

    Schemat bazy danych

    Schemat bazy danych sklepu możemy pobrać ze strony: http://www.oracle.com/webfolder/technetwork/tutorials/mooc/SQLfun/labs.zip

    W folderze setup_files znajduje się plik setup.sql, który należy uruchomić w SQL Developerze. Jak to zrobić, czyli Jak udostępnić folder maszynie wirtualnej?

    Krok 1. Udostępnienie folderu w systemie macierzystym

    Po pierwsze folder, który chcemy udostępnić maszynie wirtualnej musimy po prostu udostępnić w systemie macierzystym. Czyli mając np system Windows 8.1 klikam prawym przyciskiem myszy na folderze, który ma być widoczny na maszynie wirtualnej i wybieram np:
     Udostępnij > Określone osoby > Wszyscy

     Krok 2. Udostępnienie folderu VirtualBox’owi

    Oracle VM Virutal Box
    Maszyna>Ustawienia>Udostępnianie folderów
    Klikamy „plusik”>Ścieżka do folderu>Inny – wybieramy folder i Wybieram.
    zaznaczamy Zamontuj

     Krok 3.

    Uruchamiamy maszynę i widzimy na pulpicie folder z nazwą sf_
    Folder widoczny jest też w folderze media

     
     
    Krok 4. Wczytanie skryptu
    Oracle SQL Developer
    Wybieramy View>Files.
    A następnie w nowo otwartym widoku Files wybieramy My computer>” / „>media
    W folderze media znajdziemy wszytkie foldery usdostępnione w systemie (u mnie Windows 8) i dodane w Virtual Box. Foldery te mają nieco inną nazwę – pojawia się przedrostek sf_
    Możemy teraz kliknąć dwukrotnie na pliku i uruchomić skrypt wciskając przycisk Run Script lub klawisz F5.