Основы алгоритмизации

Основы алгоритмизации Понятие алгоритма • Алгоритмом называется строго определенная последовательность действий, определяющих процесс перехода от исходных данных к искомому результату. Пример • На левом берегу реки находятся два молодых человека со своими девушками. Всем нужно перебраться на правый берег, но в лодке только два места. Каждая девушка не хочет оставаться на берегу без своего молодого человека, если на этом же берегу находится другой молодой человек. Как всем переплыть на другой берег? Решение • Обозначим девушек и молодых людей Д1, Д2, М1, М2, переезд на правый берег →, переезд на левый берег ← . Можно записать алгоритм: 1) 2) 3) 4) 5) Д1, Д2 → Д1 ← М1, М2 → М1 ← ; Д1, М1 → Свойства алгоритма • дискретност ь (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное исполнение простых (или ранее определенных) шагов (этапов); • определенност ь – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола; • результативност ь (или конечность) – алгоритм должен приводить к решению задачи за конечное число шагов; • массовость – алгоритм решения задачи производится в общем виде, т. е. его можно будет применять для некоторого класса задач, различающихся лишь исходными данными. Способы записи алгоритмов • словесны й – записывается на естественном языке; • граф ический – с помощью блок-схемы; • операторны й – полуформализованные описания алгоритмов на некотором условном алгоритмическом языке, которые включают в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др. Словесный способ записи алгоритма • Требуется решить квадратное уравнение ax2 +bx+c=0 в области действительных чисел. Математической моделью этой задачи является известная формула корней квадратного уравнения: • Алгоритм вычисления: 1. Задать значения а, b, c. 2. Вычислить дискриминант d = b2 – 4ac. 3. Сравнить дискриминант с нулем, если он больше нуля, то вычислить корни по формуле и перейти к п. 4, иначе сообщить: «В области действительных чисел уравнение решений не имеет». 4. Записать результат: «Корни уравнения у1 и у2». Графический способ описания алгоритма • Графический способ описания алгоритма иначе называют блок - схемой. • Блок-схемой называется наглядное графическое изображение алгоритма, когда отдельные его этапы изображаются при помощи различных геометрических фигур – блоков, а связи между этапами (последовательность выполнения этапов) указываются при помощи стрелок, соединяющих эти фигуры. Блоки сопровождаются надписями. Начало Ввод a, b, c d: = b2 –4ac d<0 Вывод «Корней нет» x1 := (-b + sqrt(d))/2*a x2 := (-b - sqrt(d))/2*a Вывод x1, x2 Конец Фигуры блок-схемы Обозначение блока Выполняемая функция Блок начала-конца алгоритма. Надпись в блоке: «начало» («конец»). Блок ввода-вывода данных. Надпись в блоке: слово «ввод» («вывод» или «печать») и список вводимых (выводимых) переменных. Блок решения или действия. Надпись в блоке: конкретная операция или группа операций. Условный блок. Надпись в блоке: проверяемое условие. В результате проверки условия осуществляется выбор одного из возможных путей (ветвей) вычислительного процесса. Если условие выполняется, то следующим выполняется этап по ветви «да», если условие не выполняется, то выполняется этап по ветви «нет». Блок организация циклических процессов. Стрелка. Переход на следующее действие Типы алгоритмов • Линейный алгоритм • Разветвленный алгоритм • Циклический алгоритм Линейный алгоритм • Линейный алгоритм –алгоритм, в котором все операции выполняются последовательно одна за другой. • Пример: Пусть a, b, c – длины сторон треугольника. Необходимо найти S – площадь треугольника, P – периметр. Для нахождения площади можно воспользоваться формулой Герона: где r – полупериметр. Входные данные: a, b, c. Выходные данные: S, P. Разветвленный алгоритм • Алгоритмы разветвленной структуры применяются, когда в зависимости от некоторого условия необходимо выполнить либо одно, либо другое действие. • Пример: Даны три числа а, b, с. Найти наибольшее из них. Циклический алгоритм • Циклом называют повторение одних и тех же действий (шагов). Последовательность действий, которые повторяются в цикле, называют телом цикла. • Существует цикл с предусловием (цикл for) и цикл с постусловием. Эти циклы взаимозаменяемы и обладают некоторыми отличиями: 1) в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием – после тела цикла; 2) в цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу; 3) в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием – условие выхода из цикла. Пример: алгоритм семь раз отмерь, один раз отрежь. Начало Начало I=0 I=0 Начало N= 7 I=0, N, 1 Вывод «Отмерь» I<7 нет Вывод «Отмерь» да Вывод «Отмерь» I=I+1 I=I+1 да I<6 нет Вывод «Отрежь» Вывод «Отрежь» Вывод «Отрежь» Конец Конец Конец Цикл for Цикл с предусловием Цикл с постусловие м Задание 1) Установить Visio. 2) Построить: • блок-схему, которая рассчитывает площадь и периметр прямоугольника, если известны ширина и высота; • блок-схему, которая рассчитывает функцию F(x, y), которая равна x – y при x < y, а иначе y – x +1 (x и y известны); • блок-схему, которая рассчитывает Задания 2 1) Даны a, b, c. Найти x, которое равно MIN * 5 – MAX / 5 +6. (MIN и MAX это минимальное и максимальное значение среди a, b, c, d)/ 2) Найти функцию y(x) 3) Найти y , только когда i =2 или i=5, уменьшить y на 1