программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент

• Название: Учебное пособие Томск Эль Контент
• Анкор: программирование тусур
• Дата: 17.08.2022
• Размер: 0.93 Mb.
• Имя файла: Программирование учебное пособие.pdf
• Тип: Учебное пособие; #647947
• страница: 5 из 16

Глава 2. Азы языка Паскаль
• собственно действия, выполняемые на каждой итерации (оператор тела цикла).
<оператор цикла с параметром> ::=
for
<переменная> := <диапазон> do <оператор>
<диапазон> ::= <выражение> <направление> <выражение>
<направление> ::= to | downto
На использование управляющей переменной (параметра) налага- ются следующие ограничения:
1. Управляющая переменная должна иметь дискретный тип
(целый, символьный, булевский, перечислимый).
2. Начальные и конечные значения диапазона должны иметь тот же тип, что и параметр.
3. В теле цикла запрещается явное изменение значения управ- ляющей переменной (например, оператором присваивания).
4. После завершения оператора значение параметра становит- ся неопределенным.
Семантику данного оператора цикла можно представить следующим образом.
Оператор for V := Expr1 to Expr2 do Body;
эквивалентен оператору:
begin
Temp1 := Expr1;
Temp2 := Expr2;
if Temp1 <= Temp2 then begin
V:=Temp1;
Body;
while V <> Temp2 do begin
V:=succ(V);
Body end end end
Пример
{y=x
∧
n}
y:=1;

2.4 Пустой оператор и ограниченные типы
45
for i:=1 to n do y:=y*x;
{печать латинского алфавита с конца}
for c:=
'z' downto 'a' do write(c);
Цикл while является универсальным, цикл repeat и цикл с параметром всегда можно заменить подходящим циклом while.
Циклы while и repeat могут работать бесконечно долго.
Пример
1. Тривиальный пример — предусловие константа:
while true do <оператор>
2. y:=0;i:=1;
while i<=n do y:=y+1/i;i:=i+1;
Тело цикла состоит из одного оператора y:=y+1/i, и переменная i в нем не меняется.
3. Задача: вычислить площадь под параболой f
(x) = x
2
от a = 0 до b = 10 по формуле трапеции S = h
× [f (a)/2+f (a+h)+f (a+2×h) + . . . + f (b−h)+f (b)/2],
где h = (b
− a)/n.
h:=(b-a)/n;
S:=h*(a*a+b*b)/2;
x:=a;
repeat x:=x+h;
S:=S+x*x*h until x=b-h;
Нужно написать постусловие в виде x>=b
−h, так как равенство может и не выполниться.
2.4 Пустой оператор и ограниченные типы
Пустой оператор является в некотором смысле парадоксальной конструкци- ей, так как он, во-первых, не имеет «графического» начертания, а во-вторых, не производит никаких действий. Необходимость введения такого понятия диктуется в первую очередь синтаксическими причинами. Синтаксис языка определяет сим- вол ';' (точка с запятой) как разделитель операторов. Таким образом, последний оператор, например, в составном операторе не должен завершаться этим символом,
так как после него не следует оператор, а идет служебное слово end:
begin S1;S2;. . .;SN end

46
Глава 2. Азы языка Паскаль
Однако если предположить, что между последним оператором SN и служебным словом end расположен пустой оператор, то становится допустимой такая форма записи:
begin S1;S2;. . .;SN; end что в ряде случаев более предпочтительно.
Пустой оператор удобно использовать и в тех случаях, когда по той или иной причине необходимо организовать некоторый составной оператор, не содержащий в себе ни одного оператора, например,
writeln(
'нажмите любую клавишу');
repeat until Keypressed;
Функция (без параметров) выдает истину, если нажата любая клавиша. С по- мощью этого фрагмента мы можем остановить выполнение программы, чтобы посмотреть промежуточную печать.
Пример
Экзотические конструкции:
1) begin S1;;;;;S2; end
2) if Cond then begin end else while true do;
3) if Cond then;
Все эти примеры операторов синтаксически правильны (но бесполезны).
Стандартные дискретные типы (целый, символьный, булевский, перечисли- мый
1
) — предопределены, но пользователь может создать (определить) собствен- ный дискретный тип.
Ограниченный тип определяется сужением (ограничением) допустимого диа- пазона значений некоторого стандартного дискретного типа. Задается минимальное и максимальное значение диапазона.
Так можно задать ограничения для целого или для символьного типов:
1..10
−100..100
'a'..'z'
Ограничение может присутствовать в описании переменной:
var s:1..10;
Можно ввести идентификатор для нового типа. Для этого в программе вводится раздел описаний, начинающийся со служебного слова type:
type digits=0..9;
1
О перечислимом типе см. раздел 6.1.

2.5 Функции
47
sto=
−100..100;
letter=
'a'..'z';
var n:digits;
Ограниченный тип наследует все свойства базового типа (в частности, набор допустимых операций).
Активно используйте ограниченные типы:
• наглядность программы,
• контроль ошибочных выходов значений за пределы задан- ного диапазона (как при трансляции, так и при выполнении).
2.5 Функции
Кроме стандартных (предопределенных) функций, программист может опреде- лить новые функции. Смысл функций заключается в первую очередь в том, чтобы определить алгоритм вычисления нового значения некоторого простого (или ссы- лочного) типа. В этом отношении функции подобны выражениям, которые также вычисляют значения. В соответствии с этим вызов функции является одним из до- пустимых операндов выражения, обозначая в нем то значение, которое вычисляет
(«вырабатывает» или «возвращает») функция.
Новая функция (а их может быть несколько) определяется в разделе описания,
как правило, после описания переменных в виде:
function
<имя функции><формальные параметры>:<тип значения>;
<описания локальных констант, типов, переменных>
begin
<операторы>
end;
Пример
1. Программа, вычисляющая наибольшее значение из трех чисел:
var m,n,k:real;
function max(x,y:real):real;
{максимум двух чисел}
begin if x>y then max:=x else max:=y end;
begin

48
Глава 2. Азы языка Паскаль
writeln(
'введите три числа');
readln(m,n,k);
writeln(
'максимум=',max(max(m,n),k))
end.
Пример
2. Вычисление суммы десятичных цифр натурального числа:
type natural=0..maxint;
var n:natural;
function sumDigits(a:natural):natural;
{вычисляет сумму цифр числа a}
var m,b:natural;
begin m:=0;
repeat b:=a mod 10;
m:=m+b;
a:=a div 10;
until a=0;
sumDigits:=m end;
begin writeln(
'введите число');
readln(n);
writeln(
'Сумма цифр числа ',n,'= ',sumDigits(n));
end.
Синтаксис формальный параметров функций описывается правилами:
<формальные параметры> ::=
(<описание параметров>{;<описание параметров>})
<описание параметров> ::=
<идентификатор> {,<идентификатор>} : <идентификатор типа>
Список формальных параметров может быть пустым — функция может быть без параметров.
В теле функции могут использоваться локальные объекты (в том числе и фор- мальные параметры), а также глобальные объекты (т. е. типы, константы, перемен- ные, описанные вне функции).

2.6 Примеры программ без массивов
49
Чтобы функция действительно вычисляла нужное значение, необходимо при- сутствие в теле функции оператора присваивания (новая форма!) в виде:
<имя функции> := <выражение, вычисляющее возвращаемое значение>;
Таких операторов может быть несколько. Хотя бы один должен работать.
При вызове функции фактические параметры должны соответствовать фор-
мальным по количеству и типу.
Понятие функции является частным случаем подпрограммы. Подпрограмма —
это запись вспомогательных алгоритмов. Другим частным случаем подпрограмм в языке Паскаль является процедура.
Программа в общем виде содержит четыре раздела описаний; любой из этих разделов может отсутствовать:
const
<описания констант>
type
<описание типов>
var
<описания переменных>
<описание функций и процедур>
begin
<операторы>
end
Указанный порядок описаний является стандартным, но могут быть исключе- ния. Действует универсальное правило для написания программы: если при опи- сании какого-то объекта (типа, переменной, функции или процедуры) требуется другой объект (константа, тип, переменная), то последний объект должен быть описан раньше.
2.6 Примеры программ без массивов
Задача 1. Даны две целые переменные a, b. Составить фрагмент программы,
после исполнения которого значения переменных поменялись бы местами (новое значение a равно старому значению b, и наоборот).
Решение. Введем дополнительную целую переменную t.
t := a;
a := b;
b := t;
Задача 2. Дано целое число a и натуральное (целое неотрицательное) число n.
Вычислить a
n
Для использования циклов полезно понятие инварианта цикла. Логическое утверждение, истинное перед выполнением и после выполнения каждого шага цикла, называется инвариантным отношением или просто инвариантом цикла.
Во многих случаях полезно явно найти инвариант (и указать его в виде аннотации к циклу).
Решение. Введем целую переменную k, которая меняется от 0 до n, причем поддерживается такое свойство (инвариант) b = a
k

50
Глава 2. Азы языка Паскаль
k := 0; b := 1;
{b = a
∧
k (a в степени k)}
while k <> n do begin k := k+1; b := b*a; end;
Другое решение той же задачи.
k := n; b := 1;
{a
∧
n = b
∗ a
∧
k}
while k <> 0 do begin k := k
−1; b := b∗a; end;
Задача 3. Решить предыдущую задачу, если требуется, чтобы число действий
(выполняемых операторов присваивания) было порядка log n (т. е. не превосходило бы C
⋅ log n для некоторой константы C; log n — логарифм n по основанию 2).
Решение.
k := n; b := 1; c := a;
{a
∧
n = b
∗ c
∧
k}
while k <> 0 do if k mod 2 = 0 then begin k := k div 2; c := c
∗ c; end else begin k := k
−1; b := b∗c; end;
Каждый второй раз (не реже) будет выполняться первый вариант оператора выбора (если k нечетно, то после вычитания 1 становится четным), так что за два цикла величина k уменьшается, по крайней мере, вдвое.
Задача 4. Дано натуральное n. Вычислить 1
/0! + 1/1! + 1/2! + . . . + 1/n! (x!
обозначает произведение всех натуральных чисел от 1 до x, 0!
= 1). Требуется,
чтобы количество операций (выполненных команд присваивания) было порядка n
(не более C
⋅ n для некоторой константы C).
Решение. Инвариант: sum
= 1/0!+1/1!+. . .+1/k!. last = 1/k! (важно не вычислять заново каждый раз k!).
sum:=0; last:=1; k:=0;
while k =< n do begin sum:=sum+last; k:=k+1; last:=last/k; end
Задача 5. Вычисление значений функции. Следующая программа предназна- чена для вывода таблицы значений функции f (x) = x/(1+x) на экран.
var x: real;
k: word;
function f(x: real): real;
begin f := x/(1.0+x);
end;
begin x:=0.0;
writeln(
'Таблица значений функции f(x) = x/(1.0+x)');
writeln;
writeln(
'x':10, 'f(x)':20);
writeln;
for k:= 0 to 50 do

2.6 Примеры программ без массивов
51
begin writeln(x:10:4, f(x):20:10);
x:= x+0.1;
if k mod 10 = 9 then readln;
end;
writeln;
write(
'Нажмите ');
readln;
end.
Обратите внимание на то, что программа приостанавливает вывод через каждые
10 строк и ожидает нажатия клавиши Enter.
Задача 6. Извлечение корня из действительных чисел. Известно много раз- личных методов извлечения корня. В программировании удобнее всего пользовать- ся универсальным методом, т. е. таким методом, в соответствии с которым одни и те же, хотя бы более продолжительные, вычисления выполняются при любых ис- ходных данных. Таким методом является метод итерации. Корень с натуральным основанием
y
=
m
√
x,
x
⩾ 0,
где m — натуральное число, извлекается по формуле:
y
n
=
1
m
((m − 1)y
n
−1
+
x
y
m
−1
n
−1
) .
Поясним, каким образом по этой формуле можно получить корень y
=
m
√
x. Сна- чала примем, что корень равен произвольному числу (например, y
0
= 1; доказано,
что получающееся в результате значение корня не зависит от того, какое значение
y
0
мы избрали в качестве исходного), вычисляем новое значение y
1
, затем опять новое значение корня y
2
и т. д. Каждое новое значение y
n
оказывается все ближе к подлинному значению корня. Когда разность между значением y
n
и предыду- щим значением y
n
−1
становится весьма малой — меньшей, нежели допустимая по- грешность, принимаем, что полученное значение y
n
является корнем и вычисление заканчивается.
Приведем ряд примеров, показывающих, как извлекается кубический корень из 125 при различных исходных значениях (табл. 2.4).
Таблица 2.4 – Последовательные приближения
y
0 125.0 1.0 10.0
y
1 83.3 42.3 7.1
y
2 55.6 28.2 5.6
y
3 37.1 18.9 5.1
y
4 24.7 12.7 5.0
y
5 16.6 8.7 5.0
Написав yy вместо y
n
и y вместо y
n
−1
(где n = 1, 2, 3,. . .), составим следующий фрагмент программы извлечения корня m-ой степени из неотрицательного числа x:

52
Глава 2. Азы языка Паскаль
yy:=1.0; {исходное значение корня}
repeat y:=yy; yy:=y
∗(m−1)/m+x/power(y, m−1)/m until abs(yy
−y) < epsilon;
root:=yy;
Здесь power(y, m) — функция, которая возводит число y в m-ую степень,
а epsilon — допустимая погрешность при извлечении корня.
Этот, правильный на первый взгляд, фрагмент программы практически не очень хорош. Извлекая корень более высокой степени, можно получить очень большой результат функции power. Например, если мы будем извлекать корень
100
√
10000.0,
т. е. выполним программу при m = 100 и x = 10000.0, то при первом прохождении цикла получим yy
≈ 100. При повторном прохождении цикла необходимо будет это число возвести в 99-ю степень. Хотя интервал действительных чисел в вычисли- тельной машине очень велик, однако в данном случае мы получим значение, не попадающее в этот интервал, т. е. произойдет переполнение. Это выглядит неесте- ственным: если число, из которого мы извлекаем корень, находится в допустимом интервале, то и значение корня будет находиться в том же самом интервале. По- этому для пользователя данной программы будет совершенно непонятно, почему машина прекратила вычисления вследствие переполнения, тогда как исходное чис- ло не очень велико.
Чтобы избежать переполнения, не будем возводить число yy в степень; вместо этого будем много раз делить число x на yy.
Составим функцию извлечения корня m-ой степени (m — натуральное число)
из неотрицательного числа x с точностью до 0.00001:
function root(x:real; m:integer):real;
{корень m-ой степени из x}
const epsilon = 0.00001;
var y, yy, w, z, mm: real;
k: integer;
begin yy := 1.0; {исходное значение корня}
mm := (m
−1)/m; z := x/m;
repeat y := yy;
k := 1;
w := z;
while (k < m) and (w >= epsilon) do begin w := w/yy;
k := k+1;
end;
yy := y*mm+w;
until abs(yy
−y) < epsilon;
root := yy end;
Обратим внимание на два момента.

Контрольные вопросы по главе 2
53
Формулу извлечения корня мы разбили на две части. Одну часть действия мы вынесли из цикла, а другую часть оставили в цикле. Это было сделано из соображений экономии. Значения (часть значений), которые не изменяются при прохождении цикла, достаточно вычислить один раз, до начала цикла. В цикле остаются только те значения, которые изменяются в процессе прохождения цикла.
Такое преобразование вычислений называется чисткой цикла.
Когда требуется извлечь корень более высокой степени, то при вычислении w := w/yy частное может оказаться весьма малым, еще прежде чем деление бу- дет произведено m
− 1 раз. Поэтому цикл может быть закончен раньше, т. е. когда частное станет меньшим, нежели epsilon. Это сокращает время работы машины.
Однако здесь есть еще более существенный момент. Когда получаются очень малые действительные числа, может возникнуть странное на вид явление — переполнение в сторону малых чисел. Ведь чем меньше число, тем больше абсолютная величина его порядка (например, 1E
−60, 1E−70, 1E−89 и т. д.). В результате число, выража- ющее порядок, может не уместиться в отведенное для него место. Прерывая цикл раньше, мы избегаем этого явления.
Контрольные вопросы по главе 2 1. Напишите какую-нибудь небольшую программу на Паскале. Проведите два эксперимента с ней. Первый: отформатируйте программу в редакторе так,
чтобы на каждой строчке было только по одной лексеме программы. До- пускает ли ваша версия Паскаля синтаксическую правильность такого фор- матирования? Во втором эксперименте разместите всю программу в виде одной длинной строки. Успешна ли трансляция такой программы?
2. Каким образом в Паскале можно вычислить значения математических функций: тангенс, котангенс, арксинус, арккосинус, арккотангенс?
3. Вопросы к задаче 1 из раздела 2.6:
Почему нельзя обменять значения у переменных, написав просто a := b;
b := a
? А как все-таки обойтись без дополнительной переменной?
4. В языке Паскаль значением вещественной переменной (скажем, x) может быть только вещественное число, и в то же время допускается оператор присваивания, который вещественной переменной присваивает целое число
(например, x := 7). Как в языке устраняется это противоречие?
5. Определите операцию div через другие операции и стандартные функции.
Целой переменной s присвоить сумму цифр трехзначного целого числа k.
6. Присвоить целой переменной d первую цифру дробной части положитель- ного вещественного числа x (например, если x = 32.597, то d = 5).
7. Запишите на Паскале отношение, истинное при выполнении указанного условия и ложное в противном случае: натуральное n является квадратом целого числа.

54