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