Управление и оптимизация / Osnovi informatsionnikh i komputernikh tekhnologiy 2011

−a mod b - вычисление остатка при делении а на b нацело (b не может быть равно нулю). Тип результата, как и в предыдущем случае, определяется типами операндов. В отличие от математической операции mod, результатом которой всегда является неотрицательное число, знак результата операции mod определяется знаком ее первого операнда. Пример: (-2 mod 5)= -2.

−a shl k - сдвиг значения а на k битов влево (это эквивалентно умножению значения переменной а на 2k), освободившиеся младшие разряды заполняются нулями. Результат операции будет иметь тот же тип, что и первый ее операнд (а).

−a shr k - сдвиг значения а на k битов вправо (это эквивалентно делению значения переменной а на 2k нацело) освободившиеся старшие разряды заполняются нулями. Результат операции будет иметь тот же тип, что и первый ее операнд (а).

Операции двоичной арифметики and,or,not,xor -, работающие с битами двоичного представления целых чисел, по тем же правилам, что и соответствующие им логические операции.

not - логическое НЕ; and - логическое И; or - логическое ИЛИ;

xor - исключительное ИЛИ.

Эти операции применимы только к значениям типа boolean. Их результатом также служат величины типа boolean. В таблице приведены результаты выполнения операций. (1 – соответствует true, 2 – false).

Операнд 1	Операнд 2	not	and	or	xor
1	-	0	-	-	-
0	-	1	-	-	-
0	0	-	0	0	0
0	1	-	0	1	1
1	0	-	0	1	1
1	1	-	1	1	0

Стандартные арифметические операции

	Описание		Тип аргумента	Тип результата
abs(x)	Абсолютное значение (модуль) числа		Арифметический	Совпадает с типом
				аргумента
arctan(x)	Арктангенс (в радианах)		Арифметический	Вещественный
cos(x)	Косинус (в радианах)		Арифметический	Вещественный
exp(x)	Экспонента (ex)		Арифметический	Вещественный
frac(x)	Взятие дробной части числа		Арифметический	Вещественный
		111

int(x)	Взятие целой части числа	Арифметический	Вещественный
ln(x)	Натуральный логарифм (по	Арифметический	Вещественный
	основанию e)
odd(x)	Проверка нечетности числа	Целый	boolean
pi	Значение числа π	-	Вещественный
round(x)	Округление к ближайшему целому	Арифметический	Целый
trunc(x)	Округление "вниз" - к ближайшему	Арифметический	Целый
	меньшему целому
sin(x)	Синус (в радианах)	Арифметический	Вещественный
sqr(x)	Возведение в квадрат	Арифметический	Вещественный
sqrt(x)	Извлечение квадратного корня	Арифметический	Вещественный

Основные команды. Условный оператор if

Оператор if выбирает между двумя вариантами развития событий: if <условие>

then <один_оператор> [else <один_оператор>];

Оператор else не является обязательным.

Основные команды. Оператор цикла

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

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

В pascal циклом с параметром является цикл «for-to», общий вид которого следующий:

for i:= first to last do <оператор>;

i – счетчик, first – начальное значение, last – последнее значение. Если в цикле необходимо выполнить несколько операторов, то их необходимо заключить в операторные скобки begin… end.

Отметим, что структура циклов с параметром в других языках программирования аналогична циклу «for-to».

Цикл for-to работает следующим образом:

1.определяется значение верхней границы last (оно может быть задано числом или математическим выражением);

2.переменной i присваивается значение нижней границы first;

3.производится проверка условия i<=last для инкрементного цикла

иi>=last для декриментного;

112

4.если результат проверки верен, то есть результат логического выражения true, то выполняется <оператор>, если false, то выполнение цикла не происходит и программа переходит к выполнению следующего за циклом оператора;

5.значение переменной i увеличивается на единицу в случае инкрементного цикла и уменьшается на 1 в случае декрементного (в некоторых языках возможно задания шага);

6.пункты 3-5, составляющие одну итерацию цикла, выполняются до тех пор, пока результат проверки условия i<=last (i>=last) не даст значение false. Как только это произошло, выполнение цикла прекращается, и происходит выполнение следующего за ним оператора.

Синтаксис декрементного цикла с параметром следующий: for i:= first to last downto <оператор>.

Еще один цикл с предусловием: «while», однако данный цикл не является циклом с параметром. Его синтаксис следующий:

while <условие_1> do <оператор>.

Для выполнения нескольких операторов в теле цикла их необходимо заключить в операторные скобки begin...end.

Алгоритм выполнения:

1.проверяется условие, если оно принимает истинное значение, то приступаем к выполнению тела цикла если ложно, то переходим к выполнению следующего за циклом оператора;

2.выполнение <оператор>;

3.пункты 1 и 2 выполняются до тех пор, пока <условие_1> не станет

ложным.

Цикл с постусловием «repeat» задается следующим образом: repeat <операторы> until <условие_2>;

Данный оператор не требует операторных скобок, в случае выполнения нескольких операций внутри тела цикла.

Алгоритм выполнения:

1.выполнение <оператор>;

2.проверяется истинность <условие_1>, если да, то начинается очередное выполнение тела цикла, в противном случае программа переходит

квыполнению следующего за циклом оператора;

3.Пункты 1 и 2 выполняются до тех пор, пока <условие_2> не станет истинным.

Замечание: для прекращения выполнения цикла служат операторы:

−break прерывает работу всего цикла и начинает выполнение следующего за ним оператора;

−continue прерывает работу текущей итерации цикла и начинает выполнение следующей итерации.

113

Процедуры и функции

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

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

Подпрограммы объявляются и описываются в начале программы, до ключевого слова begin, означающего начало тела программы.

Функции объявляются следующим образом:

function <имя_функции> [(<список_параметров>)]:<тип_результата>. То есть после выполнения функции <имени функции> присваивается

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

c:= min(a,a*2);

if min(z, min(x,y))= 0 then...;

Процедуры следует объявлять так:

procedure <имя_процедуры> [(<список_параметров>)];

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

При вызове процедуры в подпрограмму передаются фактические параметры или аргументы:

<имя_подпрограммы>(<список передаваемых_аргументов>); При этом количество передаваемых переменных должно

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

включающие в себя вызовы функций.

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

<имя_программы>.<имя_глобальной переменной>.

Лабораторный практикум «Программирование на языке Turbo Pascal»

Лабораторная работа «Работа с массивами»

Цели работы:

−познакомиться с основными элементами программы на языке Pascal;

−получить практические навыки работы с массивами;

114

−развить учебно-познавательную компетентность: быть способным самостоятельно планировать свою деятельность, обладать способностью самостоятельно применять полученные знания на практике, обладать способностью к самообразованию, участвовать в проектно-исследовательской деятельности;

−формировать информационную компетенцию, позволяющую учащемуся рационализировать интеллектуальную деятельность за счет

использования новых информационных технологий и средств. Технические средства: ПЭВМ с установленной операционной системой

Windows.

Программные средства: Turbo Pascal.

Практическая часть

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

Решение.

1)Сначала рекомендуется (прежде всего, для себя) написать алгоритм на русском языке (или на псевдокоде – это нечто среднее между словесным алгоритмом и готовой программой). Для этого рассмотрим ключевые этапы решения задачи.

2)По условию нужно выделить в памяти два массива одинакового размера, назовем их A и B; обозначим размер массивов через N, индексы элементов изменяются от 1 до N. Так как язык Turbo Pascal является строго типизированным, то все необходимые переменные описываются в разделе

«var».

3)В цикле в каждый элемент B[i] массива B нужно записать модуль соответствующего элемента A[i] массива A, это нужно сделать для всех i от 1 до N.

4)По условию запрещено использовать стандартную функцию вычисления модуля; согласно определению модуля решение может быть такое: если элемент A[i] больше или равен нулю, записываем в B[i] его значение без изменений, а если меньше нуля – меняем знак, то есть, в B[i] записываем (-A[i]).

5)Решение в виде алгоритма на русском языке может выглядеть так: «Выделяем в памяти второй массив того же размера. В цикле рассматриваем все элементы первого массива с первого до последнего. Если текущий элемент больше нуля или равен нулю, в соответствующий элемент второго массива записываем его значение без изменений; если текущий элемент меньше нуля, во второй массив записываем значение элемента с обратным знаком. Выводим второй массив на экран».

6)Теперь запишем описанный алгоритм в виде программы:

115

const N = 30;

{Объявление размерности массива в разделе констант. Такой подход удобен в случае, когда может возникнуть необходимость использовать программу для массива другой размерности.}

var a, b:array[1..N] of integer; i: integer;

begin

for i:=1 to N do { ввод всех элементов массива с клавиатуры } read(a[i]);

for i:=1 to N do { формирование массива B } if a[i] < 0 then

b[i]:= -a[i] else b[i]:= a[i];

writeln('Результат:');

for i:=1 to N do { вывод всех элементов массива B } write(b[i], ' ');

end.

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

Решение:

1) Сначала опишем алгоритм решения поставленной задачи: «Чтобы накапливать сумму, нужно ввести целую переменную Sum, в которую в самом начале записываем 0; далее в цикле просматриваем все строки, для каждой строки находим максимальный элемент и прибавляем его значение к Sum. Для определения максимального элемента в строке вводим переменную max и сначала записываем в нее значение первого элемента этой строки. Затем в цикле просматриваем все остальные элементы, начиная со второго до конца массива. Если очередной элемент больше значения max, записываем в max значение этого элемента».

2) Программная реализация алгоритма. const N=10;

var A: array[1..N,1..N] of integer; i, k, max, Sum: integer;

begin

{ ввод матрицы N на N } Sum := 0;

for i:=1 to N do begin max := A[i,1];

for k:=2 to N do

if A[i,k] > max then max := A[i,k];

116

Sum := Sum + max; end;

writeln(Sum);

end.

Лабораторная работа «Работа с записями».

Цели работы:

−познакомиться с основными элементами программы на языке Pascal;

−получить практические навыки работы с записями.

Технические средства: ПЭВМ с установленной операционной системой

Windows.

Программные средства: Pascal.

Теоретические сведения.

−Символьная строка – это цепочка символов, которая может обрабатываться как единое целое, или поэлементно, как массив символов.

−Для обращения к символу с номером i строки s используется запись s[i].

−Функция Ord возвращает код символа; цифры имеют коды от 48 (цифра

0) до 57 (цифра 9), например k := Ord('1'); { получили 49 }

−с помощью функции Chr можно получить символ по его коду, например

c := Chr(49); { получили символ '1' }

−полезно знать функции и процедуры:

n := Length(s);	записать длину строки s в целую переменную n
s1 := Copy(s, 2, 5);	записать в символьную строку s1 подстроку строки s,
	которая начинается с символа с номером 2 и состоит из 5
	символов
n := Pos('курсант', s);	записать в целую переменную n номер символа, с
	которого в строке s начинается подстрока 'курсант' (если
	ее нет, в переменную n записывается 0);
n := StrToInt(s);	преобразовать строку s в целое число и записать
	результат в переменную n (PascalABC, Delphi)
Delete(s, 2, 5);	удалить из строки s 5 символов, начиная со второго
Insert('курсант', s, 3);	вставить в строку s фрагмент 'курсант', начиная с
	третьего символа (между 3-м и 4-м)
Val(s, n, r);	преобразовать строку s в целое число и записать
	результат в переменную n; если при этом произошла
	ошибка, в переменной r будет ноль, если все нормально

–ненулевое значение

−записи в Паскале объявляются с помощью ключевого слова record; в простейшем случае можно выделить память под одну запись так:

var x: record

•name: string;

117

•code: integer;

•end;

эта запись состоит из двух полей: символьной строки name

ицелого числа code

−для обращения к полям записи используют точку, например x.name означает «поле name записи x»

−можно сразу объявить массив записей:

var Info: array[1..100] of record

•name: string;

•code: integer;

•end;

это 100 одинаковых записей, имеющих общее имя Info и расположенных в памяти рядом; в каждой структуре есть поля nаme и code; чтобы работать с полями записи с номером k используют обращения вида Info[k].name и Info[k].code

Практическая часть

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

<Фамилия> <Инициалы> <номер школы> где <Фамилия> – строка, состоящая не более чем из 20 символов,

<Инициалы> – строка, состоящая из 4-х символов (буква, точка, буква, точка), <номер школы> – не более чем двузначный номер. <Фамилия> и <Инициалы>, а также <Инициалы> и <номер школы> разделены одним пробелом. Пример входной строки: Иванов П.С. 57

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

N>=1000.

Решение:

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

Так как номер школы состоит не более, чем из двух цифр, всего может быть не более 99 школ (с номерами от 1 до 99). Поэтому можно ввести массив C из 99 элементов; для всех k от 1 до 99 элемент C[k] будет ячейкойсчетчиком, в которой накапливается число участников от школы с номером k.

118

2) основной цикл обработки вводимых строк можно записать на псевдокоде так:

for i:=1 to N do begin

{читаем очередную строку }

{определяем номер школы k }

C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы } end;

3)Поскольку данные вводятся в виде символьной строки, нужно выделить в памяти переменную s типа string. Для чтения очередной строки будем использовать оператор readln.

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

5)Чтобы найти первый пробел и «отрезать» первую часть строки с этим пробелом, можно использовать команды:

p := Pos(' ', s);

s := Copy(s, p+1, Length(s)-p);

первая команда определяет номер первого пробела и записывает его в целую переменную p, в вторая – записывает в строку s весь «хвост», стоящий за этим пробелом, начиная с символа с номером p+1; длина хвоста равна

Length(s)-p, где Length(s) – длина строки.

6)Поскольку нас интересует часть после второго пробела, эти две строчки нужно повторить два раза, в результате в переменной s окажется символьная запись номера школы, для преобразования ее в форму числа можно использовать функцию Val:

Val(s, k, r) - эта процедура преобразует символьную строку s в числовое значение k; с помощью переменной r обнаруживается ошибка: если раскодировать число не удалось (в строке не число), в r будет записан нуль (здесь мы не будем обрабатывать эту ошибку, полагая, что все данные правильные), так же можно использовать аналогичную функцию StrToInt.

k := StrToInt(s);

7)таким образом, основной цикл выглядит так:

for i:=1 to N do begin

readln(s); { читаем очередную строку }

{выделяем часть после второго пробела } p := Pos(' ', s);

s := Copy(s, p+1, Length(s)-p); p := Pos(' ', s);

s := Copy(s, p+1, Length(s)-p);

{определяем номер школы k }

Val(s, k, r);

C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы } end;

119

8)заметим, что можно избежать дублирования двух строк в теле цикла, «свернув» их во внутренний цикл:

for k:=1 to 2 do begin p := Pos(' ', s);

s := Copy(s, p+1, Length(s)-p); end;

9)дальше стандартным алгоритмом определяем в массиве C минимальный элемент Min, не учитывая нули (школы, из которых не было участников):

Min := N;

for k:=1 to 99 do

if (C[k] <> 0) and (C[k]<Min) then Min := C[k];

здесь интересна первая строчка, Min:=N: по условию всего было N участников, поэтому минимальное значение не может быть больше N; обратите внимание, что привычный вариант (который начинается с Min:=C[1]) работает неверно, если из первой школы не было ни одного участника

10)и выводим на экран номера всех школ, для которых C[k]=Min: for k:=1 to 99 do

if C[k] = Min then writeln(k);

11)остается «собрать» программу, чтобы получилось полное решение; максимальное количество школ мы задали в виде константы LIM:

const LIM = 99;

var C:array[1..LIM] of integer; i, p, N, k, r, Min: integer; s:string;

begin readln(N);

for i:=1 to N do begin

readln(s); { читаем очередную строку }

{выделяем часть после второго пробела } p := Pos(' ', s);

s := Copy(s, p+1, Length(s)-p); p := Pos(' ', s);

s := Copy(s, p+1, Length(s)-p);

{определяем номер школы k }

Val(s, k, r);

C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы } end;

Min := N;

for k:=1 to LIM do

if (C[k] <> 0) and (C[k]<Min) then Min := C[k]; for k:=1 to LIM do

if C[k] = Min then writeln(k); end.

120