Конспект лекций по информатике для специальностей 2102, 2103 Автор доц., к т. н. Каширская Е. Н

Вид материала

Содержание

5.6. Побочный эффект рекурсии
5.7. Предварительное описание (ссылки вперед)
6. РЕГУЛЯРНЫЕ ТИПЫ 6.1. Одномерный массив, или переменные с индексами
Z[i]:= x[i]*y[i]
Алгоритмы сортировки массивов
1. Метод пузырька (метод обменной сортировки с выбором)
2. Сортировка выбором
3. Метод Шелла

Подобный материал:

1 ... 10 11 12 13 14 15 16 17 ... 25

5.6. Побочный эффект рекурсии

В теле подпрограммы известны, то есть доступны все объекты, описанные в объемлющем блоке, в том числе и имя самой подпрограммы. Внутри тела подпрограммы возможен вызов самой подпрограммы. Параметры и функции использующие вызовы “самих себя“, называются рекурсивными. Допустима также косвенная рекурсия, при которой параметр А вызывает параметр В, а тот, в свою очередь, вызывает С, который вызывает первоначальный параметр А.

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

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

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

Пример:

Program Side Effect;

Var a,z :integer;

Function change (x: integer): integer;

Begin

Z:=z-x; {изменяем значение нелокальной переменной}

Change:= sqr (x)

End;

Begin

Z:=10; a:=change (z); writeln(a,z);

Z:=10; a:=change (10)*change (z);

Writeln(a,z);

Z:=10; a:=change (z) * change(10);

Writeln (a,z)

End.

Выполнение этой программы приводит к следующему результату на дисплее:

100 0

10000 -10

0 0

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

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

5.7. Предварительное описание (ссылки вперед)

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

Пример :

Program Demo;

Var a, b ,c : real ;

Procedure Ring (var s , l : real ; d : real);

Begin L:=3.14 *d; {длина окружности }

S:=cir (d) ; {компилятор еще не знает о функции cir}

End;

Function Cir (d: real): real; {площадь круга }

Begin cir:= 3.14* sqr(d) / 4;

End;

………………………………………………………………………

Очевидный выход – поменять порядок строк так, чтобы функция Cir была определена перед процедурой Ring(…) .Однако можно и иначе.

Действия:

1. Оставить подпрограмму (функцию cir) на своем месте, вычеркнув из ее заголовка все параметры: Function cir;

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

Function cir (d: real): real;

После полного заголовка добавить слово Forward.

6. РЕГУЛЯРНЫЕ ТИПЫ

6.1. Одномерный массив, или переменные с индексами

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

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

Описание в разделе переменных:

Var имя массива: Array [тип индекса] of тип элемента;

Тип индекса может быть любым простым типом, кроме Real и Integer (Boolean, Char, перечислимый, ограниченный).

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

Var A: Array [1..5] of Real;

Это массив из пяти действительных чисел: А[1], А[2], А[3], А[4], А[5].

Обычно нумерация начинается с единицы и заканчивается каким-нибудь положительным числом. Однако это совсем не обязательно.

Пример: Var B: Array [1582..1994] of Integer;

Var C: Array [-754..-1] of Integer;

(это, например, население за какие-то годы нашей эры и до нашей эры).

Массив латинских букв: (можно посчитать частоту появления в тексте):

Var Lat: Array [‘A’..’Z’] of Integer;

Массив t⁰C воздуха на островах:

Type Остров = (Gaiti, Sumatra, Taimir);

Var T: Array [Остров] of Real;

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

Var А: Array [5] of Real;

Var А: Array[Integer] of Real;

Пример:

Var

Massiv: Array [1..N] of Real;

Year: Array [янв..дек] of Integer;

Если несколько массивов имеют одинаковый тип индексов и одинаковый базовый тип, то допускается в описание объединять массивы в список:

Var А, В, С: Array[1..50] of Real;

Здесь объявлено списком три массива действительных чисел, каждый из которых содержит по 50 элементов:

А[1], A[2],… A[50].

B[1], B[2],… B[50].

C[1], C[2],… C[50].

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

Элементы массива записываются в разделе операторов как идентификатор с индексом в квадратных скобках.

B[5]:=B[3]-1;

Sum:=Sum-C[K];

P1:=A[2*3+1];

Для ввода и вывода числовых значений элементов массива используются циклы.

Пример:

For I:=1 to 9 do

Read(A[I]);

Это ввод 9-ти значений элементов массива А.

For I:=1 to 9 do

Writeln(A[I]);

Это их вывод.

Пример: Вычислить сумму 15-ти целых чисел.

Program Sum;

Var X: Array [1..15] of Integer;

I: 1..15;

Sum: Integer;

Begin

Sum:=0;

For I:=1 to 15 do

Begin

Read(X[I]);

Sum:=Sum+X[I];

End;

End.

В языке программирования Паскаль помимо явного описания массивов в разделе переменных есть другая форма описания, состоящая из двух этапов. Сначала в разделе описания типов Type указывается тип массива, затем в разделе описания переменных Var перечисляются массивы, относящиеся к донному типу.

Type имя типа = Array [тип индекса] of тип элементов массива;

Var имя массива: имя типа;

Пример: Программа с двумя процедурами: одна – для ввода элементов массива, другая для вычисления суммы и произведения элементов.

Program TI4;

Type Massiv = Array [1..20] of Real;

Var A, B: Massiv;

Sum, Pr: Real;

Procedure Vvod (N:Integer; Var X:Massiv);

Var I: Integer;

Begin

Writeln(‘Ввод’);

For I:=1 to N do Read(X[I]);

End;

Procedure Summa (N:Integer; Var X:Massiv; Var Sum, Pr: Real);

Var I: Integer;

Begin

Sum:= 0;

Pr:=1;

For I:=1 to N do

Begin

Sum:=Sum+X[I];

Pr:=Pr*X[I];

End;

End;

Begin

Vvod(8,A); (*вызов процедуры*)

Summa(8,A,Sum,Pr); (*вызов процедуры*)

Writeln (‘Sum=’,Sum:7:2,’ ’:3,’Pr=’,Pr);

Writeln;

Vvod(15,B);

Summa(15,B,Sum,Pr);

Writeln (‘Sum=’,Sum:7:2,’ ’:3,’Pr=’,Pr);

End.

В основной программе описан тип массива длинной 20 элементов, а реально используются массивы А (8 элементов) и В(15 элементов).

Пример: Расположить элементы заданного действительного массива в порядке убывания: 1 2 3 4  4 3 2 1

Program Rangir;

Const N=10;

Var A: Array [1..N] of Real;

I, K: Integer; R: Real;

Begin

Writeln(‘Ввод’);

For I:=1 to N do Read (A[I]);

For K:=1 to N do

For I:=1 to N-K do

If A[I]
Begin

R:= A[I];

A[I]:= A[I+1];

A[I+1]:=R;

End;

For I:=1 to N do Write (A[I]);

End.

K - номер просмотра строки (всего N-1 просмотров)

I - номер сравнение элементов в просмотре (N-K сравнений).

Пример: Массив R состоит из 10-ти элементов действительного типа.

Type Mas = Array [1..10] of Real;

Var R: Mas;

Если в программе несколько таких массивов, то изменится лишь раздел описания переменных:

Var R, A, B, C: Mas;

В разделе операторов программы используются массивы R, A, B, C. Тип массива Mas введен формально только в разделе описаний и нигде в программе не указывается и не обрабатывается.

Пример: Найти наибольшее из 10-ти заданных целых чисел.

Program Max;

Const N=10;

Type Massiv = Array [1..N] of Integer;

Var K: Massiv;

Max, I: Integer;

Begin

Writeln(‘Ввод’);

For I:=1 to N do Read (K[I]);

Max:=K[1];

For I:=2 to N do

If K[I]>Max then Max:=K[I];

Writeln;

Write (‘Max=’, Max:4);

End.

Здесь 2 независимых цикла:

1-ый – для ввода значений массива;

2-ой – для нахождения максимального элемента.

Сначала первый элемент массива K[1] обозначается именем Мах. Затем каждый последующий элемент сравнивается со значением Мах, и если он оказывается больше, то получает имя Мах.

Пример: Составить программу определения минимального и максимального элементов заданного массива.

Program Minmax;

Const N=9; (*число элементов*)

Type Massiv = Array [1..N] of Real;

Var A: Massiv; (*массив элементов*)

I: Integer; (*параметр цикла*)

Max, Min: Real; (*максимальный и минимальный элементы*)

Procedure Maxmin (K: Integer; Var X: Massiv; Var Max, Min: Real);

Var J: Integer;

Begin

Max:=X[1];

Min:=X[1];

For J:=2 to K do

Begin

If X[J] > Max then Max:= X[J];

If X[J] < Min then Min:= X[J];

End;

End;

Begin

Writeln (‘Ввод массива’);

For I:=1 to N do Read (A[I]);

Maxmin (N, A, Max, Min); (*вызов процедуры*)

Writeln (‘макс. элемент=’, Max:4:1);

Writeln (‘мин. элемент=’, Min:4:1);

End.

В процедуре Maxmin определяются максимальный и минимальный элементы массива. Переменная J и формальные параметры процедуры K, X, Max, Min являются локальными. В основной программе происходит ввод значений массива, вызов процедуры и вывод результатов. Константа N, тип Massiv, а также переменные A, I, Max и Min являются глобальными.

Пример: Дан массив действительных чисел {A_i}, где i=1,2,3,4,..M. Пусть M = 15. Вычислить сумму элементов с 1-го по 12-ый и сумму элементов с 8-го по 15-ый. Затем найти произведение этих сумм.

Program Pr2;

Const M=15;

Var A: Array [1..M] of Real;

P: Real; (*произведение сумм*)

J: Integer; (*параметр цикла*)

Function Summa (N, K: Integer): Real;

Var I: Integer;

S: Real;

Begin

S:=0;

For I:=N to K do S:=S+A[I];

Summa:=S;

End;

Begin

Writeln (‘Ввод массива’);

For J:=1 to M do Read (A[J]);

P:=Summa (1,12)* Summa(8,15);

Writeln(‘произведение=’,P:6:3);

End.

Пример: Дан массив (Х₁,Х₂,…Х₁₀₀). Записать отдельно положительные и отрицательные элементы.

Program Sort;

Const Nmax=100;

Var X,Pol,Otr: Array [1..Nmax] of Real;

I,N,K: Integer;

Begin

N:=0; K:=0;

For I:=1 to Nmax do

Begin

Read (X[I]);

If X[I] >0 then

Begin

K:=K+1;

Pol[K]:=X[I];

End

Else

Begin

N:=N+1;

Otr[N]:=X[I];

End;

End;

For I:=1 to K do Write (Pol[I]);

Writeln;

For I:=1 to N do Write (Otr[I]);

End.

Пример: Вычислить среднее арифметическое массива D из N элементов (N500).

Program Sred;

Const NM=500;

Var D: Array [1..NM] of Real;

I,N,Nvar: Integer;

Sum, Srd: Real;

Begin

Sum:=0;

Writeln (‘Nvar=?’);

Readln(Nvar);

Writeln (‘Ввод массива’);

For I:= 1 to Nvar do

Begin

Read (D[I]);

Sum:= Sum + D[I];

End;

Srd:=Sum/Nvar;

Writeln(‘Srd=’,srd);

End.

Пример: Вычислить n!

Program Nfact;

Var NF, K, N:Integer;

Begin

Writeln(‘N=?’);

Readln (N);

NF:=1;

For K:=1 to N do NF:=NF*K;

Writeln(‘NF=’,NF);

End.

Пример: Найти наибольший элемент массива (b₁,b₂,…b₁₀₀) и его №.

Program Max;

Const NMax=100;

Var B: Array [1..NMax] of Real;

I,Imax: Integer;

Bmax: Real;

Begin

Writeln (‘Ввод массива’);

For I:=1 to NMax do Read (B[I]);

Bmax:=b[1]; Imax:=1;

For I:=2 to NMax do

If B[I]>Bmax then

Begin

Bmax:=B[I];

Imax:=I;

End;

Writeln (‘Bmax=’, Bmax, ’Imax=’, Imax);

End.

Пример: Найти скалярное произведение двух векторов:

X=(x₁,x₂,…x_n) _n

Y=(y₁,y₂,…y_n) (X,Y)= x_iy_i

ⁱ⁼¹

Program Scal;

Const N=3;

Type Vektor = Array [1..N] of Real;

Var X, Y: Vektor;

I: Integer;

S: Real;

Begin

S:=0;

Writeln (‘Ввести X,Y’);

For I:=1 to N do

Begin

Read(X[I],Y[I]);

S:= S+ X[I]*Y[I];

End;

Writeln(‘Scal=’,S);

End.

Пример: Перемножить два вектора:

X=(x₁,x₂,x₃) _ _ _

Y=(y₁,y₂,y₃) Z = X * Y

Program V;

Type Vektor = Array [1..3] of Real;

Var X, Y, Z: Vektor;

I: Integer;

Begin

Writeln (‘Ввести X,Y’);

For I:=1 to 3 do

Begin

Read (X[I],Y[I]);

Z[I]:= X[I]*Y[I];

End;

Writeln (‘Вектор Z’);

For I:=1 to 3 do Write (Z[I]);

End.

(x₁, x₂, x₃) * (y₁, y₂, y₃) = (x₁y₁, x₂y₂, x₃y₃)

Алгоритмы сортировки массивов

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

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

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

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

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

1. Метод пузырька (метод обменной сортировки с выбором)

Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в там случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю оперно для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.

2. Сортировка выбором

На этот раз при просмотре мaccива мы будем искать наименьший элемент, сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив.

3. Метод Шелла

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

4. Метод Хoopа

Этот метод, называемый также быстрой сортировкой (QuickSort), был разработан в 1962 г. (его разработал Charles Antony Richard Hoare). Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.