38. Поняття алгоритму та його основні властивості. Форми запису алгоритму. Схематичне зображення алгоритму.

Алгоритм - це спосіб з точним (тобто вираженим у точно визначеній мові) кінцевим описом застосування ефективних (тобто практично здійсненних) елементарних кроків переробки.

Алгоритми типовим чином розв’язують не тільки окремі задачі, але і класи задач.

Властивості алгоритму.

При складанні і запису алгоритму необхідно забезпечити, щоб вінволодів рядом властивостей.

Однозначність алгоритму, під якою розуміється єдиністьтлумачення виконавцем правила побудови дій та порядок їхвиконання. Щоб алгоритм володів цією властивістю, він повинен бути записанийкомандами з системи команд виконавця.

Кінцівка алгоритму - обов'язковість завершення кожної дії,складових алгоритм, і завершимо виконання алгоритму в цілому.

Результативність алгоритму, що припускає, що виконання алгоритмуповинно закінчитися отриманням певних результатів.

Масовість, тобто можливість застосування даного алгоритму для вирішенняцілого класу задач, що відповідають загальній постановці завдання. Для того щобалгоритм мав властивість масовості, слід складати алгоритм,використовуючи позначення величин і уникаючи конкретних значень.

Правильність алгоритму, під якою розуміється здатність алгоритмудавати правильні результати вирішення поставлених завдань.

Ефективність - для вирішення завдання повинні використовуватися обмеженіресурси комп'ютера (процесорний час, обсяг оперативної пам'яті і т. д.).

Розробка алгоритму.

Два різних алгоритми можуть бути правильними, але сильно відрізнятимуться за ефективністю. Розглянемо наступний алгоритм:

Кожне місто позначимо номером. Кожний тур взаємно-однозначно відповідає перестановці цілих чисел 1, 2, ..., n-1. Можна розв’язати задачу, утворюючи всі перестановки перших n-1 цілих додатних чисел. Для кожної перестановки обчислюємо вартість відповідного туру. Обробляючи таким чином всі перестановки, запам’ятовуємо такий тур, який в поточний момент має найменшу вартість. Опишемо цей алгоритм:

Алгоритм «Повний перебір».

Крок 0. Ініціалізація TOUR0, MIN∞

Крок 1. Утворення всіх перестановок (підалгоритм) for i=1 to (n-1)! do до крока 4

Крок 2. Утворення нової перестановки (підалгоритм).

Крок 3. Побудова нового тура та обчислення вартості S(T(P))

Крок 4. if S(T(P))<MIN then TOUR=T(P), MIN=S(T(P))

кінец.

39. Базові алгоритмічні конструкції.

Основні алгоритмічні конструкції:

розгалужених алгоритм.

При виконанні алгоритмів доводиться не тільки знаходити значеннявеличин, а й аналізувати їх властивості, порівнювати їх один з одним і взалежно від результату порівняння вибирати ту чи іншу гілку алгоритму.  Алгоритми, що мають кілька гілок, називаються нелінійними. До такихвідносяться розгалужуються і циклічні алгоритми. Для їх записузастосовуються складові команди.

Базова структура "розгалуження". Визначає виконання дій узалежності від виконання умови. Кожен з шляхів веде до загального виходу,так що робота алгоритму буде продовжуватися незалежно від того, який шляхбуде обраний.  | Мова QBasic | Мова блок-схем |  | Неповна | |  | IF Умова THEN дії | |  | Повне | |  | IF Умова THEN дії 1 | |  | ELSE дії 2 | |

Приклад алгоритму розгалуження на алгоритмічній мові QBasic:

INPUT «1 або 2?»  IF = 1 OR I = 2 THEN  PRINT "Ок"  ELSE  PRINT "За межами діапазону"  END IF

Основні алгоритмічні конструкції:

Циклічний алгоритм.

повторюється виконання дій (груп дій), що залежить відвиконання умови, називається циклом.

Будь-який цикл складається з трьох частин: початку, перевірки і тіла циклу.  Початок - завжди перша частина циклу. Головна його функція - підготувати цикл.  Перевірка визначає момент виходу з циклу.

Базова структура "цикл". Забезпечує багаторазове виконаннядеякої сукупності дій, яка називається тілом циклу. Основнірізновиди циклів представлені в таблиці:  | Мова QBasic | Мова блок-схем |  | Цикл типу поки що. |  | Do Until умова | |  | тіло циклу (послідовність дій) | |  | Loop | |  | Do While умова | |  | тіло циклу (послідовність дій) | |  | Loop | |  | Цикл типу для. |  | For i = i1 to i2 | |  | тіло циклу (послідовність дій) | |  | Next i | |

Приклад алгоритму цикл на алгоритмічній мові QBasic:

FOR I = 1 TO 15  PRINT I  NEXT I

FOR I = 7 TO -6 STEP -3  PRINT I  NEXT I I = 0  PRINT «Значення I на початку одно»; I  DO WHILE I