Программирование линейных алгоритмов. Практикум. Практическая работа № 3.1 "Программирование линейных алгоритмов"


Планирование уроков на учебный год


Уроки 33 - 35
Программирование линейных алгоритмов
Практикум
Практическая работа № 3.1
"Программирование линейных алгоритмов"




Элементы языка Паскаль и типы данных







imageАлфавит. Алфавит языка состоит из множества символов, включающих в себя буквы, цифры и специальные символы.

Латинские буквы: от А до Z (заглавные) и от a до z (строчные).

Цифры: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Специальные символы: + - * / = < > [ ] . , ( ) : ; { } ^ @ $ #.

Следующие комбинации специальных символов являются едиными символами (их нельзя разделять пробелами):

image

Пробелы — символ пробела (код ASCII 32) и все управляющие символы кода ASCII (от 0 до 31).

imageСлужебные слова. К спецсимволам относятся и служебные слова, смысл которых определен однозначно. Служебные слова не могут быть использованы для других целей. С точки зрения языка, они являются едиными элементами алфавита. Вот некоторые служебные слова: Program, Var, array, If, Do, While и др.

imageИдентификаторы. Идентификатором называется символическое имя определенного программного объекта. Такими объектами являются: имена констант, переменных, типов данных, процедур и функций, программ. Идентификатор — это любая последовательность букв и цифр, начинающаяся с буквы. К буквам приравнивается также знак подчеркивания. Длина идентификатора может быть произвольной, но значащими являются только первые 63 символа.

imageКомментарии. Следующие конструкции представляют собой комментарии и поэтому пропускаются компилятором:

{любой текст, не содержащий символ "фигурная скобка"}
(* любой текст, не содержащий символы "звездочка, круглая скобка"*)
//последующий текст до конца строки

Буквы русского алфавита употребляются только в комментариях, символьных и текстовых константах.

Концепция типов данных в Паскале


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

Паскаль характеризуется большим разнообразием типов данных, отраженным на рис. 3.10.

image

Тип данных называется порядковым, если он состоит из счетного количества значений, которые можно пронумеровать. Отсюда следует, что на этом множестве значений существуют понятия «следующий» и «предыдущий».

В стандартном Паскале Вирта отсутствовал строковый тип. Он был внесен в Турбо Паскаль. Кроме того, в Турбо Паскале целые и вещественные — это группы типов. В старших версиях Турбо Паскаля появился процедурный тип и тип «объект».

Каждый тип имеет свой идентификатор. В таблице 3.2 представлена информация о простых типах данных, определенных в Турбо Паскале и последующих диалектах языка. Для вещественных типов в скобках указано количество сохраняемых значащих цифр мантиссы в десятичном представлении числа.

image

imageТипы пользователя. Одна из принципиальных возможностей Паскаля состоит в том, что пользователю разрешается определять свои типы данных. Типы пользователя всегда базируются на стандартных типах данных Паскаля. Для описания типов пользователя в Паскале существует раздел типов, начинающийся со служебного слова Туре. К простым типам пользователя относятся перечислимый и интервальный типы данных.

imageПеречислимый тип задается непосредственно перечислением (списком) всех значений, которые может принимать переменная данного типа:

Туре <имя типа> = (<список значений>)

Определенное таким образом имя типа затем используется для описания переменных. Например:

image

Здесь Gaz и Metal — имена перечислимых типов, которые ставятся в соответствие переменным Gl, G2, G3 и Met 1, Met2. Переменной Day назначается перечислимый тип, которому не присвоено имени.

Значения, входящие в перечислимый тип, являются константами. Действия над ними подчиняются правилам, применимым к константам. Каждое значение в перечислимом типе занимает в памяти 2 байта, поэтому число значений этого типа не должно превышать 65 535.

Перечислимый тип — упорядоченное множество. Его элементы пронумерованы, начиная от 0 в порядке следования в описании.

Структурные типы. Особенностью Паскаля является то, что в нем структуры данных рассматриваются как типы — структур-

В программе, в которой присутствует данное выше описание переменной Day, возможен такой фрагмент:

image

imageОграниченный тип задается как упорядоченное ограниченное подмножество некоторого порядкового типа:

<константа 1>..<константа 2>

Порядковый номер первой константы не должен превышать номера второй константы в соответствующем базовом типе.

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

image

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

Автор Паскаля Вирт придавал большое значение разнообразию типов данных в языке программирования. В своей книге «Алгоритмы и структуры данных» он подчеркивает зависимость алгоритма решения задачи от способа организации данных в программе. Удачно выбранный способ организации данных упрощает алгоритм решения задачи.

image

Вопросы и задания


1. Входят ли в алфавит Паскаля русские буквы? Для чего их можно использовать?

2. Что такое идентификатор? Каковы правила задания идентификаторов?

3. Чем различаются разные типы данных из группы целочисленных типов?

4. Чем различаются разные типы данных из группы вещественных типов?

5. В чем разница между простыми и структурными типами?

6. Что такое перечислимый и ограниченный типы данных?

Операции, функции, выражения








Арифметические операции


К числовым типам данных относятся группы вещественных и целочисленных типов. К ним применимы арифметические операции и операции отношений. Операции над данными бывают унарными (применимые к одному операнду) и бинарными (применимые к двум операндам).

imageУнарная арифметическая операция в Паскале одна. Это операция изменения знака. Ее формат:

-<величина>

imageБинарные арифметические операции стандартного Паскаля описаны в табл. 3.3. В ней символ «I» обозначает целые типы, символ «R» — вещественные типы.

image

Стандартные функции и процедуры


В Паскале существует большое количество стандартных функций и процедур, к которым программист может обращаться в своих программах. Наиболее часто используются математические функции, например: sqrt(x) — квадратный корень, abs (х) — абсолютная величина, sin (х) и др. Часто используемые стандартные процедуры: Read(...) — процедура ввода, Write (...) — процедура вывода данных.

Стандартные функции и процедуры являются внешними подпрограммами по отношению к вызывающей их программе. Они объединены в модули, которые подключаются к основной программе и становятся доступными для использования. Наиболее часто используемые подпрограммы объединены в модуль под названием SYSTEM. Этот модуль подключается к программе автоматически.

Таблица 3.4 содержит описания стандартных математических функций Паскаля.

image

Для подключения других модулей необходимо в начале программы (после заголовка) записать строку:

Uses <имя модуля>

Для управления символьным выводом на экран используется стандартный модуль CRT. К программе он подключается командой:

Uses CRT

В дальнейшем из этого модуля мы будем использовать процедуру очистки экрана для символьного вывода, обращение к которой производится оператором ClrScr.

Арифметические выражения


Арифметическое выражение задает порядок выполнения действий над числовыми величинами. Арифметические выражения содержат числовые константы и переменные, арифметические операции, функции, круглые скобки. Одна константа или одна переменная — простейшая форма арифметического выражения.

Например, рассмотрим математическое выражение:

image

На Паскале оно выглядит так:

(2*A + Sqrt(0.5*sin(X + Y))) / (0.2*C - ln(X - Y))

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

1. Все символы пишутся в строчку на одном уровне. Проставляются все знаки операций (нельзя пропускать знак *).

2. Не допускаются два следующих подряд знака операций. (Нельзя: А+-В; можно: А+ (-В).)

3. Операции с более высоким приоритетом выполняются раньше операций с меньшим приоритетом. Порядок убывания приоритетов:

вычисление функции;
унарная операция смены знака (-);
*, /, div, mod;
+, -.

4. Несколько записанных подряд операций одинакового приоритета выполняются последовательно слева направо.

5. Часть выражения, заключенная в скобки, вычисляется в первую очередь. (Например, в выражении (А+В) * (C-D) умножение производится после сложения и вычитания.)

Не следует записывать выражения, не имеющие математического смысла, например: деление на нуль, логарифм отрицательного числа и т. п.

Пример. Цифрами сверху указан порядок выполнения операций:

image

Данное арифметическое выражение (на Паскале) соответствует следующему математическому выражению:

image

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

а) если у — целое положительное значение, то его степень вычисляется через умножение; например х3 —> х*х*х; большие степени следует вычислять умножением в цикле; 

б) если у — целое отрицательное число, то степень вычисляется так: ху = (1/х)|y|; а при у = 0: х0 = 1.

в) если у — вещественное значение, не равное нулю, то используется следующая математическая формула: ху = еу1n(-х) На Паскале получим арифметическое выражение:

exp(Y*ln(х))

Очевидно, что в этом случае не допускается нулевое или отрицательное значение х. Для целого у такого ограничения нет.

image

На Паскале это выражение выглядит так:

ехр(1/3*ln(А+1))

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

image

Вопросы и задания


1. Для следующих математических выражений запишите соответствующие арифметические выражения на Паскале:

image

2. Запишите математические выражения, соответствующие следующим выражениям на Паскале:

image

3. Для следующих математических выражений запишите соответствующие арифметические выражения на Паскале:

image

4. Вычислите значения выражений:

image

5. Определите типы выражений:

image

Оператор присваивания, ввод и вывод данных







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

1) оператор присваивания;
2) оператор ввода;
3) передача значения через параметры подпрограммы.

imageОператор присваивания имеет следующий формат:

<переменная>:=<выражение>

image

Сначала вычисляется выражение, затем полученное значение присваивается переменной. В первом примере приведен арифметический оператор присваивания. Здесь х — переменная вещественного типа. Во втором примере — логический оператор присваивания. Здесь b — переменная типа Boolean.

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

Ввод и вывод данных


Под вводом понимается передача данных с внешнего устройства компьютера в оперативную память. При выводе данные передаются из оперативной памяти на внешнее устройство (рис. 3.11).

image

Операция ввода называется чтением и выполняется с помощью оператора Read. Вывод называется записью, и для его выполнения используется оператор Write.

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

Для внешних запоминающих устройств (ВЗУ) файл — это поименованная область памяти этого устройства. В файлы на ВЗУ можно записывать данные по команде Write и можно читать данные из файлов по команде Read. На одном устройстве ВЗУ может храниться множество файлов одновременно. Правила именования файлов на ВЗУ определяются операционной системой. Имена для файлов, создаваемых пользователем, задает сам пользователь.

Устройства ввода с клавиатуры и вывода на экран монитора являются однофайловыми устройствами. Считается, что с клавиатурой связан один системный файл с именем INPUT. Поэтому ввод с клавиатуры равнозначен чтению из файла INPUT. С монитором связан системный файл, который называется OUTPUT. Вывод на экран — это запись данных в файл OUTPUT .

imageВвод с клавиатуры производится путем обращения к стандартной процедуре Read в следующем формате:

Read(<список ввода>)

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

Например:

Read(a, b, с, d)

При выполнении этого оператора происходит прерывание исполнения программы, после чего пользователь должен набрать на клавиатуре значения переменных а, Ъ, с, d, отделяя их друг от друга пробелами. При этом вводимые значения высвечиваются на экране. В конце нажимается клавиша Enter. Значения следует вводить в строгом соответствии с синтаксисом Паскаля.

image

Если в программе имеется несколько подряд идущих операторов Read, то данные для них можно вводить последовательно (на экране отражаются в одной строке) и лишь в конце ввода нужно нажать клавишу Enter.

image

Здесь слово «ReadLn» означает read line — «читать строку». Нажатие клавиши Enter в процессе ввода вырабатывает признак «конец строки», и данные при выполнении следующего оператора ввода будут отражаться на экране с начала новой строки. Если в предыдущем примере заменить операторы Read на ReadLn:

ReadLn(А, В); ReadLn(С, D) ;

то ввод значений будет происходить из двух строк, отраженных на экране:

18758 34 [Enter]

2.62Е-02 1.54Е+01 [Enter]

imageВывод на экран производится по оператору обращения к стандартной процедуре:

Write(<список вывода>)

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

Например: Write ('Сумма А, ' + ', В, ' = ', А+В)

Если, например, А = 5 и В = 7, то на экране получим:

Сумма 5+7=12

При выводе на экран нескольких значений в строку они не отделяются друг от друга пробелами. Программист сам должен позаботиться о таком разделении. В приведенном примере предусмотрен пробел после слова «Сумма».

Второй вариант процедуры вывода на экран:

WriteLn(<список вывода>)

Write line — «писать строку». Его действие отличается от оператора Write тем, что после вывода последнего в списке значения происходит перевод курсора к началу следующей строки. Оператор WriteLn, записанный без параметров, вызывает перевод строки.

В списке вывода могут присутствовать указатели форматов вывода (форматы). Формат определяет представление выводимого значения на экране. Формат отделяется от соответствующего ему элемента двоеточием. Если указатель формата отсутствует, то машина выводит значение по определенному правилу, предусмотренному по умолчанию.

imageЛинейная программа. Следование — простейшая алгоритмическая структура. Программа, реализующая следование, называется линейной программой. В линейной программе могут присутствовать только операторы присваивания, ввода, вывода и обращения к процедурам. Заметим, что операторы Read и Write являются обращениями к стандартным процедурам Паскаля.

Одним из обязательных условий хорошего стиля программирования является организация диалога между компьютером и пользователем. Такое диалоговое взаимодействие называется интерактивным интерфейсом.

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

image

Тестирование этой программы отразится на экране следующим образом.

А= 13

В= 28

13*28=364

Числа 13 и 28 вводятся пользователем с клавиатуры, всё остальное автоматически выводится по программе.

imageПример 2. Дано натуральное трехзначное число. Требуется вычислить сумму его цифр. Например, если дано число 325, то в результате должно получиться: 3 + 2 + 5 = 10.

Сначала составим программу, а потом ее прокомментируем.

image

В этой программе использованы две операции целочисленной арифметики: div — целочисленное деление и mod — остаток от целочисленного деления (см. табл. 3.3). Остаток от деления на 10 (mod) выделяет младшую цифру числа, а целочисленное деление на 10 (div) отбрасывает младшую цифру.

image

Чтобы лучше понять работу программы, выполним ее трассировку. В курсе 9 класса вам уже приходилось строить трассировочные таблицы. Для программы SumCifr таблица будет выглядеть следующим образом:

image

Выполнение программы на компьютере приводит к такому же результату.

Заметим, что эту задачу можно решить с помощью всего одного оператора присваивания:

Sum: =Х mod 10 + X div 10 mod 10 + X div 100

Проверьте самостоятельно.

image

Вопросы и задания


1. Назовите последовательность действий при выполнении оператора присваивания.

2. Сформулируйте правило соответствия типов для оператора присваивания. Какое существует исключение из этого правила?

3. Если у — вещественная переменная, а n — целая, то какие из следующих операторов присваивания правильные, а какие — нет?

image

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

5. Напишите оператор присваивания, в результате выполнения которого целочисленной переменной h присвоится значение цифры, стоящей в разряде сотен в записи положительного целого числа k (например, если k = 28 796, то h = 7).

6. Напишите линейную программу, в результате выполнения которой в целочисленной переменной S получится перевернутое целое четырехзначное число k. Например: если k = 1357, то S = 7531.

7. Напишите линейную программу перевода любого целого четырехзначного двоичного числа в десятичную систему счисления. Например, дано число в двоичной системе счисления: 11012. Перевод в десятичную систему выполняется так: 1 • 23 + 1 • 22 + 0 • 21 + 1 = 13.



Практикум


Работа 3.1. Программирование линейных алгоритмов


Задание


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

Уровень 1


1. Вычислить длину окружности и площадь круга одного и того же заданного радиуса R.

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

3. Дана длина ребра куба. Найти площадь грани, площадь полной поверхности и объем этого куба.

4. Три сопротивления R1, R2, R3 соединены параллельно. Найти сопротивление всей цепи.

5. Найти сумму членов арифметической прогрессии, если известны ее первый член, разность и число членов прогрессии.

6. Вычислить корни квадратного уравнения ах2 + bх + с = О с заданными коэффициентами а, b и с (предполагается, что а ≠ О и что дискриминант уравнения неотрицателен).

7. Найти площадь равнобедренной трапеции с основаниями а и b и углом α при большем основании а.

Уровень 2


8. Заданы координаты трех вершин треугольника (x1, у1), (х2, у2), (x3, у3). Найти его периметр и площадь.

9. Найти произведение всех цифр заданного четырехзначного числа.

10. Вычислить площадь и периметр правильного N-угольника, описанного около окружности радиуса R (рассмотреть N — целого типа, R — вещественного типа).

11. Дано натуральное число Т — длительность прошедшего времени в секундах. Вывести данное значение длительности в часах (НН), минутах (ММ) и секундах (SS) в следующей форме: НН ч ММ мин SS с.

12. Дано действительное число R вида nnn.ddd (три цифровых разряда в целой и дробной частях). Поменять местами дробную и целую части числа и вывести полученное значение числа.

13. Составить программу перевода радианной меры угла в градусы, минуты и секунды.

14. С начала суток часовая стрелка повернулась на у градусов (О ≤ у < 360, у — вещественное число). Определить число полных часов и полных минут, прошедших с начала суток. Сформулировать и решить обратную задачу.

Уровень 3


15. Дан произвольный треугольник ABC, для которого определен следующий набор характерных параметров: а, b, с — стороны треугольника; α, β, γ — углы (в градусах); h — высота, опущенная на сторону с; S — площадь; Р — периметр треугольника. По трем заданным параметрам вычислить все остальные. Различные сочетания параметров определяют варианты заданий.

Замечание: входные (исходные) и выходные значения углов представить в градусной мере.

image





Наверх