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

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

Глава 6. Перечислимый тип, множества, файлы
a[i]:=a[i]+[s[i][j]];
writeln(a[1]=a[2]);
Пример
Задача. Используя решето Эратосфена, найти простые числа, меньшие 256.
Решето Эратосфена — первый эффективный алгоритм для генерации простых чисел:
1. Выпишем числа 2, 3, 4, 5, 6,. . .
2. Отметим первый элемент в последовательности p как простое число.
3. Удалим из списка все числа, кратные p.
4. Вернемся к шагу 2.
Эти операции дают следующее:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,. . .
— так, что 2 — простое число.
Убираем числа, кратные 2:
3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31,. . .
— так, что 3 — простое число.
Убираем теперь числа, кратные 3:
5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43,. . .
— так, что 5 — простое число.
Теперь удаляем все числа, кратные 5:
7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53,. . .
и т. д.
const n=255;
{n = максимальное количество перебираемых натуральных чисел}
var s, {исходное множество}
primes: set of 2..n; {результирующее множество}
next,j:integer;
begin s:=[2..n]; {все числа в заданном диапазоне}
primes:=[];
next:=2; {начинаем с минимального простого числа}
repeat
{поиск очередного простого числа}
while not (next in s) do next:=next+1; {ищем в s наименьшее число}
primes:=primes+[next]; {помещаем его в primes}
j:=next;
while j<=n do {удаляем из s все числа, кратные next}
begin s:=s-[j]; j:=j+next end;

6.3 Файловые типы и ввод-вывод
117
until s=[]; {повторяем цикл до исчезновения s}
writeln(
'Простые числа < 256:');
for j:=2 to n do if j in Primes then write(j:5)
end
6.3 Файловые типы и ввод-вывод
В языке Паскаль под файлом понимается область памяти на внешнем запо- минающем устройстве, способная хранить некоторую совокупность информации.
В эту область внешней памяти можно как поместить определенные данные, так и извлечь их из нее. Эти действия имеют общее название ввод-вывод.
6.3.1 Файловые переменные и типы
Для организации ввода-вывода могут быть определены специальные перемен-
ные файловых типов, которые считаются представителями файлов в программе.
Использование переменных файловых типов предполагает интерпретацию файла как потенциально бесконечного списка значений одного и того же (базового) типа.
Пример var f:file of integer;
Под именем f определен список неопределенного количества целых чисел,
расположенный на некотором внешнем устройстве (например, магнитном диске).
С каждой переменной файлового типа также связано понятие текущего указате- ля файла. Текущий указатель — скрытая переменная (т. е. неявно описанная вместе с файловой переменной), которая обозначает («указывает») на некоторый кон-
кретный элемент файла.
Как правило, все действия с файлами (чтение из файла, запись в файл) про- изводятся поэлементно, причем в этих действиях участвует тот элемент файла,
который обозначается текущим указателем. В результате совершения операций текущий указатель может перемещаться, настраиваясь на тот или иной элемент файла.
Заметим, что один и тот же внешний файл в различных программах (или да- же в различных частях одной и той же программы) может интерпретироваться по-разному, например как последовательность целых чисел или как последова- тельность некоторых массивов, и т. д.
Синтаксис: <файловый тип> ::= file of <тип>
Тип элементов может быть любой, за исключением файлового.

118
Глава 6. Перечислимый тип, множества, файлы
Пример type sequence=file of char;
var F1,F2:sequence;
inputData:file of real;
6.3.2 Установочные и завершающие операции над файлами
При работе с файлами перед и после операций ввода-вывода необходимо вы- полнить стандартные процедуры: assign, reset, rewrite, close.
Процедура assign предназначена для установления связи между конкретным физическим файлом на магнитном носителе и переменной файлового типа, кото- рая будет являться представителем этого файла в программе. Синтаксис вызова процедуры:
assign(<файловая переменная>,<строковое выражение>);
Значение второго параметра — литеральное имя файла. Имя файла строится по правилам, принятым в операционной системе для именования файлов.
Пример assign(f,
'd:
/mydir/myfile.dta');
После выполнения данного вызова файловая переменная f будет связана с фай- лом myfile.dta в каталоге mydir диска d.
Процедуры reset и rewrite имеют один параметр — файловую переменную и предназначены для открытия файлов. При этом файловая переменная, указы- ваемая в качестве параметра, должна быть уже связана с конкретным дисковым файлом с помощью процедуры assign.
Открытие файла — поиск файла на внешнем носителе, образование специаль- ных системных буферов для обменов с ним и установка текущего указателя файла на его начало.
Reset используется, когда файл уже существует. Rewrite используется, и ко- гда файл еще не существует, а если существует, то он очищается.
Процедура close имеет один параметр — файловую переменную и завершает действия с файлом — ликвидируются внутренние буфера, образованные при откры- тии этого файла.
После этого файловую переменную можно связать посредством процедуры assign с каким-либо другим дисковым файлом.
Заметим, что при окончании работы всей программы происходит автоматиче- ское закрытие всех файлов, открытых в программе.

6.3 Файловые типы и ввод-вывод
119
6.3.3 Операции ввода-вывода
Процедуры write и read, в отличие от многих других процедур, могут вызы- ваться с различным числом параметров, и эти параметры могут иметь различные
типы.
Процедура read предназначена для чтения значений из файла в программу.
Первым параметром должно быть имя файловой переменной, к которой была при- менена одна из операций открытия (reset или rewrite). Далее должны следо- вать переменные, в которые будут помещаться читаемые из файла значения. Тип этих переменных должен совпадать с базовым типом файла из первого параметра.
Выполнение процедуры read происходит следующим образом. Начиная с те- кущей позиции указателя файла, будут последовательно читаться значения, содер- жащиеся в файле. Каждое прочитанное значение будет присваиваться очередной переменной из тех, которые указаны в вызове процедуры. После каждого акта чтения указатель файла будет смещаться на следующую позицию.
Если указатель файла указывает на «конец файла», то чтение невозможно.
Функция eof(<файловая переменная>) — булевская функция, равна истине,
если имеется ситуация «конец файла».
Процедура write позволяет записывать в файл информацию из программы.
Первым параметром этой процедуры должна быть файловая переменная, открытая процедурой reset или rewrite. Далее должен идти список переменных, тип которых совпадает с базовым типом файла из первого параметра.
Выполнение процедуры write.
Значение очередной переменной будет помещено в файл в место, отмеченное текущим указателем. После этого текущий указатель будет передвинут на одну по- зицию, и действия повторяются для следующей переменной из списка параметров.
6.3.4 Текстовые файлы
Текстовые файлы — файлы, у которых базовый тип есть char.
Представителем текстового файла в программе является переменная файлового типа, которая должна быть описана с указанием стандартного типа text:
var textInf:text;
Структура текстовых файлов отличается от структуры обычных файлов (ли- нейная последовательность элементов одного типа) тем, что содержимое тексто- вого файла рассматривается как последовательность символьных строк перемен-
ной длины, разделенных специальной комбинацией, называемой «конец строки».
Как правило, это комбинация строится из управляющего кода «перевод каретки»
(символ #13), за которым, возможно, следует управляющий код «перевод строки»
(символ #10). Текстовый файл завершается специальным кодом «конец файла» (символ
#26).
Открытие текстового файла для чтения выполняет процедура reset. Открытие текстового файла для записи выполняет процедура rewrite.
Логическая функция eoln(<файловая переменная>) возвращает true,
если текущая строка исчерпана, и false в противном случае.

120
Глава 6. Перечислимый тип, множества, файлы
В процедуре write для текстового файла все параметры, начиная со второго, могут быть не только переменными, но и выражениями следующих типов: integer, real, char, boolean и string.
Текстовый файл по определению содержит символьную информацию, поэтому при записи значения других типов (integer, real) будут преобразовываться в символьное представление и в таком виде записываться в очередную строку текстового файла. Аналогично, при чтении из текстового файла очередная часть текущей строки будет пониматься как символьное представление значения, тип которого определяется типом очередной переменной из процедуры read.
Помимо процедур read и write, для текстовых файлов имеются две их мо- дификации — процедуры readln и writeln. Эти процедуры осуществляют те же действия, что и соответствующие процедуры read и write, но после операций чтения и записи производят переход к следующей строке текстового файла.
С текстовым файлом можно использовать текстовый редактор для создания или изменения файла.
В Паскале имеются две стандартных файловых переменных текстового ти- па — Input и Output. Стандартная файловая переменная Input представляет собой доступный только для чтения файл, связанный со стандартным файлом вво- да операционной системы (клавиатура). Вторая стандартная файловая переменная
Output
— это доступный только для записи файл, связанный со стандартным фай- лом вывода (дисплей). Перед началом выполнения программы эти файлы автома- тически открываются. Имя файла в процедурах read и write не указывается,
если работа ведется со стандартным файлом.
6.3.5 Примеры работы с файлами
Приведем несколько программ, работающих с файлами.
1. Запись в файл квадратов целых чисел.
var f:file of integer;
assign(f,
'. . .');
rewrite(f);
for i:=1 to n do begin k:=i*i; write(f,k); end;
close(f);
2. Компонентами файла f являются массивы a
1
, a
2
, . . . из 10 действитель- ных чисел. Вывести на экран наибольшие элементы всех этих массивов.
type mas = array[1..10] of real;
fmas = file of mas;
var a:mas; f:fmas; r:real; i:integer;

Контрольные вопросы по главе 6
121
begin assign(f,
'. . .'); reset(f);
while not eof(f) do begin read(f,a); r:=a[1];
for i:=2 to 10 do if a[i]>r then r:=a[i];
writeln(r)
end;
close(f)
end.
3. Описать логическую функцию eq(t1,t2), проверяющую текстовые фай- лы t1 и t2 на равенство.
function eq(var t1,t2:text):boolean;
var c1,c2:char; ok:boolean;
begin reset(t1);reset(t2);ok:=true;
while not eof(t1) and not eof(t2) and ok do begin read(t1,c1);read(t2,c2);ok:=c1=c2; end;
eq:=ok and eof(t1) and eof(t2);
end;
4. Программа, которая печатает свой файл с текстом.
var s:string[126];
f:text;
begin assign(f,
'name.pas');
reset(f);
while not eof(f) do begin readln(f,s); write(s) end;
close(f)
end.
Контрольные вопросы по главе 6 1. Имеются описания type season = (winter, spring, summer, autumn);
var x, y: season;
t: (heat, cold);
Ответить на следующие вопросы.
А. Какие значения могут принимать переменные x, y и t? Допустимы ли присваивания:

122
Глава 6. Перечислимый тип, множества, файлы
x := spring;
y := x;
t := heat;
y := t;
t := hot?
Б. Вычислить значения выражений:
spring < summer;
winter <= summer;
autumn < winter;
spring <> heat;
succ(spring);
pred(spring);
succ(autumn);
pred(cold).
В. Вычислить значения выражений:
ord(spring);
ord(autumn) + ord(cold);
Г. Допустимы ли следующие операции ввода-вывода?
read(x);
write(summer);
writelnn
(' if a season is winter then there is ', t).
2. Если в базовом типе n различных значений, то сколько различных значений в построенном на его основе множественном типе?
3. Какие из следующих описаний неверны и почему?
type points = set of real;
data = set of integer;
month = (January, February, March, April, May,
June, July, August, September, October,
November, December);
m1 = set of month;
m2 = set of June .. August;
m3 = December .. February;
m4 = set of (June, July, August);
4. Какие из следующих конструкций являются множествами (в смысле языка
Паскаль), а какие нет, и почему?
[9, 6, 3, 0]; [2..3, 5, 7]; [1..15, 4..18]; [
'*', '*'];
[0..0];
[true..false];
[2, sqrt(9)];
[
'=', '>=', '>'];
[[],[5]]; [odd(7), 0<2]
5. Как для операций ввода-вывода явно обозначается текущий указатель фай- ла в программе?

Рекомендуемая литература к главе 6
123
Рекомендуемая литература к главе 6
[1]
Немнюгин С. А. Turbo Pascal / С. А. Немнюгин. — СПб. : Питер, 2001. —
496 г.
[2]
Фаронов В. В. Турбо Паскаль 7.0: Практика программирования / В. В. Фа- ронов. — М. : Нолидж, 2000. — 416 с.
[3]
Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. — М. :
Мир, 1985. — 405 с.

Глава 7
РЕКУРСИЯ
«. . . на столе появился маленький Витька Корнеев, точная копия настоящего, но величиной с руку. Он щелкнул ма- ленькими пальчиками и создал микродубля еще меньше- го размера. Тот тоже щелкнул пальцами. Появился дубль величиной с авторучку. Потом величиной со спичечный коробок. Потом с наперсток».
А. и Б. Стругацкие «Понедельник начинается в субботу»
7.1 Понятие рекурсии
Объект называетсярекурсивным, если он содержит сам себя или определен с помощью самого себя.
Рекурсия встречается не только в математике, но и в обыденной жизни. Каж- дый сталкивается с рекурсией, когда стоит с зеркальцем перед большим зеркалом.
Рекурсия встречается обычно и в природе: деревья имеют рекурсивное строение
(ветки образуются из других веток), реки образуются из впадающих в них рек.
Клетки делятся рекурсивно. Продолжение жизни связано с рекурсивным процес- сом. Молекулы ДНК и вирусы размножаются, копируя себя, живые существа имеют потомство, которое в свою очередь тоже имеет потомство и т. д. Рекурсия распро- странена и в языке, и в поведении так же, как и в способах рассуждения и познания.
Рекурсия в языке, например, может быть в структуре или в содержании:
«Петя сказал, что Вася сказал, что. . .»
«Знаю, что знаю, но не помню»
«Сделать; заставить сделать; заставить, чтобы заставили сделать;. . .»
«Замени x этим предложением»
«Запомни и передай это сообщение»
. . .

7.1 Понятие рекурсии
125
Литературным примером может служить «рассказ в рассказе», как — то: извест- ное стихотворение «У попа была собака, . . .», роман Яна Потоцкого «Рукопись, най- денная в Сарагосе», рассказ Хулио Кортасара «Непрерывность парков» или рассказ
Виктора Пелевина «Водонапорная башня» (и по форме — состоит из одного пред- ложения и по содержанию). Музыкальные формы и действия также могут быть рекурсивными во многих отношениях (например, канон или фуга, в которых ме- лодия сопровождается той же мелодией с задержкой, и другие). Целенаправленное поведение и решение проблем так же являются рекурсивными процессами.
Рекурсия является особенно мощным средством в математических определени- ях. Известны примеры рекурсивных определений натуральных чисел, древовидных структур и некоторых функций:
Натуральные числа:
1) 1 есть натуральное число;
2) целое число, следующее за натуральным, есть натуральное число.
Древовидные структуры (с ними познакомимся попозже):
1) атомарный объект есть дерево;
2) если t
1
и t
2
— деревья, то есть дерево (нарисованное сверху вниз).
Функция факториал n! для неотрицательных целых чисел:
1) 0!=1;
2) если n>0, то n!=n (n
− 1)!.
Очевидно, что мощность рекурсии связана с тем, что она позволяет определить бесконечное множество объектов с помощью конечного высказывания.
Рекурсия в программировании — один из важнейших принципов построения подпрограмм. Если процедура P содержит явное обращение к самой себе, то она называется прямо рекурсивной; если P содержит обращение к процедуре Q, ко- торая содержит (прямо или косвенно) обращение к P, то P называется косвенно
рекурсивной. Поэтому использование рекурсии не всегда сразу видно из текста программы.
Идею косвенной рекурсии хорошо иллюстрирует гравюра художника Мориса
Эшера, на которой изображены две руки, взаимно рисующие друг друга (рис. 7.1).
С процедурой принято связывать некоторое множество локальных объектов,
т. е. переменных, констант, типов и процедур, которые определены локально в этой процедуре, а вне ее не существуют или не имеют смысла. Каждый раз, когда такая процедура рекурсивно вызывается, для нее создается новое множество локальных переменных. Хотя они имеют те же имена, что и соответствующие элементы мно- жества локальных переменных, созданного при предыдущем обращении к этой же процедуре, их значения различны.

126
Глава 7. Рекурсия
Рис. 7.1 – Рисующие руки
Следующие правила области действия идентификаторов позво- ляют исключить какой-либо конфликт при использовании имен:
идентификаторы всегда ссылаются на множество переменных,
созданное последним. То же правило относится к параметрам про- цедуры.
Подобно операторам цикла, рекурсивные процедуры могут приводить к беско- нечным вычислениям. Поэтому для того, чтобы работа процедуры когда-либо за- вершилась, необходимо, чтобы рекурсивное обращение к процедуре подчинялось некоторому логическому условию, которое в какой-то момент перестает выпол- няться.
Для начала приведем два элементарных примера прямой рекурсии.
Пример 1. Подпрограмма для вычисления факториала неотрицательного числа:
function fac(n:integern>=0):integer;
begin if n=0 then fac:=1
else fac:=n*fac(n
−1)
end
Отметим сразу же, что рекурсивную функцию можно заменить рекурсивной процедурой. Для данного случая определим процедуру:
procedure f(var y:integer;n:integer);
var x:integer;
begin if n=0 then y:=1
else begin f(x,n
−1);y:=n*x end end
Первый параметр в процедуре f в результате работы получает значение равное n!.
Пример 2. Подпрограмма для вычисления наибольшего общего делителя двух положительных целых чисел:

7.1 Понятие рекурсии
127
function gcd(m,n:integer);integer;
begin if m=n then gdc:=m else if m−m,m)
else gdc:=gdc(m
−n,n)
end
Косвенная рекурсия может быть задана в системе подпрограмм, которые опре- деляются «бок о бок» и взаимно опираются друг на друга.
Пример 3. Пара подпрограмм (iseve n, isodd) для определения того, четно или нечетно данное натуральное число n.
function iseven(n:integer):boolean;
{is iven — быть четным}
begin if n=1 then iseven:=false else iseven:=isodd(n
−1)
end;
function isodd(n:integer):boolean;
{is odd — быть нечетным}
begin if n=1 then isodd:=true else isodd:=iseven(n
−1)
end;
Подставляя, скажем, isodd в iseven, можно получить непосредственную рекурсию для iseven:
function iseven(n:integer):boolean;
begin if n=1 then iseven:=false else if n=2 then iseven:=true else iseven:=iseven(n
−2)
end;
Пример 4. Примером иерархической рекурсивной системы подпрограмм мо- жет служить пара (gcd1, moda), где moda — подпрограмма, заменяющая операцию mod
(с положительным делителем), а gcd1 — подпрограмма для вычисления наи- большего общего делителя двух неотрицательных целых чисел:
function moda(m,n:integer):integer;
{m>=0 и n>0}
begin if m−n,n)
end;
function gcd1(m,n:integer):integer;
{m,n >=0}
begin if n=0 then gcd1:=m else gcd1:=gdc1(n,moda(m,n))
end;
Простое исключение moda, с тем чтобы, скажем, получить gcd из примера 2,
здесь уже невозможно.

128