Temat C3. Przedstawianie algorytmu iteracyjnego w postaci listy kroków i schematu blokowego

przez | 24 września 2019
0 komentarzy

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ą tematu C5 z podręcznika „Teraz bajty. Informatyka dla szkół ponadpodstawowych. Zakres podstawowy. Klasa I”.

Podstawa programowa

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

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

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

2) 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. Lista kroków algorytmu iteracyjnego
  2. Schemat blokowy algorytmu iteracyjnego
  3. Lista kroków i schemat blokowy algorytmu z pętlą zagnieżdżoną

1. Lista kroków algorytmu iteracyjnego

W niektórych zadaniach niezbędne jest powtórzenie tej samej operacji (ciągu operacji). Często trzeba wykonać takie same operacje (ciągi operacji) na wielu różnych danych, co jest pracochłonne i wymaga czasu. Do rozwiązania takich zadań można wykorzystać algorytmy iteracyjne. W pewnym kroku takiego algorytmu wracamy do jednego z wcześniejszych kroków, co powoduje, że wybrane czynności zostaną wykonane wiele razy – stosujemy tzw. pętlę.

Aby zapisać algorytm iteracyjny w postaci listy kroków, wskazujemy miejsce (krok), do którego należy przejść.

Przykład 1. Zapisywanie algorytmu iteracyjnego w postaci listy kroków

Zadanie: Oblicz iloczyn n liczb całkowitych.

Dane: n dowolnych liczb całkowitych, kolejno zapamiętywanych w zmiennej a.

Wynik: wartość iloczynu: iloczyn.

Lista kroków:

  1. Zacznij algorytm.
  2. Wprowadź liczbę danych: n.
  3. Zmiennej iloczyn oraz zmiennej i przypisz wartość jeden: iloczyn = 1; i = 1.
  4. Wprowadź liczbę całkowitą i zapamiętaj ją w zmiennej a.
  5. Pomnóż iloczyn przez wprowadzoną liczbę a: iloczyn = iloczyn • a.
  6. Jeśli i nie równa się n, zwiększ licznik o jeden (i = i + 1) i wróć do kroku 3.
  7. Wyprowadź wynik: iloczyn.
  8. Zakończ algorytm.

Uwagi:

  • Każdą z kolejno wprowadzanych liczb zapamiętujemy w zmiennej a (w ten sposób nie musimy korzystać z różnych zmiennych dla kolejnych liczb).
  • Wartość iloczynu dla kolejno wprowadzanych danych zapamiętywana jest w zmiennej iloczyn, której na początku algorytmu przypisujemy wartość jeden. Przypisanie iloczyn = iloczyn • a oznacza przypisanie wartości zmiennej iloczyn poprzedniej wartości tej zmiennej, pomnożonej przez wartość kolejnej liczby a.
  • Zmienna i jest tzw. zmienną sterującą pętli – steruje liczbą wykonanych kroków iteracji.
  • Przypisanie i = i + 1 oznacza przypisanie wartości zmiennej i poprzedniej wartości tej zmiennej, powiększonej o 1 (czyli w efekcie zwiększenie i o 1). Taką operację nazywamy inkrementacją.

Ćwiczenie 1. Testujemy działanie algorytmu

Przetestuj działanie algorytmu zapisanego w postaci listy kroków w przykładzie 1. dla n = 5 i dla kolejnych wartości zmiennej a: 14, 5, 18, 3, 20. Analizę przeprowadź tak jak w przykładzie 3. z tematu C5 w podręczniku „Teraz bajty. Informatyka dla szkół ponadpodstawowych. Zakres podstawowy. Klasa I”. Ile jest cykli iteracji dla n = 5?

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

Napisz specyfikację zadania i listę kroków algorytmu zliczania liczb podzielnych przez 3 wśród n liczb wprowadzanych z klawiatury. Algorytm kończy się, gdy sprawdzimy wszystkie n liczb. Na koniec wyprowadź, ile było liczb podzielnych przez 3.

Wskazówka: Zmiennej, w której będziemy zapamiętywać, ile było liczb podzielnych przez 3, na początku przypisz wartość zero.

2. Schemat blokowy algorytmu iteracyjnego

Aby przedstawić iteracje w schemacie blokowym za pomocą pętli, „wracamy” z połączeniem w odpowiednie miejsce algorytmu (rys. 1.)

Rys. 1. Schemat blokowy algorytmu iteracyjnego – 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 wybranych danych n i a.

Ćwiczenie 4. Przedstawiamy algorytm w postaci schematu blokowego

Utwórz schemat blokowy algorytmu zapisanego w postaci listy kroków w ćwiczeniu 2.

3. Lista kroków i schemat blokowy algorytmu z pętlą zagnieżdżoną

Instrukcje iteracyjne for mogą być zagnieżdżone, czyli instrukcją powtarzaną w pętli może być kolejna instrukcja pętli

Przykład 2. Zapisywanie algorytmu zawierającego pętle zagnieżdżone w postaci listy kroków

Zadanie: Napisz listę kroków algorytmu, który umożliwi wyprowadzenie na ekran monitora prostokąta o bokach n, m, narysowanego za pomocą znaków * (n – liczba znaków * w pionie, m – liczba znaków * w poziomie,). Wnętrze prostokąta powinno być wypełnione znakami *.

Dane: liczby naturalne dodatnie, określające ilość znaków * w prostokącie o bokach n, m.

Wynik: prostokąt o wymiarach m x n, zbudowany ze znaków *.

Lista kroków:

  1. Zacznij algorytm.
  2. Wprowadź liczby danych: n i m.
  3. Zmiennej i przypisz wartość jeden: i = 1.
  4. Jeśli i jest większe od n, przejdź do kroku 4;

      w przeciwnym wypadku:

    1. zmiennej jprzypisz wartość jeden: j = 1;
    2. jeśli jjest większe od m:
      1. przejdź do nowego wiersza;
      2. zwiększ licznik i o jeden (i = i + 1);
      3. wróć do kroku 3;

        4. w przeciwnym wypadku:

      4. wyprowadź (‘*’);
      5. zwiększ licznik j o jeden (j = j + 1);
      6. wróć do kroku 3.2;
  5. Zakończ algorytm.

Uwaga: Liczba kroków tej iteracji jest określona przez iloczyn: n • m.

Rys. 2. Schemat blokowy algorytmu z pętlą zagnieżdżoną – przykład 2

Ćwiczenie 5. Piszemy listę kroków algorytmu zawierającego pętle zagnieżdżone

Napisz specyfikację zadania i listę kroków oraz utwórz schemat blokowy algorytmu rysowania choinki opisanego w zadaniu 10., w tematu C5 z podręcznika „Teraz bajty. Informatyka dla szkół ponadpodstawowych. Zakres podstawowy. Klasa I”.

Ćwiczenie 6. Tworzymy schemat blokowy algorytmu zawierającego pętle zagnieżdżone

Utwórz schemat blokowy algorytmu rysowania choinki na podstawie listy kroków z ćwiczenia 5.

Zadania

  1. Napisz specyfikację zadania i listę kroków algorytmu zliczania oddzielnie liczb podzielnych przez 5 i podzielnych przez 7 wśród n liczb wprowadzanych z klawiatury. Algorytm kończy się, gdy sprawdzimy wszystkie n liczb. Na koniec wyprowadź komunikat, których liczb było więcej. Jeśli będzie po tyle samo, wyprowadź odpowiedni komunikat.
  2. Napisz listę kroków algorytmu opisanego w zadaniu 8. w tematu C5 z podręcznika „Teraz bajty. Informatyka dla szkół ponadpodstawowych. Zakres podstawowy. Klasa I”.
  3. Utwórz schemat blokowy algorytmu zapisanego w postaci listy kroków w zadaniu 1.
  4. Utwórz schemat blokowy algorytmu zapisanego w postaci listy kroków w zadaniu 2.
  5. W wybranym języku programowania napisz program na podstawie listy kroków i schematu blokowego wykonanych w zadaniach 1. i 2.
  6. Otwórz plik TC3_z5_suma_n_liczb.cpp lub TC3_z5_suma_n_liczb.py. Program powinien obliczać sumę kolejnych n liczb naturalnych, począwszy od 1 do n. Uruchom program. Czy program wyświetla poprawne wyniki? Jakie błędy występują w programie? Popraw program i uruchom.
  7. Napisz listę kroków algorytmu opisanego w zadaniu 9. w tematu C5 z podręcznika „Teraz bajty. Informatyka dla szkół ponadpodstawowych. Zakres podstawowy. Klasa I”.
  8. Napisz specyfikację zadania i listę kroków algorytmu tworzącego na ekranie tabliczkę mnożenia dla liczb od 1 do 10. W wybranym języku programowania utwórz program realizujący ten algorytm.

    9. Dla zainteresowanych

  9. Napisz specyfikację zadania i listę kroków algorytmu obliczającego sumę n składników 1 + 1 + 111 + 1111 + 1… 1 (zadanie 18., temat C5 z podręcznika „Teraz bajty. Informatyka dla szkół ponadpodstawowych. Zakres podstawowy. Klasa I”.).
  10. Utwórz schemat blokowy na podstawie listy kroków zapisanej w zadaniu 9.
  11. Napisz specyfikację zadania i listę kroków oraz utwórz schemat blokowy algorytmu wyświetlenia na ekranie monitora „szachownicy” opisanego w zadaniu 10., w tematu C5 z podręcznika „Teraz bajty. Informatyka dla szkół ponadpodstawowych. Zakres podstawowy. Klasa I”.
  12. Opisz wymyślony samodzielnie problem iteracyjny. Ułóż zadanie, zapisz specyfikację, listę kroków i utwórz schemat blokowy. Na koniec napisz program realizujący to zadanie.