Содержание: 1. Определение алгоритма. 2. Свойства алгоритма. 3. Способы описания алгоритма. 4. Базовые структуры схем алгоритмов. 5. Структурированные схемы и их построение. 6. Линейные и разветвляющиеся структуры. 7. Циклические структуры. Типы циклов. 8. Предопределенные процессы. Рекурсия. 9. Практическая часть.
1. Определение алгоритма.
Алгоритм – это система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа.
2. Свойство алгоритма.
Дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно. Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного. Понятность – алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд. Завершаемость (конечность) – при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0. Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных. Результативность – завершение алгоритма определёнными результатами. Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе. Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.
3. Способы описания алгоритма.
• на естественном языке; • на специальном (формальном) языке; • с помощью формул, рисунков, таблиц; • с помощью стандартных графических объектов (геометрических фигур) – блок-схемы.
4. Базовые структуры схем алгоритмов.
Базовые структуры алгоритмов – это определенный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей действий. К основным структурам относятся следующие: • линейные • разветвляющиеся • циклические Линейными называются алгоритмы, в которых действия осуществляются последовательно друг за другом. Разветвляющимся называется алгоритм, в котором действие выполняется по одной из возможных ветвей решения задачи, в зависимости от выполнения условий. В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в разветвляющиеся алгоритмы входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (действий). В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, которое может соблюдаться (быть истинно) или не соблюдаться (быть ложно). Такое утверждение может быть выражено как словами, так и формулой. Таким образом, алгоритм ветвления состоит из условия и двух последовательностей команд. В зависимости от того, в обоих ветвях решения задачи находится последовательность команд или только в одной разветвляющиеся алгоритмы делятся на полные и не полные (сокращенные). Циклическим называется алгоритм, в котором некоторая часть операций (тело цикла — последовательность команд) выполняется многократно. Однако слово «многократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности — получения результата за конечное число шагов. Перед операцией цикла осуществляются операции присвоения начальных значений тем объектам, которые используются в теле цикла. В цикл входят в качестве базовых следующие структуры: • блок проверки условия • блок, называемый телом цикла
Существуют три типа циклов: • Цикл с предусловием • Цикл с постусловием • Цикл с параметром (разновидность цикла с предусловием) Если тело цикла расположено после проверки условий , то может случиться, что при определенных условиях тело цикла не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называетсяциклом c предусловием. Возможен другой случай, когда тело цикла выполняется по крайней мере один раз и будет повторяться до тех пор, пока не станет ложным условие. Такая организация цикла, когда его тело расположено перед проверкой условия, носит название цикла с постусловием. Цикл с параметром является разновидностью цикла с предусловием. Особенностью данного типа цикла является то, что в нем имеется параметр, начальное значение которого задается в заголовке цикла, там же задается условие продолжения цикла и закон изменения параметра цикла. Механизм работы полностью соответствует циклу с предусловием, за исключением того, что после выполнения тела цикла происходит изменение параметра по указанному закону и только потом переход на проверку условия.
5. Структурированные схемы и их построение.
Блок-схема называется структурированной, если она построена на основе базисного множества базовых структур. Для построения структурированных блок-схем была разработана специальная технология, которая называется пошаговой детализацией. Пошаговая детализация представляет собой процесс дробления задачи на модули, т.е. исходя из общей задачи, вычленяются подзадачи, устанавливаются логические связи между ними. После этого переходят к уточнению выделенных подзадач. Этот процесс детализации продолжается до уровня позволяющего достаточно легко реализовать подзадачу на выбранном языке программирования. При пошаговой детализации используется принцип замещения, который состоит в замене любого функционального блока (прямоугольника) блок-схемы некоторой базовой структурой (следование, ветвление, повторение) из исходного базисного множества. Достоинство пошаговой детализации состоит в том, что она позволяет разработчику алгоритма упорядочить свои рассуждения. Пример. Построить структурированную блок-схему алгоритма для вычисления функции На первом шаге задачу представим в виде одного блока, в котором запишем кратко условие задачи. На втором шаге функциональный блок преобразуем в развилку, где выделено вычисление Y при x<0. На последнем шаге функциональный блок предыдущей схемы заменяем развилкой. В итоге выполнения нескольких шагов мы получили структурированную блок-схему алгоритма решения задачи.
6. Линейные и разветвляющиеся структуры.
Линейными называют алгоритмы, в которых операции выполняются последовательно одна за другой, в естественном и единственном порядке следования. В таких алгоритмах все блоки имеют последовательное соединение логической связью передачи информационных потоков. В них могут использоваться все блоки, за исключением блоков проверки условия и модификации. Линейные алгоритмы, как правило, являются составной частью любого алгоритмического процесса. Разветвляющимися называю алгоритмы, в которых в зависимости от выполнения некоторого логического условия происходит разветвление вычислений по одному из нескольких возможных направлений, называют. Подобные алгоритмы предусматривают выбор одного из альтернативных путей продолжения вычислений. Каждое возможное направление вычислений называется ветвью. Логическое условие называют простым, если разветвляющийся процесс имеет две ветви, и сложным, если процесс разветвляется на три и более ветви. Любое сложное логическое условие может быть представлено в виде простых.
7. Циклические структуры. Типы циклов.
Алгоритм циклической структуры – это алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз. Многократное повторение последовательности действий называется циклом, а многократно повторяющиеся действия – телом цикла. Изучение циклов демонстрирует главное преимущество компьютера перед человеком – выполнение большого числа действий за короткое время. Ведь даже весьма короткий циклический алгоритм, составить который не так уж долго, при исполнении может потребовать выполнения нескольких сотен действий, с которыми компьютер справится намного быстрее, чем человек. Существует три формы циклов: цикл с параметром, цикл с предусловием, цикл с постусловием. Нетрудно заметить, что эти циклы взаимозаменяемы и обладают некоторыми отличиями. 1. в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием - после тела цикла; 2. в цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу; 3. в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием - условие выхода из цикла.
8. Предопределенные процессы. Рекурсия.
Рекурсией называется такая конструкция, при которой функция вызывает саму себя. Различают прямую и косвенную рекурсии. Функция называется прямо рекурсивной, если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию, которая в свою очередь вызывает первую, то такая функция называется косвенно рекурсивной Пример прямой рекурсии:
int a() {.....a().....}
Пример косвенной рекурсии:
a(){.....b().....} b(){.....c().....} c(){.....a().....} Предопределенный процесс — это символ, который отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле).
9. Практическая часть.
Задача на одномерные массивы: Найти номер первого минимального элемента среди элементов, больших Т1 и расположенных правее первого элемента, равного Т2.
Возможные варианты ответов: 1. Не найден элемент равный Т2. Нет решения. 2. Элемент равный Т2 – последний. Нет решения. 3. Нет элементов больших Т1. Нет решения. 4. Во всех других случаях есть решение.
Пошаговое описание решение задачи: 1. Начало программы, ввод размерности массива а. 2. Начало цикла заполнения элементов массива. Обнуляем счетчик цикла i. 3. Ввод элементов массива. i++. 4. Цикл завершится при невыполнении условия счетчика i < n. 5. Вводим значение в переменную Т1, которая служит для нахождения элементов больших Т1. 6. Вводим значение в переменную Т2, которая служит для нахождения элемента равного Т2, правее первого элемента. 7. Начало цикла поиска элементов больших Т1. 7.1.Если элемент массива а больше Т1, то увеличиваем счетчик ii. 7.2. Иначе переходим к следующему шагу цикла. 8. Проверяем счетчик ii. 8.1. Если ii равно 0, то выводим сообщение «Нет элементов больших Т1» и переходим к шагу 13. 8.2. Иначе заполняем массив b с размерностью равной значению ii, элементами больших T1. 9. Проверяем массив b на элемент равный T2. 9.1. Если элемент массива равен значению Т2, то проверяем является ли он последним. Если нет элемента равного Т2, то выводим сообщение «Нет элемента равного Т2» и переходим к шагу 13. 9.2. Если элемент равный Т2 не последний, то записываем позицию элемента в переменную pos1 и переходим к шагу 10. 9.3. Иначе выводим сообщение «Элемент равный Т2 – последний» и переходим к шагу 13. 10. В переменную min присваиваем значение первого элемента массива b. 11. Начало цикла в переменную i присваиваем значение переменной pos1 и количество шагов ограничиваем до значения переменной ii, начинается поиск минимального элемента. 11.1. Если значение переменной min больше элемента массива b, то в переменную min присваивается значение этого элемента. 11.2. Иначе переходим к следующему шагу цикла. 12. После завершения цикла выводим сообщение со значением переменной min. 13. Конец программы.
Блок-схема задачи:
Задача на двумерные массивы: Дана целочисленная прямоугольная матрица. Определить количество столбцов, содержащих хотя бы один нулевой элемент.
Возможные варианты ответов: 1. Матрица не имеет нулевых элементов.
Пошаговое описание решения задачи: 1. Начало программы. 2. Ввод размерности массива N,M. 3. Инициализация цикла, переменная счетчик i обнуляется. 4. Инициализация вложенного цикла, переменная счетчик j обнуляется при каждом шаге цикла более высокого уровня. 5. Ввод элементов двумерного массива. Увеличение счетчика j. 6. Завершение вложенного цикла при невыполнении условия j < M. 7. Увеличение счетчика i. 8. Завершение цикла при невыполнении условия i < N. 9. Инициализация цикла поиска отрицательных элементов. i = 0 10. Начинается цикл поиска нулевых элементов по строкам. i<n && a[i,j]!=0 11. По окончании вложенного цикла проверяем условие i!=n, если да – то увеличиваем переменную-счетчик ++ct., если нет – то увеличиваем счетчик j. 12. По окончанию цикла проверяем переменную ct. a. Если переменная ct равна 0, то нулевых элементов не найдено. Переходим к шагу 13. b. Если переменная ct не равна 0, то были найдены нулевые элементы, вывод сообщения о количестве найденных нулевых элементов. Переходим к шагу 13. 13. Завершение работы программы.
