Программирование алгоритмов линейной структуры

Введение

 

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

Язык Паскаль был разработан в начале 70-х годов ХХ века швейцарским  профессором Никлаусом Виртом как  инструмент для систематического обучения программированию. Для этого в состав языка были включены элементы структурного программирования (последовательные, разветвляющиеся и циклические структуры) и структуры данных (массивы, записи, файлы и т.д.). В 1983 году французский математик Филипп Кан разработал компактный, быстродействующий компилятор, названный Турбо Паскалем. В 1992 году фирма Borland International выпустила в свет очередную версию языка Турбо Паскаль 7.0 с улучшенным интерфейсом пользователя и более быстрым компилятором. Принципы построения программ, заложенные в Паскале, получили развитие в таких языка программирования как Ада, Модула-2, Си и т.д. Турбо Паскаль не только обеспечивает возможность создания больших программ, поддерживая их строгую логическую структуру, что весьма ценно для начинающих программистов, создающих серьезные программы, так как приучает их к определенной дисциплине. Кроме того, Паскаль считается достаточно простым и эффективным инструментом для решения инженерных задач.

Предлагаемые методические указания к выполнению лабораторных работ (части 3 и 4) разработаны в помощь первокурсникам в самостоятельном освоении одного из важнейших разделов курса информатики «Алгоритмизация и программирование». Изложение основных вопросов программирования подкрепляется конкретными примерами и сопровождается необходимыми комментариями. В приложениях содержится весь необходимый справочный материал. Для достижения наилучшего результата при изучении изложенного материала необходимо придерживаться следующих общих требований и рекомендаций по выполнению лабораторных работ:

- при подготовке к лабораторным  работам и в процессе их  выполнения студенты приобретают  навыки построения блок-схем и  практического программирования, учатся  эффективно использовать операторы  языка, а также анализировать  полученные результаты;

- перед выполнением лабораторной  работы студент обязан внимательно  ознакомиться с ее описанием,  изучить предлагаемый теоретический  материал (при необходимости следует  обратиться к дополнительным  источникам информации) и подготовить  бланк отчета, включающий титульный лист установленной формы, цель работы, текст варианта задания, соответствующие блок-схему, листинг программы и ответы на контрольные вопросы. Вариант задания выдается преподавателем. Студенты, неподготовленные к работе, к выполнению лабораторной не допускаются;

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

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

 

 

Лабораторная работа №1. Программирование алгоритмов линейной структуры

 

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

 

1.1 Алгоритм и блок-схема 

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

Алгоритм – это формальное описание способа решения задачи путем разбиения ее на конечную по времени последовательность понятных исполнителю действий (этапов).  При этом должны быть четко указаны как содержание каждого этапа, так и порядок выполнения этапов. Отдельный этап алгоритма либо представляет собой другую, более простую задачу, алгоритм которой разработан ранее, либо должен быть достаточно простым и понятным без пояснений. Наиболее распространенный вид алгоритма – графический выполняется в виде блок-схемы – совокупности геометрических фигур (блоков), связанных между собой при помощи стрелок. Все формулы в блок-схеме записываются на языке математики, а не конкретном языке программирования. В таблице А1 приведены наиболее используемые виды блоков. Блок-схемы выполняются в соответствии с ГОСТ 19.701-90, ЕСПД, но для упрощения записи их можно строго не соблюдать. Любой алгоритм синтезируют из типовых элементов: алгоритмов линейной, разветвляющейся и циклической структуры.

1.2 Особенности языка  Турбо Паскаль и структура  программы

К основным особенностям Турбо Паскаль  можно отнести довольно строгие  требования к структуре программы. Программа на языке Паскаль записывается в виде последовательности символов, к числу которых относятся латинские буквы, арабские цифры, знаки препинания, знаки операций. Для обозначения исходных данных и результатов вычислений (промежуточных и итоговых) употребляются переменные, имена (идентификаторы)  которых могут быть не только буквами - a, b, X, Y и т.д., но и последовательностью символов вида x1, time, alfa2 и т.д., которые состоят из букв и цифр и начинаются с буквы. Ключевые слова – это множество имен, которые используются в языке для написания операторов и других конструкций. Имена, применяемые пользователем для обозначения конструкция не должны совпадать с ключевыми словами. Список зарезервированных слов и перечень операций языка приведены в таблицах В1 и В2. Соответствующее исходное данное или результат вычисления называется значением переменной. Константы отличаются от переменной тем, что их значения не меняются в ходе выполнения программы. Числа записываются в десятичной системе, вместо запятой ставится точка: 0, -19, 0.27, 3.1415 и т.д.

К основным типам данных языка Паскаль относятся: вещественный (Real), целочисленный (Integer), логический (Boolean) и литерный (Char). Целые числа и числа с плавающей точкой могут быть представлены в различных формах (таблица В3).

Структура простейшей программы  на Паскале приведена в таблице  С1. В описательной части задается имя программы, все метки и константы, которые будут использоваться в программе, а также идентификаторы и тип переменных. Главной частью программы является ее исполнительная часть, то есть последовательность инструкций, которую должен выполнить компьютер. Эти инструкции принято называть операторами.

Более сложные арифметические выражения  строятся из операндов (констант и переменных), соединенных знаками арифметических операций. Кроме того, в выражении могут быть использованы круглые скобки и функции (таблица С2). Результатом расчета арифметического выражения является число. При составлении арифметических выражений должны соблюдаться следующие правила:

• два знака арифметических операций не должны стоять рядом;
• при вычислении значений арифметических выражений действуют правила старшинства операций: указатели функций; умножение и деление слева направо;  сложение и вычитание слева направо; круглые скобки изменяют этот естественный порядок, то есть старшим действием является действие в скобках.

 

1.3 Алгоритмы линейной  структуры и используемые в  них операторы

Алгоритм называется линейным, если все операции в нем выполняются последовательно друг за другом.

Оператор присваивания позволяет изменить текущее значение переменной. Вид оператора приведен в таблице D1. Вычисляется выражение, стоящее справа от знака ":=" ("присвоить"), полученный результат присваивается переменной, стоящей в левой части оператора. При этом старое значение, хранившееся в ней, безвозвратно пропадает. Например, Р:= 5; (в переменную Р запишется число 5).

Для ввода данных и  вывода результатов используются процедуры ввода и вывода (таблица D1). Существуют форматный и бесформатный способы вывода.

 

1.4 Пример алгоритма и программы  линейной структуры

Даны переменные a  и b. Найти

При составлении алгоритма  необходимо выделить однотипные выражения (здесь a²+b²), которые достаточно посчитать один раз, а затем использовать результат вычислений. Желательно разбить сложные вычисления одного выражения на более простые (например, отдельно вычислить числитель и знаменатель дроби) для того, чтобы в алгоритме не было громоздких формул. На рисунке 1.1 представлен вариант блок-схемы алгоритма и программа.

 

Program Primer1; Var a,b,c,z:real; Begin Write ('Введите a и b'); Read (a, b); C := sqr(a) + sqr(b); z := sqrt (sqrt(c)) + sin(c) – 1/с; Write('Z=', z:10:3) End.

Рисунок 1.1 - Блок-схема алгоритма и программа линейной структуры

 

Вычисление значения Z производится в следующей последовательности:

1. в блоке 2 вводятся исходные данные – значения a и b;
2. в блоке 3 вычисляется арифметическое выражение a²+b² и результат запоминается в переменной c;
3. в блоках 4-6 вычисляются первое слагаемое, числитель и знаменатель второго слагаемого;
4. в блоке 7 производится окончательный расчет Z;
5. в блоке 8 выводятся исходные данные и результат.

В программе действия блоков 3-7 записываются операторами  присваивания, блоки 2 и 8 реализуются  операторами ввода/вывода. Ввод осуществляется с запросом, поэтому сначала записан оператор Write, а затем Read. Вывод осуществляется форматным способом. Все переменные, участвующие в программе, объявляются в разделе Var ее описательной части.

 

1.5 Варианты заданий

Составить блок-схему и программу вычисления значений функции при заданных значениях аргумента.

 

1)	2)
3)	4)
5)	6)
7)	8)
9)	10)
11)	12)
13)	14)
15)	16)
17)	18)
19)	20)
21)	22)
23)	24)
25)	26)
27)	28)
29)	30)

 

1.6 Контрольные вопросы

1 Назовите основные этапы подготовки  и решения задач на ПК?

2 Что такое алгоритмический язык?

3 Что такое алгоритм? Назовите  основные свойства алгоритмов.

4 Что понимается под «блок-схемой»?  Назовите элементы блок-схемы.

5 Опишите структуру простейшей  Паскаль-программы.

6 Какие типы данных используются  в Паскале?

7 Какой алгоритм называется линейным? Опишите оператор присваивания.

8 Каких правил следует придерживаться  при составлении арифметических  выражений?

9 Подумайте как можно представить  в Паскале функции tg x, ctg x, lg x ?

10 Какие операторы используются  для ввода и вывода данных в Паскале?

11 Как осуществляется форматный  и бесформатный выводы в Паскале?

12 Как осуществляется вывод с  комментарием в Паскале?

 

 

Лабораторная работа №2. Программирование алгоритмов разветвленной структуры

 

Цель работы – ознакомление с  особенностями программирования алгоритмов разветвленной структуры, а также использования различных операторов перехода.

 

2.1 Алгоритмы разветвленной  структуры. Операторы перехода  и выбора

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

Оператор условного  перехода реализует разветвление алгоритма и применяется, когда в зависимости от условия необходимо выполнить либо одно, либо другое действие. В качестве условий используются логические отношения. Логические отношения представляют собой записи равенств и неравенств: <, >, =, <=, >=,<> (не равно), AND (логическое "и"), OR (логическое "или"). В Паскале оператор условного перехода имеет две конструкции (таблица D1).

В Паскале принят порядок  выполнения операторов согласно их следованию в программе. Если необходимо обойти какую-то группу операторов, то используется оператор безусловного перехода, который в блок-схеме отображается в виде стрелки, а не отдельного блока (таблица D1). Метка, используемая в операторе, показывает, что дальнейшая работа должна проводиться в другой части программы, с той строки, на которую она указывает и должна быть предварительно описана в разделе Label (например, Goto NM;). Этот оператор используется только в исключительных ситуациях, поскольку такие переходы разрушают связи между структурой программы и структурой вычислений, что приводит к потере ясности программы и затрудняет задачу верификации (доказательства правильности составления программы).

Кроме оператора безусловного перехода, в Турбо Паскале 7.0 иногда используются четыре безусловные функции:

-   Break – позволяет досрочно закончить цикл;

- Continue – позволяет начать новую итерацию цикла, не дожидаясь окончания предыдущей итерации;