Вопросы теории: 1. Определение алгоритма. 2. Свойства алгоритмов. 3. Способы описания алгоритма. 4. Базовые структуры схем алгоритма. 5. Структурированные схемы и их построение. 6. Линейные и разветвляющиеся структуры. 7. Циклические структуры. Типы циклов. 8. Предопределенные процессы. Рекурсия.
Составить схемы 2-х задач (одна на одномерные массивы, вторая на двумерные) и описать решение каждой задачи на конкретном примере, т.е. поработать за компьютер. 1) Задан целочисленный одномерный массив a из n элементов. Найти минимальное значение среди элементов, меньших заданного числа В, и расположенных до первого элемента, большего заданного числа А. 2) Найти в матрице первую строку, все элементы которой отрицательны. Увеличить все элементы матрицы на значение первого элемента найденной строки. Теория
1. Определение алгоритма.
Алгоритм – одно из фундаментальных понятий в программировании и информатике. Это точное и безотказное предписание действий, которые должны быть выполнены. То есть мы можем считать алгоритмом любую инструкцию, если ее команды не допускают различных вариантов исполнения и указания предусмотрены для всех возможных вариантов событий. На практике алгоритмы составляют для решения тех или иных задач, то есть получения необходимых результатов по заданным исходным данным. Вид алгоритма, да и сама возможность его написания зависят от исполнителя (это можно быть и человек, и автоматическое устройство), или точнее, от его системы команд (то есть набора инструкций, которые он «умеет» выполнять).
2. Свойства алгоритмов.
Алгоритм обладает следующими свойствами:
1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т.е. преобразование исходных данных в результат осуществляется во времени дискретно.
2. Определенность. Каждое правило алгоритма должно быть четким, однозначным.
3. Результативность. Алгоритм должен приводить к решению за конечное число шагов.
4. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.
5. Правильность. Алгоритм правильный, если его выполнение дает правильные результаты решения поставленной задачи.
3. Способы описания алгоритма.
Существует четыре основных способа записи алгоритма:
1. Словесный, т.е. запись на естественном языке, описание словами последовательности выполнения алгоритма.
2. Формульно-словесный, т.е. запись на естественном языке, описание словами последовательности выполнения алгоритма, плюс параллельная демонстрация формул.
3. Графический, т.е. с помощью блок-схем.
4. Программный, т.е. на языке программирования.
4. Базовые структуры схем алгоритма. Используя исходные элементы блок-схем можно собрать более крупные кирпичики, которые называют базовыми структурами. Базовые структуры (конструкции): 1) Следование. Образуется последовательностью действий, следующих одно за другим; 2) Ветвление (полное и не полное). Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма; 3) Повторение (цикл с предусловием или постусловием). Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла;
4) Вход;
5) Выход. Каждая базовая структура имеет один вход и один выход.
5. Структурированные схемы и их построение. Блок-схема называется структурированной, если она построена на основе базисного множества базовых структур.
Для построения структурированных блок-схем была разработана специальная технология, которая называется пошаговой детализацией. Пошаговая детализация представляет собой процесс дробления задачи на модули, т.е. исходя из общей задачи, вычленяются подзадачи, устанавливаются логические связи между ними. После этого переходят к уточнению выделенных подзадач. Этот процесс детализации продолжается до уровня позволяющего достаточно легко реализовать подзадачу на выбранном языке программирования.
При пошаговой детализации используется принцип замещения, который состоит в замене любого функционального блока (прямоугольника) блок-схемы некоторой базовой структурой (следование, ветвление, повторение) из исходного базисного множества. Достоинство пошаговой детализации состоит в том, что она позволяет разработчику алгоритма упорядочить свои рассуждения.