Семакин И.Г., Шестаков А.П. Основы программирования

Подождите немного. Документ загружается.

Type Vec=Array [1..N] Of

Real;

Var T,Dt: Vec;

St:

Real;

I: Integer;

Begin {Ввод исходных данных}

WriteLn('Вводите таблицу

температур');

For I:=l To N Do

Begin

Write

(I:

' : ')

;

ReadLn(T[I])

End;

{Вычисление средней температуры}

St:=0;

For I:=l To N Do

St:=St+T[I];

St:=St/N;

{Вычисление таблицы отклонений от среднего}

For I:=l To N Do

Dt[I]:=T[I]-St;

{Вывод результатов}

WriteLn('Средняя температура

равна',St:6:2);

WriteLn;

WriteLn('Отклонения от средней

температуры:');

For I:=l To N Do

WriteLn

(1:1,

':',Dt[I] :б:2)

End.

По этой программе можно рассчитать среднее значение и век-

тор отклонений от среднего для любого одномерного веществен-

ного массива. Настройка на размер массива осуществляется толь-

ко редактированием раздела констант.

Пример 2.

Выбор

максимального элемента. Пусть из рассмотрен-

ного выше массива температур требуется отобрать самую высокую

температуру и номер месяца, ей соответствующего. Идея алгорит-

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

ратуру в вещественной переменной тмах, сначала в нее зано-

сится первое значение массива т

[ 1

Затем поочередно сравни-

вается значение тмах с остальными элементами массива

температур, и каждое значение большее, чем тмах, присваива-

ется этой переменной. Для получения номера самого теплого ме-

сяца в целой переменной NumMax в нее следует каждый раз засы-

лать номер элемента массива температур одновременно с занесе-

нием в тмах его значения.

ТМах:=Т[1];

NumMax:=1;

ПО

For I:=2 To 12 Do

If T[I]>Tmax

Then

Begin

TMax:=T[I];

NumMax:=I

End;

Заметим, что если в массиве температур несколько значений,

равных максимальному, то в

NumMax

будет получен первый номер

из этих элементов. Чтобы получить последнюю

дату,

нужно в опе-

раторе if заменить знак отношения > на >=.

Пример 3. Сортировка массива. В одномерном массиве X из N

элементов требуется произвести перестановку значений так, что-

бы они расположились по возрастанию, т.е.

{

< Х

... <X

Существует целый класс алгоритмов сортировки. Ниже описан

алгоритм, который называется «метод пузырька».

Идея: производится последовательное упорядочивание смеж-

ных пар элементов массива: Х

и Х

...,

В итоге

максимальное значение переместится в

Затем ту же процедуру

повторяют до X

^ и т.д., вплоть

до

цепочки из двух элементов

Такой алгоритм будет иметь структуру

двух

вложенных циклов с

внутренним циклом

—

переменной (сокращающейся) длины.

For I:=l To N-l Do

For K:=l To N-I Do

If Х[К]>Х [K+l]

Then

Begin

А:=Х[К];

Х[К]:=Х[К+1];

Х[К+1]:=А

End;

Пример 4. Дан описанный выше двумерный массив среднеме-

сячных температур за

лет.

Определить, в каком году было самое

теплое лето, т.е. в каком году была наибольшая средняя темпера-

тура летних месяцев.

Идея решения: в векторе

получить средние температуры лет-

них месяцев за

лет.

Затем найти номер наибольшего элемента в

этом векторе, это и будет искомый год.

Program Example_2;

Type Month=Array[l..12] Of

Real;

Year=Array[1981..1990] Of Month;

Var H: Year;

S: Array[1981..1990] Of

Real;

I,J,K:

Integer;

111

Begin {Ввод данных с клавиатуры)

For

I:=1981

To 1990 Do

For J:=l To 12 Do

Begin

Write(J:2,

•

.',1:4,

' :

');

ReadLn(H[I,J])

End;

{Вычисление вектора средних летних

температур)

For

I:=1981

To 1990 Do

Begin

S[I]:=0;

For J:=6 To 8 Do

S[I]

:=S[I]+H[I,

J];

S[I]:=S[I]/3

End;

{Определение года с самым теплым летом)

К:=1981;

For

I:=1982

То 1990 Do

If S[I]>S[K] Then K:=I;

WriteLn('Самое теплое лето было в',

К, '-м году')

End.

Упражнения

Дан вектор

{z,},

/ = 1,..., 50. Вычислить длину этого вектора:

L =

^Z\+Z2+-

zh •

Вычислить полином 10-й степени по формуле Горнера:

...

+ а

{

((...(а

)х

а%)х

+ ... + a

)x + а

Для вектора

{х,},

=1,...,

20, подсчитать количество компо-

нент, значения которых лежат в интервале

[0,1].

Даны два вектора {х,}, {у,}, i = 1,..., 10, упорядоченные по

возрастанию. Слить их в один вектор

{z,),

/= 1,..., 20, так чтобы

сохранилась упорядоченность.

Дан массив, состоящий из 100 целых

чисел.

Вывести все чис-

ла, которые встречаются в этом массиве:

а) несколько раз;

б) только по одному разу.

целочисленной матрице размером 10x10 найти значение и

индексы максимального элемента.

В двоичной матрице 5x10 определить номер строки с наи-

большим количеством нулей.

112

8. Все строки вещественной матрицы 1 Ох

упорядочить по убы-

ванию значений их элементов.

9. Транспонировать целочисленную матрицу 5x5, т.е. отразить

относительно главной диагонали.

10.

двоичной матрице 10х

найти совпадающие строки.

3.18. Понятие множества. Множественный тип данных

Одним из фундаментальных разделов математики является те-

ория множеств. Некоторые моменты математического аппарата этой

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

(множества).

Множеством называется совокупность однотипных элементов,

рассматриваемых как единое целое. В Паскале могут быть только

конечные множества. В Турбо Паскале множество может содер-

жать от 0 до 255 элементов.

В отличие от элементов массива элементы множества не прону-

мерованы, не упорядочены. Каждый отдельный элемент множества

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

ствия. Действия могут выполняться только над множеством в целом.

Тип элементов множества называется базовым типом. Базовый

тип может быть любым скалярным, за исключением типа Real.

Конструктор множества. Конкретные значения множества зада-

ются с помощью конструктора множества, представляющего со-

бой список элементов, заключенный в квадратные скобки. Сами

элементы могут быть либо константами, либо выражениями базо-

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

конструктора:

[3,4,7,9,12] — множество из пяти целых чисел;

[1..

100] — множество целых чисел от

до 100;

[' а', 'Ъ', ' с'

] —

множество, содержащее три литеры a, b, с;

['А'. . '

', '?','!'] — множество, содержащее все пропис-

ные латинские буквы, а также знаки ? и !.

Символы [] обозначают пустое множество, т.е. множество, не

содержащее никаких элементов.

Не имеет значения порядок записи элементов множества внут-

ри конструктора. Например, [1,2,3] и [3,2,1]эквивалентные

множества.

Каждый элемент в множестве учитывается только один раз.

Поэтому множество [1,2,3,4,2,3,4,5] эквивалентно

[

1. . 5].

Переменные множественного типа описываются так:

Var <идентификатор>: Set Of <базовый тип>

Например:

Var A,D: Set Of Byte;

ИЗ

В:

Set Of 'a'..'z';

C: Set Of Boolean;

Нельзя вводить значения во множественную переменную опе-

ратором ввода и выводить оператором вывода. Множественная пе-

ременная может получить конкретное значение только в результате

выполнения оператора присваивания следующего формата:

Множественная переменная>:=<множественное выражение>

Например:

А:=[50,100,150,200];

В:

= [' m' , ' п ' , ' к' ] ;

C:=[True,False];

D:=A;

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

множествами.

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

операции теории множеств. Это

объединение,

пересечение,

разность

множеств. Во всех таких операциях операнды и результаты есть

множественные величины одинакового базового типа.

Объединение

множеств.

Объединением двух множеств Ан В на-

зывается множество, состоящее из всех элементов, принадлежа-

щих хотя бы одному из множеств А или В. Знак операции объеди-

нения в Паскале +.

На рис. 34, а схематически показан результат объединения двух

множеств.

Например:

[1,2,3,4] + [3,4,5,б]-> [1,2, 3,4, 5, б]

Пересечение

множеств.

Пересечением двух множеств А и В на-

зывается множество, состоящее из всех элементов принадлежа-

щих, одновременно множеству А и множеству В (см. рис. 34, б)

Знак операции пересечения в Паскале *.

Например:

[1,2,3,4]*[3,4,5,6]->[3,4]

Разность

множеств.

Разностью двух множеств А и В называется

множество, состоящее из элементов множества А, не принадле-

жащих множеству В (см. рис. 34, в).

Например:

[1,2,3,4]-[3,4,5,6]-»[1,2]

[3,4,5,6]-[1,2,3,4]-»[5,6]

Очевидно, что операции объединения и пересечения — пере-

становочны, а разность множеств

—

не перестановочная операция.

Операции

отношения.

Множества можно сравнивать между со-

бой, т.е. для них определены операции отношения. Результатом

114

А+ В

А * В

А-

Рис.

отношения, как известно, является логическая величина true или

false. Для множеств применимы все операции отношения, за ис-

ключением > и <. В таблице описаны операции отношения над

множествами. Предполагается, что множества А и В содержат эле-

менты одного типа.

Отношение

А = В

АО В

А<= В

А>= В

Результат

True

Множества А и В совпадают

Множества А и Вне совпадают

Все элементы А принадлежат В

Все элементы В принадлежат А

False

В противном случае

Вот несколько примеров использования операций отношения.

Пусть переменная м описана в программе следующим образом:

Var M: Set Of Byte;

В разделе операторов ей присваивается значение:

М:=[3,4,7,9];

Тогда операции отношения дадут следующие результаты:

М=[4,7,3,3,9] - true,

M<>[7,4,3,9]

[3,4]<=М

[]<=М

М>=[1..10]

М<=[3..9]

false,

true,

false,

true.

Операция

вхождения.

Это операция, устанавливающая связь меж-

ду множеством и скалярной величиной, тип которой совпадает с

базовым типом множества. Если х

—

такая скалярная величина,

а м — множество, то операция вхождения записывается так:

х in м

115

Результат — логическая величина true, если значение х вхо-

дит в множество м, и false

—

в противном случае. Для описанно-

го выше множества

4 In M — true,

5 In M — false.

Рассмотрим несколько задач, для решения которых удобно

использовать множества.

Пример 1. Дана символьная строка. Подсчитать в ней количе-

ство знаков препинания (.-,;:!*?).

Program PI;

Var S: String; I,K: Byte;

Begin

ReadLn(S); K:=0;

For I:=l To Length(S) Do

If S[I] In ['.', •-', ', ', ';', ':','!', '*','?•]

Then K:=K+1;

WriteLn('Число знаков препинания равно',К)

End.

В этом примере использована множественная константа с сим-

вольным типом элементов. Эту задачу можно решить и без множе-

ства, записав в операторе if длинное логическое выражение:

[

. ') Or (S[i]

'-') и т.д. Использование множества

сокращает запись.

Пример 2. Даны две символьные строки, содержащие только

строчные латинские буквы. Построить строку S3, в которую вой-

дут только общие символы si и S2 в алфавитном порядке и без

повторений.

Program P2;

Type Mset=Set Of

'a'..'z';

Var S1,S2,S3: String;

MS1,MS2,MS3:

Mset;

C: Char;

Procedure SM(S: String; Var MS:

Mset);

(Процедура формирует множество MS, содержащее все

символы строки S}

Var I: Byte;

Begin

MS:=[];

For I:=l To Length(S) Do

MS:=MS+[S[I]]

End;

Begin {Ввод исходных строк}

ReadLn(Sl);ReadLn(S2) ;

{Формирование множеств MSI и MS2 из символов строк

S1 и S2}

SM(S1,MS1);SM(S2,MS2);

116

{Пересечение множеств - выделение общих элементов в

множество MS3}

MS3:=MS1*MS2;

{Формирование результирующей строки S3}

S3:='';

For С:='а' То 'z' Do

If С In MS3 Then S3:=S3+C;

WriteLn('Результат:',S3)

End.

Пример З. Составить программу, по которой из последователь-

ности натуральных чисел от 2 до N

< /V<255) будут выбраны

все простые числа.

Для решения задач такого типа существует алгоритм, извест-

ный под названием «Решето Эратосфена». Суть его в следующем:

Из числовой последовательности выбираем минимальное

значение, это будет простое число.

Удаляем из последовательности все числа, кратные выб-

ранному.

Если после удаления последовательность не стала пустой, то

возвращаемся к выполнению пункта 1.

Вот пример работы такого алгоритма для N=

(подчеркнуты

выбранные простые числа):

3 4 5 б 7 8 9 10 11 12 13 14 15

3 5 7 9 11 13 15

5 7 11 13

I 11 13

II 13

Решение этой задачи удобно программировать, используя мно-

жественный тип.

Program Eratosfen;

Const

N=201;

{Возможно любое значение 1<N<256}

Var А,В: Set Of 2..N;

К,Р: Integer;

Begin

{Формирование исходного множества А;

В - искомое множество простых чисел,

сначала - пустое}

A:=[2..N];

B:=[];

Р:=2;

Repeat

{Поиск минимального числа в множестве А}

While Not(P In A) Do Р:=Р+1;

{Включение найденного числа в множество В}

117

В:=В+[Р];

К:=Р;

{Исключение из А чисел, кратных Р}

While K<=N Do

Begin

A:=A-[K];

K:=K+P;

End

Until A=[];

{Вывод результата, т.е. всех чисел из множества В в

порядке возрастания}

For Р:=2 То N Do If P In В Then WriteLn(P)

End.

Красивая программа! К сожалению, ею нельзя воспользовать-

ся для

./V

> 255 из-за отмеченного выше ограничения на макси-

мальный размер множества в Турбо Паскале.

Пример 4. Как уже говорилось, нельзя вводить значения непос-

редственно в множество. Однако такая потребность у программи-

ста может возникнуть.

этом случае можно прибегнуть к процеду-

ре INSET, описанной ниже. Для примера рассматривается мно-

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

основной программе глобально объявлен тип SetChar.

Type SetChar: Set Of Char;

Procedure INSET(Var M:

SetChar);

Var I,N: Byte; C: Char;

Begin

Write('Укажите размер множества:'); ReadLn(N);

M:=[];

For I:=l To N Do

Begin

Write(I:1, '-й

элемент:');

ReadLn

(С);

M:=M+[C]

End;

WriteLn('Ввод завершен!')

End.

В основной программе для ввода значений в множество, на-

пример с именем

SIM,

достаточно записать оператор: INSET (SIM);

Произойдет диалоговый ввод значений.

Упражнения

программе присутствуют описания:

Var P: Set Of 0..9; I,J: Integer;

118

Если

3 и у

то какое значение получит переменная Рпри

выполнении следующих операторов присваивания:

а) Р

б) р

в) Р

=[1+3,J Div 2,J..Sqr(I)-3];

=[2*I..J];

=[I,J,2*I,2*J]?

Г) [1..6] + [3.

[i..6]-[3.

з)

[]*[4];

.8];

Вычислить значения отношений:

a) [2] о [2, 2, 2]; 6)['a','b'] = ['b','a'];

в) [4, 5, 6] = [4, 5, 6]; г) ['с', •ЬЧ = [

с'..'Ь'];

Д)[2,3,5,7]<=[1..9]; е)[3,б..8]<=[2..7,9];

ж)Тгипс(З.Э) In[l,3,5]; 3)Odd(4) In[].

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

а) [1,3,5] +

[2,4];

б) [1,3,5]*[2,4];

В) [1,3,5]-[2,4];

Д) [1..6]*[3..8];

Ж) [] + [4];

и)

[]-[4].

Составить программу подсчета количества различных знача-

щих цифр в десятичной записи натурального числа.

Составить программу, печатающую в возрастающем порядке

все целые числа из диапазона

...255,

представимые в виде

где п, т

Дана строка из строчных русских

букв.

Между соседними сло-

вами

—

запятая, за последним словом

—

точка. Напечатать

алфа-

витном порядке:

а) все гласные буквы, которые входят в каждое слово;

б) все согласные буквы, которые не входят ни в одно слово;

в) все согласные буквы, которые входят только в одно слово;

г) все гласные буквы, которые входят более чем в одно слово.

3.19. Файлы. Файловые переменные

С термином «файл» вам уже приходилось встречаться. Прежде

всего это понятие обычно связывают с информацией на устрой-

ствах внешней памяти.

Паскале понятие файла употребляется в

двух смыслах:

• как поименованная информация на внешнем устройстве (вне-

шний файл);

• как переменная файлового типа в Паскаль-программе (внут-

ренний файл).

В программе между этими объектами устанавливается связь.

Вследствие этого все, что происходит в процессе выполнения

программы с внутренним файлом, дублируется во внешнем фай-

119