Министерство образования Республики Беларусь Учреждение образования
«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»
Институт информационных технологий
Специальность ИСиТ(э)
КОНТРОЛЬНАЯ РАБОТА
По курсу “Основы конструирования программ”
Вариант № 10
Студент-заочник 1 курса
Минск, 2012
Содержание
Вариант 10
1. Алгоритм – это набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий. 2. Свойства алгоритмов: • Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно. • Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного. • Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд. • Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0. • Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных. • Результативность — завершение алгоритма определёнными результатами. • Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе. • Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных. 3. Способы описания алгоритмов: Основные способы записи алгоритмов: • словесный (родном языке); • с помощью схем (графический); • языком псевдокоде; • языком программирования. 4. Базовые структуры схем алгоритма. это определенный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей действий. К основным структурам относятся следующие: • линейные • разветвляющиеся • циклические 5. Структурированные схемы и их построение. 6. Линейные и разветвляющиеся с труктуры. Линейными называются алгоритмы, в которых действия осуществляются последовательно друг за другом. Стандартная блок-схема линейного алгоритма приводится ниже:
Разветвляющимся называется алгоритм, в котором действие выполняется по одной из возможных ветвей решения задачи, в зависимости от выполнения условий. В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в разветвляющиеся алгоритмы входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (действий).
В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, которое может соблюдаться (быть истинно) или не соблюдаться (быть ложно). Такое утверждение может быть выражено как словами, так и формулой. Таким образом, алгоритм ветвления состоит из условия и двух последовательностей команд.
В зависимости от того, в обоих ветвях решения задачи находится последовательность команд или только в одной разветвляющиеся алгоритмы делятся на полные и не полные (сокращенные). Стандартные блок-схемы разветвляющегося алгоритма приведены ниже:
7. Циклические структуры. Типы циклов. Циклическим называется алгоритм, в котором некоторая часть операций (тело цикла — последовательность команд) выполняется многократно. Однако слово «многократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности — получения результата за конечное число шагов.
Перед операцией цикла осуществляются операции присвоения начальных значений тем объектам, которые используются в теле цикла. В цикл входят в качестве базовых следующие структуры:
• блок проверки условия • блок, называемый телом цикла
Существуют три типа циклов: • Цикл с предусловием • Цикл с постусловием • Цикл с параметром (разновидность цикла с предусловием)
Если тело цикла расположено после проверки условий , то может случиться, что при определенных условиях тело цикла не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называется циклом c предусловием.
Возможен другой случай, когда тело цикла выполняется по крайней мере один раз и будет повторяться до тех пор, пока не станет ложным условие. Такая организация цикла, когда его тело расположено перед проверкой условия, носит название цикла с постусловием.
Цикл с параметром является разновидностью цикла с предусловием. Особенностью данного типа цикла является то, что в нем имеется параметр, начальное значение которого задается в заголовке цикла, там же задается условие продолжения цикла и закон изменения параметра цикла. Механизм работы полностью соответствует циклу с предусловием, за исключением того, что после выполнения тела цикла происходит изменение параметра по указанному закону и только потом переход на проверку условия. Стандартные блок-схемы циклических алгоритмов приведены ниже:
8. Предопределенные процессы. Рекурсия. Предопределённый процесс- Символ отображает выполнение процесса, состоящего из одной или нескольких операций, который определен в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в него данные. Например, в программировании − вызов процедуры или функции.
Реку́рсия — процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии. Рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
9. Задача №10. (одномерный массив) найти номер последнего максимального элемента среди элементов, лежащих в диапазоне[c,d] и расположенных до первого четного элемента.
Нет
Да
Нет
Да
Нет
Нет Да
Описание: Задан целочисленный одномерный массив a из n элементов. Начало программы, ввод элементов(n) в диапазоне[c,d].
10. Задача №10. (двумерный массив) Проверить, все ли строки матрицы упорядочены по возрастанию. Если нет, найти первую неупорядоченную строку и упорядочить.
