Temat C1. Przedstawianie algorytmu liniowego w postaci listy kroków i schematu blokowego

przez | 6 sierpnia 2019

Wszystkie treści na stronie ir.migra.pl chronione są prawami autorskimi. Więcej informacji znajdziesz tutaj.

Uwaga: Zapoznaj się wcześniej z treścią tematów C1-C3 z podręcznika „Teraz bajty. Informatyka dla szkół ponadpodstawowych. Zakres podstawowy. Klasa I”. Wykonaj zawarte w nich ćwiczenia i zadania.

Zapisy podstawy programowej realizowane w temacie:

I. Rozumienie, analizowanie i rozwiązywanie problemów.

Zakres rozszerzony. Uczeń spełnia wymagania określone dla zakresu podstawowego, a ponadto:

2) do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych;

3) objaśnia dobrany algorytm, uzasadnia poprawność rozwiązania na wybranych przykładach danych i ocenia jego efektywność;

II. Programowanie i rozwiązywanie problemów z wykorzystaniem komputera i innych urządzeń cyfrowych.

I + II. Zakres rozszerzony. Uczeń spełnia wymagania określone dla zakresu podstawowego, a ponadto:

1) zapisuje za pomocą listy kroków, schematu blokowego lub pseudokodu, i implementuje w wybranym języku programowania, algorytmy poznane na wcześniejszych etapach […];

Spis treści

  1. Sposoby przedstawiania algorytmów
  2. Lista kroków algorytmu liniowego
  3. Schemat blokowy algorytmu liniowego
  4. Analizowanie działania algorytmu

1. Sposoby przedstawiania algorytmów

Algorytmy możemy przedstawić w postaci:

  • opisu słownego,
  • listy kroków,
  • graficznej (schematu blokowego, drzewa),
  • pseudokodu,
  • programu komputerowego.

1.1. Lista kroków

Lista kroków to przedstawienie algorytmu w kolejnych punktach (krokach). Każdy punkt listy kroków zawiera opis czynności. Należy jasno i precyzyjnie określać polecenia wykonywane w poszczególnych krokach. Na przykład:

  • wprowadź wartość n;
  • oblicz wartość wyrażenia w = –b / a;
  • jeśli x < 0, wróć do kroku 2.
Zasady tworzenia listy kroków
  1. Kolejność punktów nie może być przypadkowa – musi być zgodna z działaniem algorytmu. Na przykład punkt z poleceniem obliczenia wartości wyrażenia nie może wystąpić przed wprowadzaniem wartości danych do obliczeń.
  2. Na podstawie listy kroków można napisać program komputerowy. W programowaniu bardzo istotna jest prawidłowa kolejność poleceń. Może się oczywiście zdarzyć, że w poleceniu będzie określone przejście do innego, niż kolejny, punktu listy kroków, np. w przypadku tzw. pętli.
  3. Algorytm może się kończyć w kilku miejscach listy.

1.2. Schemat blokowy

W schemacie blokowym poszczególne operacje przedstawia się graficznie, za pomocą odpowiednio połączonych figur geometrycznych (bloków). Kształt bloku wskazuje na rodzaj wykonywanej operacji, natomiast opis bloku zawiera jej parametry (dane). Połączenia określają, w jakiej kolejności będzie realizowany dany algorytm.

Zasady tworzenia schematu blokowego
  1. Operacje algorytmu należy umieszczać w odpowiednich blokach – tabela 1.
  2. Każdy schemat blokowy ma jeden blok startowy, natomiast bloków zakończenia algorytmu może być kilka.
  3. Wszystkie bloki muszą być ze sobą połączone (nie może być przerw w schemacie).
  4. Każde połączenie jest zaczepione do danego bloku i dochodzi do następnego bloku lub innego połączenia.
  5. Kolejność wykonywania operacji wyznaczają połączenia między blokami.
  6. Do każdego bloku wchodzi jedno połączenie (oprócz bloku początku algorytmu) i jedno połączenie z niego wychodzi (oprócz bloku warunku, z którego wychodzą dwa połączenia, oraz bloku zakończenia algorytmu, z którego nie wychodzi żadne połączenie).
Tabela 1. Figury geometryczne stosowane w graficznym przedstawianiu algorytmów

2. Lista kroków algorytmu liniowego

Aby zapisać algorytm liniowy w postaci listy kroków, zapisujemy sekwencyjnie (po kolei) ponumerowane punkty przedstawiające kolejne kroki algorytmu.

Przykład 1. Przedstawianie algorytmu liniowego w postaci listy kroków

Zadanie: Fabryka produkuje rocznie sw samochodów osobowych i dostawczych. Oblicz, ile zostanie wyprodukowanych samochodów osobowych, jeśli produkcja samochodów dostawczych stanowi p% rocznej produkcji. Po daj tylko całkowitą część wyniku.

Dane: liczba naturalna sw oznaczająca wielkość produkcji samochodów osobowych i dostawczych; liczba rzeczywista dodatnia p określająca procent produkcji samochodów dostawczych.

Wynik: część całkowita z liczby rzeczywistej so, określająca liczbę samochodów osobowych.

Lista kroków:

  1. Zacznij algorytm.
  2. Wprowadź wartości: sw i p
  3. Zmiennej so przypisz wartość wyrażenia: sw = (p*sw)/100 .
  4. Wyprowadź całkowitą część wyniku: so.
  5. Zakończ algorytm.

Ćwiczenie 1. Testujemy działanie algorytmu

Przetestuj działanie algorytmu zapisanego w postaci listy kroków (przykład 1.) dla danych: (50000; 30,8), (50000; 14), (20000; 14), gdzie pierwsza liczba określa wielkość produkcji sw, a druga – procent p.


Ćwiczenie 2. Zapisujemy algorytm w postaci listy kroków

  1. Napisz specyfikację zadania i listę kroków algorytmu obliczania, jaki procent liczby a stanowi liczba b.
  2. Sprawdź działanie algorytmu utworzonego w punkcie 1. dla danych z zadania: W zawodach sportowych wzięło udział 27 uczniów szkoły liczącej 578 uczniów. Jaki procent uczniów szkoły wziął udział w zawodach?
  3. Ułóż jeszcze jedno zadanie, w którym zastosujesz algorytm podany w punkcie 1. Przetestuj działanie tego algorytmu.

3. Schemat blokowy algorytmu liniowego

Aby przedstawić algorytm liniowy w postaci schematu blokowego, układamy kolejno (sekwencyjnie) bloki przedstawiające kroki algorytmu.

Do rysowania schematów blokowych można wykorzystać Kształty, dostępne w programach Microsoft Word, Microsoft PowerPoint lub Paint. Można również poszukać w Internecie darmowych programów do tworzenia schematów blokowych. Schemat blokowy możesz również narysować odręcznie w zeszycie.

Schemat blokowy algorytmu liniowego przygotowany na podstawie listy kroków z przykładu 1.
Rys. 1. Schemat blokowy algorytmu liniowego przygotowany na podstawie listy kroków z przykładu 1.

Ćwiczenie 3. Testujemy działanie algorytmu

Przetestuj działanie algorytmu przedstawionego w postaci schematu blokowego na rysunku 1. dla następujących danych (sw, p): (25000;), (30, 25), (33; 20).

Ćwiczenie 4. Przedstawiamy algorytm w postaci schematu blokowego

  1. Odpowiedz na pytania: Ile bloków START i KONIEC może być w schemacie blokowym? Jakie są zasady łączenia poszczególnych typów bloków?
  2. Narysuj schemat blokowy na podstawie listy kroków wykonanej w ćwiczeniu 2.

Wskazówka: Jeśli wykonujesz zadanie w edytorze tekstu, korzystając z Kształtów, pamiętaj o możliwości grupowania wstawionych obiektów.

4. Analizowanie działania algorytmu

Zanim przeanalizujemy działanie algorytmu, powinniśmy sprawdzić, czy poprawnie skonstruowaliśmy schemat blokowy.

Należy prześledzić, czy:

  • umieściliśmy właściwe bloki w odpowiedniej kolejności,
  • bezbłędnie wpisaliśmy operacje wewnątrz bloków,
  • prawidłowo połączyliśmy wszystkie bloki.

Po sprawdzeniu budowy schematu analizujemy działanie algorytmu zapisanego w postaci graficznej. Analiza polega na podstawieniu przykładowych danych i wykonaniu krok po kroku, według strzałek w połączeniach operacji zapisanych w kolejnych blokach schematu. W ten sposób symulujemy realizację algorytmu.

Zawsze należy wykonywać zarówno analizę poprawności budowy schematu, jak i analizę działania algorytmu, ponieważ może się okazać, że schemat jest poprawnie zbudowany, ale algorytm przedstawiony za jego pomocą jest źle realizowany.

Najczęstsze błędy:

  • zastosowaliśmy właściwe bloki, ale umieściliśmy je w niewłaściwej kolejności,
  • narysowaliśmy poprawnie schemat, ale otrzymujemy błędne wyniki, bo zastosowaliśmy niewłaściwe wzory,
  • błędnie zinterpretowaliśmy treść zadania i, chociaż narysowany przez nas schemat jest poprawny, wyniki są inne niż oczekiwane.

Przykład 2. Analizowanie działania algorytmu przedstawionego w postaci schematu blokowego

Sprawdzamy konstrukcję schematu blokowego z rysunku 5. Oceniamy, czy:

  • bloki są właściwe i umieszczono je we właściwej kolejności,
  • operacje wewnątrz bloków są poprawnie zapisane,
  • wszystkie bloki są połączone.
  • Analizujemy działanie algorytmu dla danych: w = 30000; p = 17.
    Obliczamy liczbę samochodów osobowych:
    so = 30000 – (17*30000)/100
    so = 24900
    Zostanie wyprodukowanych 24900 samochodów osobowych.

Ćwiczenie 5. Analizujemy działanie algorytmu

Korzystając z przykładu 2., przeanalizuj dla różnych danych działanie algorytmu przedstawionego w postaci schematu w ćwiczeniu 3.
Wskazówka: Działanie algorytmu najlepiej prześledzić, zapisując operacje dla konkretnych danych obok odpowiednich bloków schematu.

Ćwiczenie 6. Przedstawiamy algorytm w postaci listy kroków i schematu blokowego

  1. Zapisz specyfikację zadania i listę kroków algorytmu obliczania pola powierzchni i objętości czworościanu foremnego o krawędzi a. Jaką figurą geometryczną jest ściana w czworościanie foremnym?
  2. Na podstawie listy kroków zbuduj schemat blokowy tego algorytmu i przeanalizuj jego działanie.

Ćwiczenie 7. Określamy algorytm na podstawie schematu blokowego

  1. Otwórz plik TC1_c7_schemat.pdf. Jaki algorytm został przedstawiony na tym schemacie? Sformułuj treść zadania, zapisz specyfikację i listę kroków tego algorytmu.
  2. Przeanalizuj algorytm dla różnych danych.

Zadania

Uwaga: Każdy schemat blokowy i program przetestuj dla kilku różnych danych, nawet jeśli w zadaniu nie ma takiego polecenia.

  1. W wybranym języku programowania (C++ lub Python) napisz program realizujący algorytm przedstawiony:
    a) w postaci listy kroków w przykładzie 1. i schematu blokowego na rysunku 1.,
    b) w postaci listy kroków i schematu blokowego utworzonego w ćwiczeniu 6.,
    c) w postaci listy kroków utworzonej w ćwiczeniu 7. i schematu blokowego z pliku TC1_z5_schemat.pdf
    Wskazówka (punkt 1a): We wzorze na obliczenie liczby samochodów osobowych, należy zastosować operator dzielenia z obcięciem części ułamkowej.
  2. Napisz specyfikację i listę kroków zadania: Samochód przejechał trasę z miasta A do miasta B w ciągu 1 godziny. Przez t1 minut jechał z prędkością V1, a następnie przez t2 minut – z prędkością V2. Oblicz średnią prędkość samochodu.
  3. Utwórz schemat blokowy na podstawie listy kroków z zadania 2. Prześledź działanie algorytmu dla różnych danych.
  4. Zapisz specyfikację zadania i listę kroków algorytmu obliczania sumy odwrotności liczb całkowitych x i y różnych od zera. Na podstawie listy kroków zbuduj schemat blokowy tego algorytmu i przeanalizuj jego działanie.
  5. Otwórz plik TC1_z5_schemat.pdf. Jaki algorytm został przedstawiony za pomocą tego schematu blokowego. Sformułuj treść zadania oraz zapisz specyfikację i listę kroków tego algorytmu. Przeanalizuj algorytm dla różnych danych.
  6. W wybranym języku programowania (C++ lub Python) napisz programy realizujące algorytmy przedstawione w postaci list kroków i schematów blokowych w zadaniach 2-5.
  7. Dla zainteresowanych

  8. Zapisz specyfikację zadania i przedstaw w postaci listy kroków oraz schematu blokowego algorytm obliczania średniej ocen ze sprawdzianu z informatyki w pewnym liceum. Przyjmij, że liczba uczniów wynosi 120. Wprowadź liczby poszczególnych ocen. Dodatkowo oblicz, jaki procent uczniów otrzymał oceny niedostateczne. Przeanalizuj działanie algorytmu dla różnych danych.
    Wskazówka: Przyjmij, że wszyscy uczniowie przystąpili do sprawdzianu.
  9. Zapisz specyfikację zadania i przedstaw w postaci listy kroków i schematu blokowego rozwiązanie zadania: Właściciel działki o powierzchni P m2 na d % powierzchni tej działki postawił dom. ¼ pozostałej części działki obsiał trawą. Pozostałą część działki w trzech równych częściach przeznaczył na: ogród kwiatowy, chodniki i taras. Oblicz, jaki procent powierzchni całej działki stanowi ogród kwiatowy. Przeanalizuj działanie algorytmu dla różnych danych.
  10. W wybranym języku programowania (C++ lub Python) napisz programy realizujące algorytmy przedstawione w postaci list kroków i schematów blokowych w zadaniach 7. i 8.