Министерство образования Республики Беларусь

 

Учреждение образования

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

 

 

 

 

 

Контрольная работа по курсу

" ОСНОВЫ КОНСТРУИРОВАНИЯ ПРОГРАММ"

вариант №1

 

 

  

 

 

 

Выполнил Андриенко Владимир Владимирович

Группа № 192301

Проверил Мытник Николай Петрович

 

 Минск 2011

1.Теоретическая часть

1.1 Определение алгоритма

Алгоритм - это конечная последовательность команд исполнителю для выполнения некоторой работы или решения задачи. Создание алгоритма, пусть даже самого простого – процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело – реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принять называть формальным исполнителем. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершить исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образуют систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.

1.2 Свойства алгоритма

Разработать алгоритм решения задачи означает разбить задачу на последовательно выполняемые шаги, причем результаты выполнения предыдущих этапов могут использоваться при выполнении последующих. При этом должны быть четко указаны как содержание каждого шага, так и порядок выполнения шагов, т.к. компьютер – формальный исполнитель.

Свойства:

• Понятность – каждая команда должна быть понятна исполнителю, т.е. входить в систему команд исполнителя.

• Дискретность(прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных шагов). Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

• Определенность(детерминированность) – каждое правило алгоритма должно быть четким, однозначным. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

• Результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определённый результат. Вывод о том, что решения не существует - тоже результат.

• Массовость – алгоритм должен решать любую задачу из того класса задач, для решения которых он разработан. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. Например, алгоритм решения квадратного уравнения должен решать любое квадратное уравнение.

1.3 Способы описания алгоритма

Для описания алгоритмов существует множество способов. Основные способы описания следующие:

• словесный;

• алгоритмический язык;

• схема;

• псевдокод.

Алгоритмический язык — формальный язык, используемый для записи, реализации и изучения алгоритмов. Всякий язык программирования является алгоритмическим языком, но не всякий алгоритмический язык пригоден для использования в качестве языка программирования. Под схемой программы будем понимать графическое представление последовательности шагов алгоритма, которое наглядно показывает очередность и взаимосвязь операций, осуществляемых в алгоритме на каждом его шаге. Иначе говоря, схема программы служит для графического изображения структуры алгоритма. Любая схема содержит набор геометрических фигур или блоков. Последовательность действий указывается с помощью стрелок, соединяющих отдельные блоки

Псевдокод — язык описания алгоритмов, использующий ключевые слова языков программирования, но опускающий подробности и специфический синтаксис.

1.4 Базовые структуры блок-схем

Базовые алгоритмические структуры. Используя исходные элементы блок-схем можно собрать более крупные кирпичики, которые называют базовыми структурами. Базовые структуры (конструкции):

• следование;

• ветвление (полное и не полное);

• повторение (цикл с предусловием или постусловием);

• вход;

• выход.

Каждая базовая структура имеет один вход и один выход. Схемы основных базовых алгоритмических структур:

• Следование Повторение (Цикл )

• Ветвление (полное)

• Выбор (оператор switch)

1.5 Структурированные блок схемы и их построение

Блок-схема называется структурированной, если она построена на основе базисного множества базовых структур. Для построения структурированных блок-схем была разработана специальная технология, которая называется пошаговой детализацией. Пошаговая детализация представляет собой процесс дробления задачи на модули, т.е. исходя из общей задачи, вычленяются подзадачи, устанавливаются логические связи между ними. После этого переходят к уточнению выделенных подзадач. Этот процесс детализации продолжается до уровня позволяющего достаточно легко реализовать подзадачу на выбранном языке программирования. При пошаговой детализации используется принцип замещения, который состоит в замене любого функционального блока (прямоугольника) блок-схемы некоторой базовой структурой (следование, ветвление, повторение) из исходного базисного множества. Достоинство пошаговой детализации состоит в том, что она позволяет разработчику алгоритма упорядочить свои рассуждения.