1. Теоретическая часть…………………………………………………………...3 1.1. Определение алгоритма…………………………………………………3 1.2. Свойства алгоритмов……………………………………………………3 1.3. Способы описания алгоритмов…………………………………………4 1.4. Базовые структуры схем алгоритмов…………………………………..4 1.5. Структурированные схемы и их построение…………………………..4 1.6. Линейные и разветвляющиеся структуры……………………………..5 1.7. Циклические структуры. Типы циклов………………………………...5 1.8. Предопределенные процессы. Рекурсия……………………………….6 2. Практическая часть……………………………………………………………7 2.1. Задача на одномерные массивы………………………………………...7 2.2. Задача на двумерные массивы Теоретическая часть
1. Определение алгоритма Алгоритм – последовательность точных предписаний, понятных исполнителю совершить последовательность действий на достижение конкретного результата.
2. Свойства алгоритмов 1) Последовательность – все действия располагаются друг за другом, и переход к следующему действию возможен только после завершения предыдущего действия; 2) Определенность – каждое действие алгоритма должно быть четко определено и однозначно выполнено, не оставляя места произволу; 3) Дискретность – исполнение алгоритма должно распадаться на выполнение отдельных шагов. Выполнение следующего шага происходит только после выполнения предыдущего шага; 4) Конечность – выполнение алгоритма завершается после конечного числа шагов; 5) Результативность – завершение алгоритма за конечное число шагов и получение искомого результата. Сообщение о том, что алгоритм не имеет решения, тоже является результатом. 6) Массовость – каждый алгоритм предполагает наличие некоторых исходных данных и приводит к получению определенного искомого результата. Массовость алгоритма состоит в том, что алгоритм служит не для решения одной определенной задачи, а для решения целого класса определенных задач путем варьирования исходных данных.
3. Способы описания алгоритмов a) Словесный способ – обычно используется для записи алгоритмов, где исполнителем является человек. Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противного. b) Блок-схема – графическая форма записи алгоритма. c) Программа – алгоритм, записанный на понятном компьютеру языке программирования. d) Примером табличных алгоритмов могут служить бухгалтерские ведомости, таблицы инженерных расчетов и т.п.
4. Базовые структуры схем алгоритма Алгоритмы можно представлять, как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл. Характерной особенностью базовых структур является наличие в них одного входа и одного выхода. 1) Базовая структура «следование». Образуется последовательностью действий, следующих одно за другим. 2) Базовая структура "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура «ветвление» существует в четырех основных вариантах: «если - то»; «если – то - иначе»; «выбор»; «выбор - иначе». 3) Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
5. Структурированные схемы и их построение Блок-схема называется структурированной, если она построена на основе базисного множества базовых структур. Для построения структурированных блок-схем была разработана специальная технология, которая называется пошаговой детализацией. Пошаговая детализация представляет собой процесс дробления задачи на модули, т.е. исходя из общей задачи, вычленяются подзадачи, устанавливаются логические связи между ними. После этого переходят к уточнению выделенных подзадач. Этот процесс детализации продолжается до уровня позволяющего достаточно легко реализовать подзадачу на выбранном языке программирования. При пошаговой детализации используется принцип замещения, который состоит в замене любого функционального блока (прямоугольника) блок-схемы некоторой базовой структурой (следование, ветвление, повторение) из исходного базисного множества. Достоинство пошаговой детализации состоит в том, что она позволяет разработчику алгоритма упорядочить свои рассуждения.
6. Линейные и разветвляющиеся структуры Линейные алгоритмы состоят из нескольких команд (операторов), которые должны быть выполнены последовательно одна за другой. Ветвление(развилка) – такая форма организации действий, при которой в зависимости от выполнения или невыполнения конкретного условия совершается либо одна либо другая последовательность действий.
7. Циклические структуры. Типы циклов Циклом называют повторение одних и тех же действий (шагов). Последовательность действий, которые повторяются в цикле, называют телом цикла. Существует несколько типов алгоритмов циклической структуры. На рисунках изображены циклы с предусловием и с постусловием соответственно, которые называют условными циклическими алгоритмами. В цикле с предусловием условие проверяется до тела цикла, в цикле с постусловием – после тела цикла. В цикле с постусловием тело цикла выполняется хотя бы один раз, в цикле с предусловием тело цикла может не выполниться ни разу. В цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием – условие выхода из цикла. Существует безусловный циклический алгоритм, который удобно использовать, если известно, сколько раз необходимо выполнить тело цикла.
8. Предопределенные процессы. Рекурсия Предопределенными процессами называются процессы, определенные в системе заранее (до начала их прямого использования). Функция называется рекурсивной, если во время ее обработки возникает повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций. Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции. Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже считаются рекурсивными. Обращение к рекурсивной подпрограмме ничем не отличается от вызова любой другой подпрограммы. При этом при каждом новом рекурсивном обращении в памяти создаётся новая копия подпрограммы со всеми локальными переменными. Такие копии будут порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения стека.
Практическая часть
1. Задан целочисленный одномерный массив a из n элементов. Найти номер первого максимального значения среди отрицательных элементов, расположенных правее первого элемента, равного Т. Решение: 1) Вводим размерность массива n, вводим сам массив a[n], вводим переменную T. 2) С помощью цикла проверяем, существует ли в массиве элемент равный T. Если цикл закончился, при этом последний элемент не равен T – вывод сообщения «Нет элементов равных T». В противном случае, проверка условия: вышли из цикла и последний элемент массива равен T. В этом случае вывод сообщения «T – последний элемент». 3) Если второе условие также ложно, значит, мы вышли из цикла раньше, чем он закончился. 4) Объявляем новую переменную max = 0. 5) Увеличиваем счетчик предыдущего цикла на единицу и начинаем новый цикл с этого значения, пока не закончится массив. 6) Находим первый отрицательный элемент, если max = 0, тогда принимаем текущий элемент как максимальный и запоминаем порядковый номер этого элемента в массиве. 7) Если же ранее (на предыдущих итерациях цикла) мы приняли какой-то максимальный отрицательный элемент, то есть max не равно 0, проверяется следующее условие: текущий элемент больше максимального? Если больше, максимальным становится данный элемент и порядковый номер перезаписывается. 8) Когда цикл завершится, проверяется max = 0, если равен, значит в массиве отрицательных элементов нет. Если не равен – вывод порядковый номер максимального отрицательного элемента массива.
2. Проверить, все ли столбцы матрицы упорядочены по убыванию. Если нет, то упорядочить первый неупорядоченный столбец.
Решение:
1) Вводим размерность двумерного массива (матрицы) n на m, вводим сам массив A[n][m]. 2) Вводим переменную count = -1 для последующей проверки, все ли столбцы матрицы упорядочены по убыванию. 3) Проходим по столбцам по элементам массива с помощью двух вложенных циклов for, при этом проверяется, является ли элемент, стоящий выше в столбце меньшим, стоящего ниже. Если является, запоминаем номер данного столбца и принудительно выходим из цикла. 4) После выхода из циклов (принудительно или нет), проверяется переменная count. Если она не изменилась, значит все столбцы матрицы упорядочены по убыванию. Программа завершается. 5) Если не упорядочены, то count равна номеру первого неупорядоченного столбца. 6) Вводим два цикла for, один в убывающем порядке и проверяем данный столбец. Если элемент, расположенный выше меньше нижнего – меняем эти элементы местами. Таким образом, с помощью этих двух циклов сортируем столбец по убыванию методом пузырька. 7) В конце выводим полученную матрицу и программа завершается.
