3. Lekcje z algorytmami

1. Definicja, wprowadzenie
Algorytm to opisany krok po kroku sposób postępowania prowadzący do rozwiązania problemu. Może być zapisany słownie (np. przepis kulinarny), za pomocą bloków, pseudokodu, najczęściej jednak ma postać programu komputerowego zapisanego w odpowiednim języku.

Etapy tworzenia algorytmu:

1. określenie problemu i celu

2. analiza sytuacji

3. opracowanie rozwiązania

4. sprawdzenie poprawności

5. zapisać w postaci schematu lub programu.

2. Algorytym Euklidesa
Algorytm Euklidesa to jeden za najstarszych algorytmów.  Służy do wskazania NWD (największego wspólnego dzielnika) dwóch liczb naturalnych.

Algorytm można zapisać wg schematu:
1) podaj dwie różne liczby naturalne a i b inne niż 0
2) dopóki liczby te są różne:
jeżeli a > b, podstaw pod a wartość a-b
jeżeli a < b, podstaw pod b wartość b-a
3) podaj a jako wynik

Zadanie: zrealizuj ten algorytm w Scratchu:    Scratch   plik

3. Liczby parzyste, liczby pierwsze
Przy budowaniu algorytmów dotyczących liczb czasami wykorzystujemy jej cechę podzielności. W budowaniu skrytptów wykorzystujemy wtedy modulo (resztę z dzielenia). Np. przy budowaniu algorytmu sprawdzającego parzystość liczby wykorzystamy modulo dzielenia przez 2. 

3. Wieża Hanoi - algorytm powtarzalny (rekurencyjny)
Wieża Hanoi to przykład tzw. algorytmu rekurencyjnego (powtarzalnego). Grę wymyślił w 1883 roku francuski matematyk. Składa się z 3 słupków. Na jednym umieszczone są krążki o coraz mniejszej średnicy.

Gra polega na przeniesieniu krążków na 3 słupek w jak najmniejszej liczbie ruchów. Wolno przenieść tylko jeden i nie wolno kłaść większego na mniejszy. Drugi słupek jest pomocniczy.

Adres gry: http://online.freeware.info.pl/hanoi.html

Rekurencja - tworzenie pętli w procedurze przez wywołanie tej procedury wewnątrz jej definicji. 

4. Algorytm sortowania
Najpopularniejszy algorytm sortowania polega na scalaniu. Przykład sortowania od najmniejszego elementu:
a) przyjmujemy, że pierwszy element jest najmniejszy.
b) sprawdzamy kolejne elementy. Jeżeli element jest mniejszy to zastępujemy dotychczasowe minimum, jeżeli większy - zostawiamy dotychczasowe minimum.
c) czynność powtarzamy, aż do ostatniego elementu.
d) po ułożeniu pierwszego - powtarzamy cały algorytm z pozostałymi elementami.

Plik z zadaniem

Copyright © zygmunt.vxm.pl 202