1. Определение алгоритма. 2. Свойства алгоритмов. 3. Способы описания алгоритма. 4. Базовые структуры схем алгоритма. 5. Структурированные схемы и их построение. 6. Линейные и разветвляющиеся структуры. 7. Циклические структуры. Типы циклов. 8. Предопределенные процессы. Рекурсия.
Практика
Составить схемы 2-х задач (одна на одномерные массивы, вторая на двумерные) и описать решение каждой задачи на конкретном примере, т.е. поработать за компьютер.
1)Задан целочисленный одномерный массив a из n элементов. Найти максимальное значение среди отрицательных элементов, расположенных до первого элемента, меньшего заданного числа Х. 2)Задачи на двумерные массивы. Проверить, есть ли в матрице хотя бы одна строка, содержащая положительный элемент, и найти ее номер. Знаки элементов предыдущей строки изменить на противоположные.
Теория
1. Определение алгоритма. Алгоритм - система правил, сформулированная на понятном исполнителю языке, которая определяет процесс перехода от допустимых исходных данных к некоторому результату и обладает свойствами массовости, конечности, определенности, детерминированности.
2. Свойства алгоритмов a. Дискретность алгоритма - поочередное выполнение команд алгоритма за конечное число шагов приводящее к решению задачи. Запись алгоритма распадается на отдельные указания исполнителю выполнить некоторое законченное действие. Каждое такое указание называется командой. Команды алгоритма выполняются одна за другой. После каждого шага исполнения алгоритма точно известно, какая команда должна выполняться следующей. Алгоритм представляет собой последовательность команд (также инструкций, директив), определяющих действия исполнителя (субъекта или управляемого объекта). Таким образом, выполняя алгоритм, исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат. В этом случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции. Это очень важная особенность алгоритмов. создание алгоритма дает возможность решать задачу формально, механически исполняя команды алгоритма в указанной последовательности. b. Oпределенность (или точность) алгоритма - каждая команда алгоритма должна однозначно определять действие исполнителя. c. Понятность алгоритма - алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в его систему команд. У каждого исполнителя имеется свой перечень команд, которые он может исполнить. Совокупность команд, которые могут быть выполнены исполнителем, называется системой команд исполнителя. d. Результативность (конечность) алгоритма - исполнение алгоритма должно закончиться за конечное число шагов. e. Массовость алгоритма - обеспечивающие решения всего класса задач данного типа. Свойство массовости не является необходимым свойством алгоритма. Оно скорее определяет качество алгоритма.
3. Способы описания алгоритмов 1) словесный; 2) табличный; 3) графический; 4) программа на алгоритмическом языке. Для словесного представления алгоритма используется естественный язык (пример - любые инструкции, рецепты и т.п.) Примером табличных алгоритмов могут служить бухгалтерские ведомости, таблицы инженерных расчетов и т.п. Графический способ представления алгоритма - это блок-схема является наиболее наглядным. Схема алгоритма состоит из графических блоков. Программа - изложение алгоритма специально для ЭВМ в понятных ей символах, словах и командах (иначе говоря - языком программирования). Четвёртый способ – единственный «понятный» компьютеру как автоматическому исполнителю. Первые три служат для понимания решения задачи самим человеком.
4. Базовые структуры алгоритмов Базовые алгоритмические структуры. Используя исходные элементы блок-схем можно собрать более крупные кирпичики, которые называют базовыми структурами. Базовые структуры (конструкции): 1) следование; 2) ветвление (полное и не полное); 3) повторение (цикл с предусловием или постусловием); 4) вход; 5) выход. Каждая базовая структура имеет один вход и один выход.
5. Структурированные блок схемы и их построение Блок-схема называется структурированной, если она построена на основе базисного множества базовых структур. Для построения структурированных блок-схем была разработана специальная технология, которая называется пошаговой детализацией. Пошаговая детализация представляет собой процесс дробления задачи на модули, т.е. исходя из общей задачи, вычленяются подзадачи, устанавливаются логические связи между ними. После этого переходят к уточнению выделенных подзадач. Этот процесс детализации продолжается до уровня позволяющего достаточно легко реализовать подзадачу на выбранном языке программирования. При пошаговой детализации используется принцип замещения, который состоит в замене любого функционального блока (прямоугольника) блок-схемы некоторой базовой структурой (следование, ветвление, повторение) из исходного базисного множества. Достоинство пошаговой детализации состоит в том, что она позволяет разработчику алгоритма упорядочить свои рассуждения. Пример: a) Построить структурированную блок-схему алгоритма для вычисления функции b) На первом шаге задачу представим в виде одного блока, в котором запишем кратко условие задачи. c) На втором шаге функциональный блок преобразуем в развилку, где выделено вычисление Y при x<0. d) На последнем шаге функциональный блок предыдущей схемы заменяем развилкой. В итоге выполнения нескольких шагов мы получили структурированную блок-схему алгоритма решения задачи.
6. Линейные и разветвляющиеся структуры. Линейными называются алгоритмы, в которых действия осуществляются последовательно друг за другом. Стандартная блок-схема линейного алгоритма приводится ниже:
Разветвляющимся называется алгоритм, в котором действие выполняется по одной из возможных ветвей решения задачи, в зависимости от выполнения условий. В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в разветвляющиеся алгоритмы входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (действий). В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, которое может соблюдаться (быть истинно) или не соблюдаться (быть ложно). Такое утверждение может быть выражено как словами, так и формулой. Таким образом, алгоритм ветвления состоит из условия и двух последовательностей команд. В зависимости от того, в обоих ветвях решения задачи находится последовательность команд или только в одной разветвляющиеся алгоритмы делятся на полные и не полные (сокращенные). Стандартные блок-схемы разветвляющегося алгоритма приведены ниже:
7. Циклические структуры. Типы циклов. Алгоритм циклической структуры – это алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз. Многократное повторение последовательности действий называется циклом, а многократно повторяющиеся действия – телом цикла. Изучение циклов демонстрирует главное преимущество компьютера перед человеком – выполнение большого числа действий за короткое время. Ведь даже весьма короткий циклический алгоритм, составить который не так уж долго, при исполнении может потребовать выполнения нескольких сотен действий, с которыми компьютер справится намного быстрее, чем человек. Существует три формы циклов: цикл с параметром, цикл с предусловием, цикл с постусловием. Нетрудно заметить, что эти циклы взаимозаменяемы и обладают некоторыми отличиями. a) в цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием - после тела цикла; b) в цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу; c) в цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием - условие выхода из цикла.
8. Предопределенные процессы. Рекурсия. Предопределенный процесс - процесс, состоящий из одной или нескольких операций, которые определены в другом месте программы (в подпрограмме, модуле). В блок-схеме данный процесс обозначается следующим образом:
Рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Практическая часть.
1. Найти максимальное значение среди отрицательных элементов, расположенных до первого элемента, меньшего заданного числа Х.
Решение 1) Вводим размерность массива n, вводим сам массив A[n], вводим переменную X. 2) Проверяем, существует ли в массиве элемент, который меньше Х и если существует, то запоминаем индекс этого элемент в переменную i (индекс i начинается с 1). В случае не нахождения элементов меньших Х выводим «Отсутствие элементов меньше Х». 3) Находим первый по счёту отрицательный элемент, расположенный до первого элемента, меньшего заданного числа Х. Для этого составляем 2 условия: a) Если индекс первого элемента (i), меньше заданного Х равен 2 и первый элемент в массиве является отрицательным, то записываем в переменную temp первый элемент массива. b) Если индекс первого элемента (i), меньше заданного X больше двух, то ищем наибольший отрицательный элемент массива в заданном промежутке от первого элемента до элемента с индексом i (индекс i начинается с 1). В случае не нахождения отрицательных элементов в заданном промежутке выводится сообщение о не нахождении отрицательных элементов, расположенных до первого элемента, меньшего заданного числа Х. 4) Находим наибольший отрицательный элемент из промежутка от начала массива до элемента с индексом i (индекс i начинается с 1), т.е. до первого элемента, меньшего заданного числа Х. Записываем результат в temp. 5) Выводим результат temp. 2. Проверить, есть ли в матрице хотя бы одна строка, содержащая положительный элемент, и найти ее номер. Знаки элементов предыдущей строки изменить на противоположные.
Решение 1) Вводим размерность двумерного массива(матрицы) n, вводим сам массив A[n][n]. 2) Проходим построчно элементы массива с помощью двух вложенных циклов for. Первый цикл проходит по строкам сверху вниз, внутри цикл проходит элементы строки слева направо. Каждый элемент проверяется является ли он положительным: a) Если элемент является положительным, то записывается номер строки, с которой находится элемент (stroka). Задаётся флаг, чтобы больше не было входов в условие положительности элемента. b) Если элемент не является положительным, то программа продолжает проходить массив до нахождения положительного элемента. 3) В случае не нахождения положительного элемента: a) Выводится сообщение о не нахождении подходящей строки с положительным элементом. b) Иначе знаки элементов предыдущей строки изменяются на противоположные. 4) Выводим номер строки (stroka) и преобразованный массив.
