refik.in.ua 1


Основи алгоритмізації та програмування

  • 

  • Базові структури алгоритму


 Базові структури алгоритмів

  • Базові структури алгоритмів –– це способи керування процесами обробки даних. Комбінуючи керуючі структури, можна складати алгоритми (програми) для різноманітних задач.

  • Виділяють три базові алгоритмічні структури:

  • 1. Лінійні алгоритми (слідування).

  • 2. Розгалуження (вибір).

  • 3. Повторення (цикл).

    • Слідування –– це лінійна структура, яка являє послідовність команд, виконуваних поспіль.
  • Розгалуження –– це вид керуючої структури, що передбачає можливість вибору команд залежно від умови.

  • Цикл –– це процес, який виконується кілька разів в залежності від виконання умови



Лінійна структура

  • Лінійна структура має вигляд:

  • Алг Коло_Круг

  • арг R: ціл

  • рез L, S: дійсн

  • Поч

  • Ввести R

  • L : = 2  R

  • S : =  R2

  • Вивід L

  • Вивід S

  • Кін


 Розгалуження

    • Умовний оператор (опеpатоp умовного пеpеходу) служить для запису алгоритмiчної структури розгалуження, тобто дозволяє вибрати для виконання один з двох операторiв в залежностi вiд того виконується деяка умова чи нi.
  • Iснує дві форми умовного оператора:

  • - повна;

  • - коротка


 Розгалуження в повній формі

      • Якщо <логічний вираз> то серія1
      • інакше серія2;
  • все



 Розгалуження в неповній формі

  • Якщо <логічний вираз>

  • то серія;

  • все



Розгалуження. Приклад

  • Приклад.

      • Алг Task_Max
      • Арг a, b: ціл;
      • Рез max: ціл;
      • Поч
      • Ввести a;
      • Ввести b;
      • якщо a>b то max:=a інакше max:=b;
      • Вивід max;
      • Кін
  • Завдання. Які дії виконає дана програма? Складіть блок-схему до прикладу.



 Повторення

      • Якщо обчислювальний процес мiстить багаторазове обчислення за одними i тими ж математичними залежностями, але для рiзних значень змiнних, що входять до них, то його називають циклiчним.
  • а) пiдготовку циклу - задання початкових значень змiнним циклу перед першим його проходом;

  • б) тiло циклу - дiї, якi повторюються в циклi для рiзних значень змiнних циклу;

  • в) модифiкацiю (змiну) значень змiнних циклу перед кожним новим його повторенням;

  • г) керування циклом - перевiрку умови продовження (або закiнчення) циклу i перехiд на початок тiла циклу, якщо виконується умова продовження циклу (або вихiд з циклу при його закiнченнi).


 Типи циклічних алгоритмів

      • Розрiзняють цикли iз заданим числом повторень (цикли з параметром) i цикли з напеpед невiдомим числом повторень (цикли з передумовою та з пiсляумовою):
      • 1. Цикл-для
      • 2. Цикл-до
      • 3. Цикл-поки


Цикл-для

  • Вказівка повторення з параметром записується таким чином:

      • для i:=x1 до xn крок Н
      • пц
      • тіло циклу;
      • кц
  • і - параметр циклу

  • х1 - початкове значення параметру

  • xn - кінцеве значення параметру

  • H - крок зміни параметру (може набувати значення +1 або -1)

  • Цикл-для виконується т.ч.: параметру і присвоюється початкове значення х1. Він порівнюється з кінцевим значенням xn. Якщо х1<=xn, то виконується цикл. Значення і автоматично змінюється на крок Н і знову порівнюється зі xn і т.д. Якщо отримуємо, що x1>xn, то цикл не виконується.



Цикл-поки

      • Поки <умова>
      • пц
      • тіло циклу;
      • кц
  • Якщо умова істинна то виконується тіло циклу. Виконання програми повертається до перевірки умови циклу.

  • Якщо умова хибна, то виконується вказівка, яка знаходиться після вказівки з передумовою



 Цикл-до

  • Повторювати

  • пц

  • тіло циклу;

  • кц

  • до <умова>;

  • Спочатку виконується тіло циклу, а пізніше перевіряється умова. Якщо умова істинна, то виконання циклу завершується, якщо ні, то цикл виконується ще раз і т. д.


 Повторення. Приклад

  • Приклад

  • Обчислити суму n- перших натуральних чисел.

  • Складемо блок-схему і алгоритм


 Повторення. Приклад

  • Алг Сума;

      • арг: n, i: ціл;
      • рез S: дійсн;
      • Поч
      • Ввести n;
      • i:=1;
      • S:=0;
          • поки i<=n
          • пц
          • S:=S+i;
          • i:=i+1;
          • кц
      • Вивід S;
  • Кін



 Повторення. Приклад. Завдання

  • 1. Який вид циклу виконується в даній задачі? Чому?

  • 2. Визначіть початкові умови циклу

  • 3. Визначіть тіло циклу.

  • 4. Визначіть керуючу змінну циклу.

  • 5. Визначіть крок з яким змінюється лічильник циклу.

  • 6. Яким буде результат S, якщо n набуде значення 2; 3; 5; 10; 100?