przykłady algorytmów

Algorytmy sortowania

ALGORYTMY SORTOWANIA (PORZĄDKOWANIA)

Sortowanie (porządkowanie) – proces ustawienia zbioru obiektów w określonym porządku

Metody sortowania:
przez zamianę (sortowanie bąbelkowe)
przez wybieranie
przez wstawianie
ALGORYTM SORTOWANIA BĄBELKOWEGO
Jedną z popularnych metod sortowania jest sortowanie przez prostą zamianę (sortowanie bąbelkowe). W metodzie tej porównujemy sąsiednie elementy. W celu uporządkowania elementów od najmniejszego do największego, jeśli drugi element jest mniejszy od poprzedniego, to zamieniamy go miejscami. Następnie element, który stał się drugim, porównujemy z trzecim i przestawiamy, jeśli jest mniejszy itd.

Sortowanie bąbelkowe polega na porównywaniu parami kolejnych liczb i przestawianiu, jeśli są ustawione w niewłaściwej kolejności.

Zadanie. Sortowanie bąbelkowe

Uporządkuj liczby: 7 6 1 9 5 w kolejności od najmniejszej do największej.

Przebieg pierwszy:
7 6 1 9 5    – porównujemy 7 i 6 ( przestawiamy, bo 6 < 7)
6 7 1 9 5    – porównujemy 7 i 1 ( przestawiamy, bo 1 < 7)
6 1 7 9 5    – porównujemy 7 i 9 ( nie przestawiamy, bo 10 > 7)
6 1 7 9 5    – porównujemy 9 i 5 ( przestawiamy, bo 5 < 10)
6 1 7 5 9         – 9 na właściwym miejscu

Przebieg drugi:
6 1 7 5 9    – porównujemy 6 i 1 ( przestawiamy, bo 1 < 6)
1 6 7 5 9    – porównujemy 6 i 7 ( nie przestawiamy, bo 7 > 6)
1 6 7 5 9   – porównujemy 7 i 5 ( przestawiamy, bo 5 < 7)
1 6 7 5 9    – porównujemy 7 i 5 ( przestawiamy, bo 5 < 7)
1 6 5 7 9         – 7 i 9 na właściwym miejscu

Przebieg trzeci:
1 6 5 7 9    – porównujemy 1 i 6 ( nie przestawiamy, bo 6 > 1)
1 6 5 7 9    – porównujemy 6 i 5 ( przestawiamy, bo 5 < 6)
1 5 6 7 9         – 6, 7, 9 na właściwym miejscu

Przebieg czwarty:
1 5 6 7 9 – porównujemy 1 i 5 nie przestawiamy, bo 5 > 1
…

Spójrz wyżej. Czy ciąg po pierwszym przebiegu jest już uporządkowany? Ponieważ nie jest, należy wykonywać kolejne przebiegi. Powinniśmy to robić, aż liczby zostaną uporządkowane, a więc do momentu, aż nie trzeba będzie przestawiać miejscami żadnego elementu.

w czwartym przebiegu nie są zamieniane żadne elementy, czyli nie ma potrzeby dalszego porównywania. Można zakończyć algorytm, liczby są uporządkowane w żądanej kolejności

Zadanie do samodzielnego wykonania
Ułóż 5 książek w przypadkowej kolejności na stole. Uporządkuj je według wysokości (od najwyższej do najniższej), stosując algorytm sortowania bąbelkowego.

ALGORYTM SORTOWANIA PRZEZ WYBIERANIE
Jeśli chcemy uporządkować elementy jakiegoś zbioru np. w kolejności od najmniejszego do największego to możemy wybrać najmniejszy element i umieścić go na początku. Następnie wybieramy najmniejszy element z pozostałego zbioru i umieszczamy go po poprzednio wybranym elemencie (czyli jako drugi) itd.Taka metoda porządkowania nazywa się sortowaniem przez wybór. Polega na wyszukaniu największej liczby, przestawieniu jej na początek ciągu elementów (czyli zamienieniu jej z pierwszą liczbą ciągu) i takim samym postępowaniu dalszym z pominięciem pierwszego elementu.

Zadanie. Sortowanie bąbelkowe

Uporządkuj liczby: 7 6 1 9 5 w kolejności od najmniejszej do największej.

7 6 1 9 5    – 1 na pierwszą pozycję, 7 w miejsce 1
1 6 7 9 5    – 5 na drugą pozycję, 6 w miejsce 5
1 5 7 9 6    – 6 na trzecią pozycję, 7 w miejsce 6
1 5 6 9 7    – 7 na czwartą pozycję, 9 w miejsce 7
1 5 6 7 9    – 9 na właściwym miejscu (piątym)

Zadanie do samodzielnego wykonania
Wykonaj zadanie z ćwiczenia drugiego, stosując algorytm sortowania przez wstawianie.

ALGORYTM SORTOWANIA PRZEZ WSTAWIANIE
Metoda porządkowania przez wybór polega na wstawianiu elementu we właściwe miejsce, jest ona powszechnie stosowana przez osoby grające w karty.

7| 6 1 9 5
6 7| 1 9 5
1 6 7| 9 5
1 6 7 9| 5
1 6 7 5 9|

Na schemacie kreska odziela posortowaną lewą część liczb od nieposortowanej prawej części.

Jeśli pragniemy ustawić liczby w kolejności od najmniejszego do największego, to bierzemy element drugi i jeśli jest on mniejszy od pierwszego to wstawiamy przed nim. Następnie bierzemy element trzeci i wstawiamy również w odpowiednie miejsce, a więc jeśli jest mniejszy od pierwszego to przed pierwszy, jeśli mniejszy od drugiego to przed drugi.

ALGORYTM SORTOWANIA TABLICY
Przykład
Schemat blokowy algorytmu sortowania bąbelkowego elementów tablicy jednowymiarowej

schemat blokowy

Algorytm. Gra Papier Kamień Nożyce

Grę „Papier Kamień Nożyce” znają chyba wszyscy. Tym razem naszym zadaniem jest stworzenie algorytmu wskazującego zwycięzcę tej gry.

Zakładamy, że w grze uczestniczą dwaj gracze. Każdy z graczy może wybrać (pokazać) jedną z trzech wartości: papier albo kamień albo nożyce. Możemy więc przystąpić do tworzenia specyfikacji algorytmu:

Dane wejściowe:
g1: pierwszy gracz – ciąg znaków zawierający jedną z wartości: {papier, kamień, nożyce}
g2: drugi gracz – ciąg znaków zawierający jedną z wartości: {papier, kamień, nożyce}

Naszym zadaniem jest wskazanie zwycięzcy. Jak może zakończyć się starcie? Mamy trzy możliwości:albo wygrał gracz pierwszy albo gracz drugi albo też gracze pokazali tą samą rzecz i gra zakończyła się remisem. Zatem możemy zdefiniować:

Dane wyjściowe (wynik):
wynik: wynik gry – napis (ciąg znaków) zawierający jedną z wartości {„Wygrał gracz 1”, „Wygrał gracz 2″,”Remis”}

Metoda wskazania zwycięzcy

Ciąg dalszy już niedługo …

Algorytm przedstawiony w języku programowania

Przykładowy fragment kodu programu w języku C#:

if (p1 == p2)
      return „Remis!”;

    if (((p1 == „kamień”) && (p2 == „nożyce”)) ||
        ((p1 == „nożyce”) && (p2 == „papier”)) ||
        ((p1 == „papier”) && (p2 == „kamień”)))
    {
      return „Wygrał gracz 1!”;
    }
    else
    {
      return „Wygrał gracz 2!”;
    }

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ą.

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:

Podaj pierwszą liczbę
Podaj drugą liczbę
Podaj trzecią liczbę
Dodaj do siebie liczby i wynik zapamiętaj
Wypisz otrzymany wynik

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.

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.

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: NWD

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

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.