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

Основы алгоритмизации Алгоритм Алгоритм — это последовательность действий, которые необходимо выполнить для решения определенной задачи или получения результата. Алгоритм обладает следующими свойствами: • Дискретность (прерывность, раздельность) – процесс решения задачи представляется как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего. •Определенность – каждое действие алгоритма должно быть четким, однозначным и не оставлять места для множества возможных смыслов. • Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов. Классификация алгоритмов по структуре • Линейны й алгорит м – набор команд (указаний), выполняемых последовательно во времени друг за другом, безальтернативно, без повторений уже реализованных ранее команд. • Развет вляющийся алгоритм – алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ выполняет переход на одну из нескольких возможных команд. • Циклический алгорит м – алгоритм, предусматривающий многократное повторение одного и того же фрагмента (одних и тех же операций) над новыми исходными данными. Цикл программы – последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия. Изображение алгоритмов с помощью блок-схем Наименование Обозначение Функция Начало-конец (пуск-остановка) Обозначает начало и конец программы или подпрограммы Действие Выполнение одной или нескольких операций Ввод/вывод Операции ввода или вывода даных Предопределенный процесс Вызов подпрограммы Изображение алгоритмов с помощью блок-схем Наименование Обозначение Условие А>0? Множественные условия Или Функция Проверка значение выражение и разветвление алгоритма Проверка значение выражение и разветвление алгоритма на более, чем три ветви. Изображение алгоритмов с помощью блок-схем Наименование Обозначение Функция Границы цикла с предусловием или постусловием Обозначает начало и конец цикла, где указываются условия цикла. Цикл со счетчиком Описывает начальное значение переменной, ее приращение и конечное значение Соединитель Нужен для соединения линий алгоритма при их разрыве или переходе на другую страницу Комментарий Применятся для описания набора блоков Язык структурного программирования Разработан в 1970 годах Эдсгером Вибе Дейкстрой. Основная идея – отказ от оператора перехода (Goto) в языках программирования высокого уровня, так как они могут создавать проблемы с чтением программы и с её выполнением (не выполняется очистка памяти в точке «ухода» и инициализация переменных в точке «прихода»). Язык включает 3 основные операции: 1. Действие 2. Условие — ЕСЛИ (условие) ТО ИНАЧЕ 3. Цикл — ПОКА (условие) перечень действий Язык структурного программирования При записи алгоритма содержимое условий и циклов должно записываться с отступом, образуя структурированный уровневый вид: действия ЕСЛИ (условие) ТО действия ПОКА (условие) действия действия ИНАЧЕ действия Принципы структурного программирования 1. Следует отказаться безусловного перехода. от использования оператора 2. Любая программа строится на основе трех базовых конструкций: действие, условие, цикл. 3. Базовые конструкции могут быть вложены друг друга в произвольной форме и неограниченном количестве. 4. Повторяющиеся фрагменты желательно оформлять в виде подпрограмм. 5. Логически законченные группы инструкций желательно объединять в блоки. 6. Все перечисленные конструкции должны иметь один вход и один выход. 7. Разработка программы ведется пошагово, используя метод «сверху-вниз». Метод «сверху-вниз» При разработке алгоритма или программы, первоначально реализуется основной управляющий алгоритм без детализации функциональных элементов, которые заменяются функциями-заглушками, возвращающими постоянное значение. По мере разработки каждая функция-заглушка реализуется своим алгоритмом, вызывающим, при необходимости, другие функции-заглушки. Разработка заканчивается когда все функции-заглушки реализованы в виде набора базовых конструкций. Метод «снизу-вверх» Предполагает обратный путь разработки: Сначала реализуются элементарные функции из которых собираются более сложные конструкции. В настоящее время активно используется, так как существует большое количество библиотек, содержащих готовые функции. Элементарные алгоритмы Элементарная программа Запускаем среду «Исполнители»: C:\robovin&logic\robowin\robot.exe Закрываем блокноты. В теле программы (между фигурными скобками) пишем: целые А,Б,В; вывод "введите А"; ввод А; вывод "введите Б"; ввод Б; В=А+Б; выводстр "А+Б=",В; Запускаем программу кнопкой F9. Поиск минимума (максимума) Обобщенный алгоритм: min=A[0] i=1 ПОКА (iA[i]) ТО min=A[i] i=i+1 Чем будет отличаться алгоритм поиска максимума? Поиск минимума (максимума) Правильны й обобщенный алгоритм: ЕСЛИ (n>0) ТО min=A[0] i=1 ПОКА (iA[i]) ТО min=A[i] i=i+1 Поиск второго максимума Алгоритм: ЕСЛИ (n>1) ТО ЕСЛИ (А[0]>А[1]) ТО max_b=A[0] max_m=A[1] ИНАЧЕ max_b=A[1] max_m=A[0] i=2 ПОКА (imax_b) ТО max_m=max_b max_b=A[i] ИНАЧЕ ЕСЛИ (A[i]>max_m) ТО max_m=A[i] i=i+1 Поиск третьего максимума Как будет выглядеть алгоритм поиска максимума? А четвертого минимума? А если в массиве элементы повторяются? третьего Более простой способ – отсортировать массив, а потом в нем искать необходимый элемент. Алгоритмы сортировки Самый простой алгоритм – «Пузырек». i=0 ПОКА (iA[j]) ТО //сортируем по возрастанию врем=А[i] А[i]=A[j] A[j]=врем j=j+1 i=i+1 Программа сортировки Часть 1: ввод массива: целые И,Ж,К; целые А[5]; И=0; пока (И<5) { вывод "Введите А[",И,"]"; ввод А[И]; И=И+1 } Программа сортировки Часть 2: сортировка массива: И=0; пока (И<5) { Ж=И+1; пока (Ж<5) { если (А[И]>А[Ж]) { К=А[И]; А[И]=А[Ж]; А[Ж]=К; } Ж=Ж+1; } И=И+1; } Программа сортировки Часть 3: вывод массива: И=0; пока (И<5) { выводстр "А[",И,"]=", А[И]; И=И+1 } Домашнее задание Разработать и реализовать алгоритм, который будет искать 3-й минимум и 4-й максимум в массиве, размер которого определяется пользователем (но не более 200) следующим образом: Ввод количества элементов Ввод элементов массива Сортировка массива Копирование отсортированного массива в другой, исключая повторяющиеся элементы Вывод искомых минимумов и максимумов, если они есть с помощью второго массива.