МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению лабораторных работ дисциплина «Основы программирования» специальности 09.02.03 «Программирование в компьютерных системах»

7. Пусть Получить

8. Пусть Для заданного натурального n1 найти сумму квадратов тех чисел , которые не превосходят двух.

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

10. Даны действительные числа Вычислить с точностью до :

а) ; б) ;

в) ; г) .

ТЕМА 5. АЛГОРИТМЫ ОБРАБОТКИ ОДНОМЕРНЫХ МАССИВОВ

Цель – знакомство со структурированными типами данных – массивами, их описанием, алгоритмами решения некоторых задач обработки одномерных массивов и их реализацией средствами языка Pascal.

Задание. Даны целые числа . Если они образуют убывающую последовательность, то построить новую последовательность так, чтобы сначала расположились все четные, а потом – все нечетные члены исходной последовательности. Если не образуют убывающую последовательность, то поменять в ней местами наибольшее и наименьшее из чисел.

Решение. Данная задача распадается на несколько относительно независимых подзадач. А именно:

1) установление факта – образуют или не образуют убывающую последовательность числа . Пусть Flag=1, если последовательность убывающая и Flag=0 – в противном случае;

2) если Flag=1, то построить соответствующим образом новую последовательность и закончить решение задачи;

3) если Flag=0, то определить mx – местоположение наибольшего и mn – местоположение наименьшего из чисел последовательности ; затем нужно поменять местами числа и .

В итоге результатом решения задачи будет или построенная новая последовательность , или измененная последовательность .

Рассмотрим каждую подзадачу подробнее.

1. Последовательность является убывающей, если для каждой пары соседних чисел выполняется условие

, i=1,2,…,24. (12)

Поэтому, один из способов решения этой подзадачи заключается в подсчете - количества пар соседних чисел, удовлетворяющих вышеуказанному условию. Если в результате просмотра всех пар окажется, что =24, то исходная последовательность является убывающей и необходимо строить новую последовательность . Отметим, что в этом случае в качестве переменной Flag выступает переменная . Действительно, условия Flag=1 и =24,а также Flag=0 и

На алгоритмическом языке этот фрагмент имеет вид:

:=0

для от 1 до 24

нц

если

то :=+1

все

кц

Вторым способом решения этой подзадачи является часто используемый в математике метод от противного. Он заключается в формулировке такого предположения, для опровержения которого достаточно единичного факта. В нашем случае таким предположением будет следующее: пусть последовательность является убывающей, т.е. Flag=1. Как только обнаружится нарушение условия (12) убывания членов последовательности, так сразу положим Flag=0. Очевидно, что последующие нарушения условия (12) также будут устанавливать значение переменной Flag в нуль.

На алгоритмическом языке это можно записать так:

Flag:=1

для от 1 до 24

нц

если не ( )

то Flag:=0

все

кц

Отметим, что условие не() эквивалентно условию . Далее, просматривать последовательность следует до тех пор, пока еще остается в силе предположение об убывании ее членов и еще есть не просмотренные соседние пары чисел. Поэтому, целесообразнее использовать цикл ПОКА:

Flag:=1; :=1

пока Flag=1 и

нц

если

то Flag:=0

все

:=+1

кц

2. Для построения новой последовательности с сохранением взаимного относительного расположения чисел необходимо дважды просмотреть исходную последовательность, выбирая вначале все четные, а потом – все нечетные ее члены. Если порядок следования нечетных чисел из можно изменить на обратный, то исходную последовательность достаточно просмотреть только один раз, расставляя четные числа с начала последовательности , а нечетные – с конца. В любом случае «скорость» просмотра последовательности (изменение индекса ) и «скорость» заполнения с начала последовательности не совпадают. Поэтому, при построении результирующей последовательности ее элементы нужно индексировать другим индексом (например, ). Очевидно, что на любом шаге j≤i. При заполнении последовательности нечетными числами с конца местоположение (индекс) очередного нечетного числа определяется выражением 26-(-), где − индекс рассматриваемого элемента исходной последовательности, а j − количество четных чисел, расставленных с начала последовательности . Но удобнее использовать индекс для заполнения результирующей последовательности с конца, положив первоначально =26 и уменьшая значение этой переменной каждый раз на единицу.

В случае сохранения взаимного относительного расположения чисел в последовательности, алгоритм примет вид:

:=0

для от 1 до 25

нц

если - четное

то :=+1

все

кц

для от 1 до 25

нц

если - нечетное

то :=+1

все

кц

В случае расположения нечетных чисел в обратной последовательности алгоритм примет вид:

:=0; :=26

для от 1 до 25

нц

если - четное

то :=+1

иначе :=-1

все

кц

3. Для перестановки местами наибольшего и наименьшего чисел последовательности необходимо сначала определить их номера (индексы) mx и mn соответственно. Тогда - наибольшее, а − наименьшее из чисел, которые необходимо поменять местами. Используем метод от противного. Пусть первое число последовательности является одновременно наибольшим и наименьшим, т.е. mx=1 и mn=1. Если при просмотре последовательности найдется такое , то значение mx=i. Аналогично, если , то mn=i. После просмотра всей последовательности в mx и mn будут находиться необходимые значения. Очевидно, что если в последовательности несколько чисел равны наибольшему (или наименьшему) значению, то будет определен номер первого по порядку. Чтобы определить номер последнего из них достаточно заменить строгие неравенства нестрогими.

Далее, для обмена значениями двух величин необходимо использовать промежуточную величину того же типа. Обозначим ее через r. Тогда на алгоритмическом языке этот фрагмент примет вид:

:=1; :=1

для от 1 до 25

нц

если

то :=

все

если

то :=

все

кц

:=;:=; :=

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

алг Обработка массива (цел таб [1:25], [1:25])

арг

рез ,

нач цел , , , , ,

:=0

для от 1 до 24

нц

если

то k:=k+1

все

кц

если =24

то :=0

для от 1 до 25

нц

если - четное

то :=+1

все

кц

для от 1 до 25

нц

если - нечетное

то :=+1

все

кц

иначе

:=1; :=1

для от 1 до 25

нц

если

то :=

все

если

то :=

все

кц

:=; :=; :=

все

кон

Наш алгоритм рассчитан на обработку массивов, состоящих из 25 элементов, номера которых изменяются от 1 до 25. Если нужно обработать массивы с другой нумерацией элементов, то в программу всякий раз прийдется вносить соответствующие изменения. При этом существует определенный риск того, что не все исправления будут сделаны должным образом. Если элементы массивов и далее будут нумероваться с единицы, то устранить риск просто. Для этого нужно в программе определить константу − количество элементов массива и реализовать предложенный выше алгоритм при =25. После отладки достаточно будет изменять только определение этой константы в исходном тексте программы. Безусловным недостатком такого подхода является необходимость перекомпиляции программы. Аналогичным образом можно поступить и при изменяющемся начале нумерации, определив константу − начало нумерации, и сделав необходимые исправления в параметрах циклов.

Запишем программу на языке Pascal.

Program Obrabotka_mas;

Const n=25;

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

Var a, b : Massiv;

i, j, k, mn, mx : Word;

r : Integer;

Begin

WriteLn('Введите массив из ', n, ' целых чисел');

For i:=1 to n do Read(a[i]);

WriteLn;

k:=0;

For i:=1 to n-1 do

If a[i] a[i+1] then Inc(k);

If k = n-1 then

Begin j:=0;

For i:=1 to n do

If Not Odd(a[i]) then

Begin

Inc(j); b[j]:=a[i]

End;

For i:=1 to n do

If Odd(a[i]) then

Begin

Inc(j); b[j]:=a[i]

End;

WriteLn('Построена последовательность b');

For i:=1 to j do Write(b[i]:6)

End

Else

Begin

mx:=1; mn:=1;

For i:=1 to n do

Begin

If a[i] a[mx] then mx:=i;

If a[i]

End;

r:= a[mx]; a[mx]:= a[mn]; a[mn]:=r;

WriteLn('Изменена последовательность a');

For i:=1 to n do Write(a[i]:6)

End;

WriteLn

End.

Варианты заданий

1. Даны действительные числа . Если в результате замены отрицательных членов их квадратами будет образована неубывающая последовательность, то получить сумму членов исходной последовательности; в противном случае получить их произведение.

2. Даны целые числа . Получить новую последовательность, выбросив из исходной все члены со значением .

3. Даны целые числа .Все члены последовательности с четными номерами, предшествующие первому по порядку члену со значением , домножить на .

4. Даны целые числа , каждое из которых отлично от нуля. Если в последовательности отрицательные и положительные члены чередуются (+, -, +, -,… или -, +, -, +, …), то ответом должна служить сама исходная последовательность. Иначе получить все отрицательные члены последовательности, сохранив порядок их следования.

5. Даны натуральное число , действительные числа (числа попарно различны, ). В последовательности поменять местами наибольший член и член с номером m.

6. Даны действительные числа Получить действительные преобразовав для получения члены по правилу: если они оба отрицательны, то каждый из них увеличить на 0,5; если отрицательно только одно число, то отрицательное число заменить его квадратом; если оба числа неотрицательны, то каждое из них заменить на среднее арифметическое исходных значений.

7. Даны целые числа . Если в данной последовательности ни одно четное число не расположено после нечетного, то получить все отрицательные члены последовательности, иначе – все положительные.

8. Даны целые числа . Наименьший член последовательности заменить целой частью среднего арифметического всех членов, остальные члены оставить без изменения. Если в последовательности несколько наименьших членов, то заменить их все.

9. Даны целые числа . Получить новую последовательность из 100 целых чисел, заменяя нулями, если не равно и заменяя единицей в противном случае ().

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

ТЕМА 6. АЛГОРИТМЫ ОБРАБОТКИ ДВУМЕРНЫХ МАССИВОВ

Цель – углубление навыков алгоритмизации решения некоторых задач обработки двумерных массивов; реализация алгоритмов средствами языка Pascal.

Задание. Дана вещественная матрица Z(n,m). Построить вектор X по следующему правилу: x(j) равно среднему арифметическому элементов j-го столбца матрицы Z, j=1,...,m. В векторе найти номер k наименьшей из положительных компонент и все элементы соответствующего k-го столбца матрицы заменить значением этой компоненты вектора.

Решение. Данная задача распадается на несколько относительно независимых подзадач. А именно:

1) построить вектор Х по соответствующему правилу;

2) определить в векторе Х номер k – наименьшей из положительных компонент, km]. При этом нужно учесть, что все компоненты вектора Х могут оказаться неположительными и значение k будет неопределенным. В этом случае положим, например, k=0, выдадим соответствующее сообщение и закончим алгоритм. Если наименьших компонент будет несколько, то запомним номер первой из них;

3) если km], то все элементы соответствующего k-го столбца матрицы Z заменить значением компоненты вектора Х[k].

Рассмотрим каждую подзадачу подробнее.

1. Математическая модель имеет вид:

(13)

На алгоритмическом языке этот фрагмент запишется так:

для j от 1 до m

нц

X[j]:=0

для i от 1 до n

нц

X[j]:=X[j]+Z[i,j]

кц

X[j]:=X[j] / n

кц

2. Один из возможных способов решения заключается в следующем:

а) определить номер какой-нибудь, например первой по порядку, положительной компоненты вектора Х. Этот номер будет начальным значением для k на следующем шаге;

б) если k0, то определить в векторе Х номер наименьшей из положительных компонент.

На алгоритмическом языке этот фрагмент имеет вид:

 начало 2а 

k:=0; j:=1

пока jm и k=0

нц

если X[j]0

то k:=j

все

j:=j+1

кц

 начало 2б 

если k0

то

для j от k+1 до m

нц

если X[j]0 и X[j]X[k]

то k:=j

все

кц

иначе y:=”положительных компонентов в векторе Х нет”

все

Здесь y – литерная величина для хранения отрицательного результата.

3. При k0 , i=1,…,n.

Алгоритм заполнения k-го столбца матрицы имеет вид:

если k0

то

для i от 1 до n

нц

Z[i,k]:=X[k]

кц

все

При составлении алгоритма учтем, что шаги 1) и 2а) можно объединить, определив номер последней из положительных компонент вектора Х. Также можно объединить шаги 2б) и 3), так как они выполняются только при условии k0.

По смыслу задачи компоненты вектора Х вещественного типа. Выберем тип для матрицы также вещественный. Ниже приведен соответствующий алгоритм с необходимыми изменениями.

алг Обработка матрицы ( цел n,m,k, лит y, вещ таб Z[1:n,1:m], X[1:m] )

арг n, m, Z

рез k, y, X, Z

нач цел i, j

{ построение вектора и определение номера k

последней положительной компоненты вектора }

k:=0

для j от 1 до m

нц

X[j]:=0

для i от 1 до n

нц

X[j]:=X[j]+Z[i,j]

кц

X[j]:=X[j] / n

если X[j]0

то k:=j

все

кц

{ определение номера наименьшей положительной компоненты вектора и замена соответствующего столбца матрицы }

если k0

то

для j от 1 до k -1

нц

если X[j]0 и X[j]X[k]

то k:=j

все

кц {определен номер наименьшей положительной компоненты}

для i от 1 до n

нц

Z[i,k]:=X[k]

кц

иначе y:=”положительных компонентов в векторе Х нет”

все

кон

При написании программы на языке Pascal объявим m и n константами, например, m=3, n=5.

Program Matrica;

Const m=3; n=5;

Type Vector = Array[1..m] of Real;

Var X: Vector;

Z: Array[1..n] of Vector;

i, j, k : Word;

Begin

WriteLn('Введите матрицу ', n, '*', m, ' из вещественных чисел');

For i:=1 to n do

For j:=1 to m do Read(Z[i,j]);

WriteLn;

{ построение вектора и определение номера k}

{ последней положительной компоненты вектора }

k:=0;

For j:=1 to m do

Begin

X[j]:=0;

For i:=1 to n do

X[j]:=X[j]+Z[i,j];

X[j]:=X[j] / n;

If X[j]0 Then k:=j

End;

For j:=1 to m do Write(X[j]:8:3);

WriteLn;

{определение номера наименьшей положительной компоненты вектора}

{и замена соответствующего столбца матрицы}

If k0 Then

Begin

For j:=1 to k-1 do

If (X[j]0) and (X[j]

{ определен номер наименьшей положительной компоненты }

WriteLn('k=',k);

For i:=1 to n do

Begin

Z[i,k]:=X[k]; { замена соответствующего элемента k-го столбца }

{ матрицы }

For j:=1 to m do Write(Z[i,j]:8:3); {вывод i-ой строки матрицы}

WriteLn; { переход на новую строку экрана }

End

End

Else WriteLn('положительных компонентов в векторе Х нет')

End.

Варианты заданий

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

2. Найти первый положительный элемент в каждом столбце матрицы А, номер k столбца, в котором находится минимальное из них, и вычесть это минимальное значение из элементов k-ой строки, если строка с таким номером существует.

3. Определить номер столбца матрицы А с минимальным количеством отрицательных элементов и прибавить значения этого столбца к соответствующим элементам всех столбцов.

4. Найти среднее арифметическое в каждой строке матрицы А и, определив минимальное, прибавить его к элементам той строки, в которой он находится.

5. Найти максимальный элемент матрицы и вычесть его из элементов всех столбцов, кроме того, в котором он находится.

6. В квадратной матрице найти максимальный элемент. Если он окажется на главной диагонали, то элементы первой строки заменить его значением.

7. Найти максимальный и минимальный элементы в матрице. Умножить элементы строки, в которой находится максимум, на минимальное значение.

8. Определить номер столбца матрицы А с максимальным количеством единичных элементов и вычесть элементы этого столбца из соответсвующих элементов всех столбцов.

9. Найти минимальный и максимальный элементы в квадратной матрице. Заменить элементы строки, в которой находится минимальный элемент, элементами столбца, в котором находится максимальный элемент.

10. Определить номер строки матрицы А с максимальным количеством нулевых элементов и умножить элементы этой строки на соответствующие элементы нечетных строк.

ТЕМА 7. АЛГОРИТМЫ ОБРАБОТКИ СТРОК

Цель – знакомство со структурированными типами данных – строками, их описанием, алгоритмами решения некоторых задач обработки строк; реализация алгоритмов средствами языка Pascal.

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

Решение. Обозначим исходный текст через S, а результирующий - R. Так как предшествующая предложению группа пробелов в тексте S не учитывается, то построим промежуточный текст Т, в котором нет пробелов перед предложениями. Кроме того, удалим все символы текста после последней точки, потому что они не образуют предложение, при этом выведем на экран соответствующее сообщение.

Пусть j – начало текущего предложения, а k – его длина (номер первой точки, начиная отсчет с j-го символа). Просмотрев весь текст Т, определим jmin и kmin – начало и длину самого короткого из предложений. Добавим в текст R “вырезку” T[jmin : jmin+kmin-1] и пробел-разделитель. Из текста Т данную “вырезку” удалим. Затем снова просмотрим текст Т, определим новые значения jmin и kmin и т.д., пока в тексте Т не останется ни одного предложения, т.е. он станет пустым. Это можно отождествить с k=0 (в тексте нет точек).

Для построения текста Т перепишем в него исходный текст S с “приклеенной” слева точкой. Затем в тексте Т удалим все символы после последней точки и все пробелы от каждой точки до первого символа, не равного пробелу. После этого удалим “приклеенную” слева точку.

Алгоритм с комментариями в фигурных скобках имеет вид:

алг Строки ( лит S, R, y)

арг S

рез R, y

нач лит Т, цел j, k, jmin, kmin, Flag

T:=”.” + S { исходный текст S с “приклеенной” слева точкой }

Flag:=0

j:=длин(T)

пока T[j:j] ”.”

нц

Удалить j-ый символ из T

j:=j-1 {удаление символов после последней точки}

Flag:=1

кц

j:=2 { начало первого предложения }

пока j длин( T )

нц

пока T[ j : j] =” “ { пока текущий j-ый символ ─ пробел }

нц

Удалить j-ый символ из T

кц

j:=j+(Номер очередной точки текста T, начиная отсчет с j-го символа)

{начало очередного предложения}

кц

Удалить первый символ из T { удаление “приклеенной” слева точки }

R:= ””

пока длин( T ) 0

нц

jmin:=0;

kmin:= длин( T ) { длина предложения не больше длины текста}

j:=1 { начало первого предложения }

пока j длин( T )

нц

k:= Номер очередной точки текста T, начиная отсчет с j-го символа

если k kmin

то jmin := j; kmin := k;

все

j := j + k { начало очередного предложения }

кц

R := R + T[jmin : jmin+kmin-1] + “ “ { формирование результата }

Удалить kmin символов из T, начиная с jmin

кц

если Flag = 1

то

y:=”В исходном тексте удалены все символы после последней точки”

все

кон

При составлении программы учтем, что в языке программирования Pascal команде Удалить… соответствует процедура Delete, “вырезке” T[jmin : kmin] - функция Copy, команде Номер очередной точки… - функция Pos. Для переменной Flag удобно выбрать тип Boolean. Значение True имеет место при отбрасывании символов после последней точки.

Программа примет вид:

Program Stroky;

Var S, T, R : String;

Flag : Boolean;

j, k, jmin, kmin : Integer;

Begin

WriteLn('Введите текст');

ReadLn( S );

T:='.' + S ; { исходный текст S с "приклеенной" слева точкой }

Flag:=False; { предположим, что в конце текста стоит точка }

j:=Length(T);

While T[j] '.' Do { пока в конце текста не точка }

Begin

Delete(T, j, 1); { удалить последний символ }

Dec(j); Flag:=True;

End;

j:=2; { начало первого предложения }

While j

Begin

While T[ j ] = ' ' Do { пока текущий j-ый символ ─ пробел, }

Delete (T, j, 1) ; {удалить j-ый символ из T }

j:= j + Pos('.', Copy(T, j, Length( T ) - j +1)); {начало}

{очередного предложения}

End;

Delete(T, 1, 1); { удаление "приклеенной" слева точки }

R:='';

While Length( T ) 0 Do

Begin

jmin:=0;

kmin:= Length( T ); { длина предложения не больше длины текста!}

j:=1; { начало первого предложения }

While j

Begin

k:= Pos('.', Copy(T, j, Length( T ) - j +1)); {длина предложения }

{минус номер очередной точки текста T,} {начиная отсчет с j -го символа }

If k

Begin jmin := j;

kmin := k;

End;

j := k+j; { начало очередного предложения }

End;

R := R + Copy(T, jmin, kmin) + ' '; { формирование результата }

Delete(T, jmin, kmin); {удаление kmin символов из T, начиная с jmin}

End;

WriteLn(R);

If Flag Then WriteLn('Примечание: в исходном тексте удалены все ',

'символы после последней точки');

End.

Варианты заданий

1. Составить программу, по которой на экран выводится слово, содержащее наименьшее количество символов в данном тексте.

2. Составить программу, по которой данный текст переписывается так, что порядок символов в ней обратный и, кроме того, перед каждым символом стоит буква "A". Количество символов в тексте при этом удваивается.

3. Составить программу, по которой в данном тексте буквосочентание "sin" заменяется на "синус" и буквосочетание "cos" заменяется на "косинус".

4. Написать программу, определяющую в данном предложении слово, в котором доля гласных максимальна.

5. Написать программу, печатающую данное предложение так, что каждое его слово целиком находится в данной строке распечатки (т.е. отсутствуют переносы). Длина строки распечатки 20 символов.

6. Заменить окончание "ое" каждого слова, встречающегося в данном предложении, на "ые".

7. Составить программу, по которой определяется количество повторений союзов в данном тексте.

8. Составить программу, по которой на экран выводится слово данного текста, начинающееся с буквы "а" и содержащее наибольшее количество символов.

9. Составить программу, определяющую, сколько раз в данном предложении встречается сочетание букв "оно". Найти и напечатать слово предложения, в котором это сочетание встречается максимальное количество раз.

10. Проверить в данном тексте соответствие открывающих и закрывающих круглых скобок.

ТЕМА 8. ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ. ИСПОЛЬЗОВАНИЕ ПОДПРОГРАММ

Цель – углубление навыков алгоритмизации методом пошагового уточнения с использованием вспомогательных алгоритмов; реализация алгоритмов с помощью процедур и функций языка Pascal.

Задание. Расположить элементы векторов из целых чисел в порядке возрастания их значений. (Задача сортировки).

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

Пусть нам дан вектор из целых чисел. Назовем последовательность элементов текущим массивом на i-ом шаге. Предположим, что в результате выполнения предыдущих (i-1) шагов первые i-1 элемент находятся на своих местах, т.е.

, (14)

и для любого из оставшихся n-(i-1) элемента справедливо неравенство

(15)

На i-ом шаге определим k – номер наименьшего элемента текущего массива и поменяем местами и элементы. В силу (14) и (15) первые i элементов станут упорядоченными, т.е. , а неравенство (15) будет верным для оставшихся n-i элементов. Продолжая и так далее, через n-1 шаг получим решение задачи ( на n–ом шаге остается один элемент в текущем массиве; он будет наибольшим в векторе и располагаться на последнем месте).

В первом приближении алгоритм имеет вид:

алг Сортировка (нат n, цел таб a[1:n] )

арг n, a

рез a

нач нат i, k

для i от 1 до n-1

нц

Определить номер k наименьшего элемента текущего массива

Поменять местами и элементы

кц

кон

В алгоритме используются две «укрупненные» команды «Определить номер…» и «Поменять местами…», требующие дальнейшего уточнения. Используем для их реализации вспомогательные алгоритмы. Так как результатом выполнения первого алгоритма есть одна величина, то оформим его как вспомогательный алгоритм вычисления значения функции. При этом в заголовке перед служебным словом алг укажем тип результата нат, а значение функции передадим через специальное служебное слово знач. После имени функции в круглых скобках задаются только ее аргументы, поэтому отсутствуют строки арг и рез.

нат алг Nmin (нат n, i, цел таб a[1:n] )

нач нат j, k

k:=i

для j от i+1 до n

нц

если a[j]

то k:=j

все

знач:= k

кц

кон

Обмен значениями двух величин был рассмотрен ранее. Алгоритм имеет вид:

алг Обмен ( цел a, b)

арг a, b

рез a, b

нач цел r

r:=a; a:=b; b:=r

кон

Теперь можно записать алгоритм сортировки вектора полностью:

алг Сортировка (нат n, цел таб a[1:n] )

арг n, a

рез a

нач нат i, k

для i от 1 до n-1

нц

k :=Nmin ( n, i, a )

Обмен ( a[k], a[i])

кц

кон

Две команды в теле цикла можно заменить одной, исключив переменную k : Обмен ( a[Nmin(n,i,a)], a[i] ).

Полностью алгоритм решения задачи имеет вид:

алг Сортировка векторов( цел таб a[1:10], b[1:8] )

арг a, b

рез a, b

нач

Сортировка( 10, a)

Сортировка( 8, b)

кон

Из последнего алгоритма видно, что задача сортировки любого другого количества векторов не представляет проблемы. Более того, можно выбрать иной вспомогательный алгоритм сортировки, сохранив его заголовок. Можно привлечь группу программистов, поручив им разработку отдельных алгоритмов, что ускорит процесс решения задачи. Однажды разработанные вспомогательные алгоритмы удобно использовать при решении других задач. Так, с помощью алгоритмов Обмен, Nmin и аналогичной функции Nmax(n,i,a), находящей номер наибольшего элемента в векторе , начиная с i–го, третий этап решения рассмотренной в пятой теме задачи можно записать одной командой в виде: Обмен ( a[Nmin(25, 1, a)] , a[Nmax(25, 1, a)]).

Программа обработки вектора всегда содержит его описание и почти всегда ввод и/или вывод его элементов. Поместим объявление константы n (например, n=100), типа массива Mas и описание процедур ввода и вывода элементов вектора в файл с именем VvVyv.pas рабочего каталога. Содержимое этого файла имеет вид:

Const n=100;

Type Mas=Array[1..n] Of Integer;

Procedure Vvod(n:Word; Var a: Mas);

Var i: Word;

Begin

For i:=1 to n do Read(a[i])

End;

Procedure Vyvod(n:Word; a: Mas);

Var i: Word;

Begin

For i:=1 to n do Write(a[i]:8:2);

WriteLn

End;

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

{$I имя_файла} для вставки содержимого файла в текст программы.

Program SortVect;

{$I VvVyv} {Вставка объявлений константы n и типа Mas,}

{а также описаний процедур ввода и вывода}

Var a,b: Mas;

Function Nmin(n,i:Word; a:Mas):Word;

Var j,k:Word;

Begin

k:=i;

For j:=i+1 to n do

If a[j]

Nmin:=k

End;

Procedure Swap(a,b:Integer);

Var r:Integer;

Begin

r:=a; a:=b; b:=r

End;

Procedure Sort(n:Word; a:Mas);

Var i:Word;

Begin

For i:=1 to n-1 do Swap(a[Nmin(n,i,a)], a[i])

End;

Begin

WriteLn(‘Введите ’,10,’ чисел вектора А’);

Vvod(10,a);

Sort(10,a);

WriteLn(‘Результат сортировки вектора А’);

Vyvod (10,a);

WriteLn(‘Введите ’,8,’ чисел вектора В’);

Vvod(8,b);

Sort(8,b);

WriteLn(‘Результат сортировки вектора B’);

Vyvod (8,b);

End.

Варианты заданий

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

1. Даны три массива А(10), B(6), С(8). Найти максимальный элемент в каждом массиве и максимальный среди максимальных.

2. Даны две матрицы Х(3,4), Y(4,2). Найти среднее арифметическое всех элементов в каждой матрице.

3. Даны три массива А(10), B(6), С(8). Нормировать элементы каждого массива (т.е. разделить все его элементы на максимальный элемент).

4. Даны четыре вектора А(5), B(5), C(8), D(8). Вычислить скалярное произведение (A,B) и (C,D). ( Скалярное произведение векторов X и Y вычисляется по формуле: (X,Y)=).

5. Даны три матрицы A(2,3), B(2,3), C(2,3). Присвоить переменной K значение 2, если все суммы элементов каждой матрицы равны между собой, значение 1, если равны две какие-либо суммы и значение 0 в противном случае.

6. Даны три матрицы A(2,2), B(2,3), C(3,2). Если сумма всех элементов матрицы больше 0, то у первого элемента этой матрицы заменить знак на противоположный.

7. Даны две матрицы A(2,2), B(3,3). Присвоить переменной PA значение 1, если элементы матрицы А симметричны относительно главной диагонали и значение 0 в противном случае. Аналогично вычислить PB для матрицы B.

8. Даны две матрицы А(3,4) и В(4,3). Подсчитать количество элементов, больших 10 для каждой из матриц.

9. Даны три массива А(6), В(7), С(8). В каждом из этих массивов найти сумму элементов после первого отрицательного и сумму элементов, расположенных до него.

10. Даны три матрицы А(2,2), В(2,3), С(4,3). В каждой из этих матриц найти максимальный элемент и заменить его нулем.

ТЕМА 9. РЕКУРСИВНЫЕ АЛГОРИТМЫ

Цель – применение рекурсии при решении некоторых задач; построение рекурсивных алгоритмов и их реализация средствами языка Pascal.

Задание. Написать рекурсивную функцию вычисления xⁿ, xR, nZ, не используя операцию возведения в степень.

Решение. Для простоты будем считать, что = 1. Тогда множество значений аргументов для тривиального результата зависит только от n: ={(х,0)}. При этом =1.

Назовем функцию Power. Тогда

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

вещ алг Power(вещ х, цел n)

нач

если n=0

то знач:=1

иначе

если n0

то знач:= Power (х, n-1)*х

иначе знач:= Power (1/х, -n)

все

все

кон

Запишем программу с использованием соответствующей рекурсивной функции.

Program PrimPower;

Var x:Real;

n:Integer;

Function Power(x:Real; n:Integer): Real;

Begin

If n=0 Then Power:=1

Else If n0 Then Power:=Power(x, n-1)*x

Else Power:=Power(1/x, -n)

End;

Begin

WriteLn(‘x n=’); ReadLn(x, n);

WriteLn(‘Ответ:’, Power(x, n))

End.

Варианты заданий

1. Написать рекурсивную функцию вычисления НОД(n,m), n,mZ.

2. Написать рекурсивную функцию вычисления числа сочетаний C_mⁿ, nm, n,mZ.

3. Написать рекурсивную функцию вычисления корня уравнения f(x)=0 методом деления пополам.

4. Написать рекурсивную функцию вычисления корня уравнения f(x)=0 методом Ньютона.

5. Написать рекурсивную функцию вычисления корня уравнения f(x)=0 методом хорд.

6. Написать рекурсивную функцию вычисления корня уравнения x=g(x) методом итераций.

5. Написать рекурсивную функцию вычисления суммы степенного ряда, например,

8. Написать рекурсивную функцию отображения X [0;], добавляя или вычитая из X число .

9. Написать рекурсивную функцию вычисления интеграла по формуле Симпсона.

10. Написать рекурсивную функцию вычисления интеграла по формуле трапеций.

ТЕМА 10. АЛГОРИТМЫ РАБОТЫ С МНОЖЕСТВАМИ

Цель – знакомство со структурированными типами данных – множествами, их описанием, алгоритмами решения некоторых задач обработки множеств; реализация алгоритмов средствами языка Pascal.

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

Решение. Обозначим исходный текст через S. Пусть A – множество букв алфавита; V – множество букв –го предложения; T – множество букв, входящих в первые предложения ; W – множество букв, входящих не менее чем в два предложения из первых предложений ; Z – множество букв, входящих не менее чем в три предложения из первых предложений; R – множество букв, входящих только в два предложения заданного текста.

Очевидно, что R= W \ Z, где k – количество предложений текста. Тогда математическая модель задачи примет вид:

Z = Z (W V) ; (16)

W = W (T V) ; (17)

T = T V ; (18)

= 1,2,…,k, (19)

Z= W= T=. (20)

Множество V должно начинаться с пустого для каждого предложения.

Запишем программу решения задачи.

Program PrimSet;

Var S:String;

A,V,T,W,Z,R:Set of Char;

i:Integer;

c:Char;

Begin

Write(‘Введите исходный текст:’); ReadLn(S);

A:=[‘А’..’Я’, ’а’..’я’];

V:=[ ]; Z:=[ ]; W:=[ ]; T:=[ ];

For i:=1 To Length(S) Do

If S[i] In [ ‘.’, ‘!’, ‘?’ ] Then

Begin

Z:=Z + (W * V);

W:=W + (T * V);

T:=T + V;

V:=[ ]

End

Else If S[i] In A Then Include( V, S[i] );

R:=W – Z;

WriteLn(‘Список букв, которые встречаются только в двух ', 'предложениях:’);

For c:=’А’ To ‘я’ Do

If c In R Then Write(c:2);

WriteLn;

End.

Варианты заданий

1. Описать функцию Count(s), подсчитывающую общее количество цифр и знаков '+', '-' и '*', входящих в строку s.

2. Дано 100 целых чисел от 1 до 50. Определить, сколько среди них чисел Фибоначчи и сколько чисел, первая значащая цифра в десятичной записи которых 1 или 2.

3. Описать функцию CountDay(m), определяющую количество дней в месяце m (невисокосного года).

4. Описать функцию Card(S), подсчитывающую количество элементов во множестве S типа M. Тип М объявляется глобальным и совместим по присваиванию с типом Byte. (Например, Card([5,8,21])=3 ).

5. Описать процедуру Print(S), печатающую в алфавитном порядке все элементы множества S, состоящего из латинских букв.

6. Описать функцию Sum(A,s1,s2), вычисляющую сумму тех элементов матрицы A, номера строк и столбцов которых принадлежат соответственно непустым множествам s1 и s2.

7. Дан текст. Определить, каких букв − гласных (а,е,и,о,у,ы,э,ю,я) или согласных − больше в этом тексте.

8. Описать функцию Digit(n), подсчитывающую количество различных (значащих) цифр в десятичной записи натурального числа n.

9. Описать процедуру Print(n), печатающую в возрастающем порядке все цифры, не входящие в десятичную запись натурального числа n.

10. Дан текст из строчных латинских букв. Напечатать:

а) первые вхождения букв в текст, сохраняя их исходный взаимный порядок;

б) все буквы, входящие в текст не менее двух раз;

в) все буквы, входящие в текст по одному разу.

ТЕМА 11. АЛГОРИТМЫ РАБОТЫ С ЗАПИСЯМИ

Цель – знакомство со структурированными типами данных – записями, их описанием, алгоритмами решения некоторых задач обработки массивов записей; реализация алгоритмов средствами языка Pascal.

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

Решение. Определим тип записи TData для сведений об экспортируемом товаре в виде:

Здесь Day, Month, Year – день, месяц и год отправки товара на экспорт; Name – его наименование; Country – страна-импортер; Size – объем поставляемой партии в штуках. В скобках указаны типы полей. Поле Date также является записью.

Пусть исходный массив имеет имя A, а наименование товара для поиска Nam1. Построим результирующий массив B из записей, содержащих название страны и общий объем экспортируемого товара SumSize, в виде:

Объем товара по всем странам обозначим через Itogo с начальным значением, равным нулю. Для каждой i-ой записи A[i], как только A[i]. Name= Nam1, увеличим значение Itogo на величину A[i].Size и будем просматривать массив В с целью установления факта наличия записи k с той же самой страной-импортером, что и в A[i], т.е. В[k].Country = A[i].Country. В этом случае увеличим значение SumSize на величину Size:

В[k].SumSize := В[k].SumSize +A[i].Size; (21)

Если такой записи в массиве В еще нет, то добавим в него новую запись со значениями полей A[i].Country и A[i].Size соответственно. При этом реальное количество элементов массива возрастет на единицу. Обозначим это количество через L.

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

Фрагмент алгоритма имеет вид:

Itogo:=0

L:=0 {сначала в массиве В нет записей}

для i от 1 до N

нц

если A[i].Name=Nam1

то

Itogo:=Itogo+ A[i].Size

k:=0 {предположим, что в В нет записи о стране,

импортирующей заданный товар}

j:=1

пока j ≤ L и k = 0 {пока не просмотрен массив В и не

нц найдена нужная запись}

если В[j].Country = A[i].Country

то k:=j {в массиве В найдена запись k ≠ 0 о стране-

импортере}

все

j:=j+1

кц

если k ≠ 0

то В[k].SumSize := В[k].SumSize +A[i].Size

иначе { добавим в массив В новую запись }

L:=L+1

В[L].Country = A[i].Country

В[L].SumSize := A[i].Size

все

все

кц

Если L так и останется равным нулю, то данный товар не экспортируется ни в одну из стран.

Программа примет вид:

Program MasZap;

Const M=100;

Type TData=Record

Data:Record

Day,Month:Byte;

Year:Word

End;

Name:String[20];

Country:String[15];

Size:LongInt

End;

TDataB=Record

Country:String[15];

SumSize:LongInt

End;

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

B:Array[1..M] of TDataB;

L,i,j,k,N:Word;

Itogo:LongInt;

Nam1:String[20];

Begin

Write('Введите количество записей N=');

ReadLn(N);

For i:=1 To N Do

Begin WriteLn(i,'-я запись:');

Write('Введите дату в виде ЧЧ ММ ГГГГ ');

With A[i].Data Do ReadLn(Day,Month,Year);

With A[i] Do

Begin

Write('Введите название товара '); ReadLn(Name);

Write('Введите страну-импортера '); ReadLn(Country);

Write('Введите объем партии в шт. '); ReadLn(Size);

End;

End;

Write('Введите название данного товара '); ReadLn(Nam1);

Itogo:=0;

L:=0;

For i:=1 To N Do

If A[i].Name=Nam1 Then

Begin Itogo:=Itogo+A[i].Size;

k:=0; j:=1;

While (j

Begin

If B[j].Country=A[i].Country Then k:=j;

Inc(j)

End;

If k0 Then B[k].SumSize:=B[k].SumSize+A[i].Size

Else Begin Inc(L);

B[L].Country:=A[i].Country;

B[L].SumSize:=A[i].Size

End

End;

If L=0 Then WriteLn('Данный товар не экспортируется')

Else Begin

WriteLn('--------------------------------');

WriteLn('Страна-импортер : Объем поставок');

WriteLn('--------------------------------');

For j:=1 To L Do

With B[j] Do WriteLn(Country:15,' : ',SumSize:13);

WriteLn('--------------------------------');

WriteLn(' Итого : ',Itogo:13)

End

End.

Примерный вид диалога показан ниже (набираемая информация указана жирным шрифтом):

Введите количество записей N=5

1-я запись:

Введите дату в виде ЧЧ ММ ГГГГ 01 03 1999

Введите название товара ЗАЗ-Таврия

Введите страну-импортера Грузия

Введите объем партии в шт. 30

2-я запись:

Введите дату в виде ЧЧ ММ ГГГГ 20 10 1999

Введите название товара Т-80

Введите страну-импортера Пакистан

Введите объем партии в шт. 50

3-я запись:

Введите дату в виде ЧЧ ММ ГГГГ 15 11 1999

Введите название товара Су-24

Введите страну-импортера Россия

Введите объем партии в шт. 5

4-я запись:

Введите дату в виде ЧЧ ММ ГГГГ 01 04 1999

Введите название товара ЗАЗ-Таврия

Введите страну-импортера Россия

Введите объем партии в шт. 100

5-я запись:

Введите дату в виде ЧЧ ММ ГГГГ 10 09 1999

Введите название товара ЗАЗ-Таврия

Введите страну-импортера Грузия

Введите объем партии в шт. 50

Введите название данного товараЗАЗ-Таврия

---------------------------------------------

Страна-импортер : Объем поставок

---------------------------------------------

Грузия : 80

Россия : 100

---------------------------------------------

Итого : 180

Варианты заданий

1. Сведения о пассажире состоят из номера рейса, его фамилии, количества вещей и общего веса вещей. Дан массив, содержащий сведения о некоторых пассажирах.

а) создать массив сведений о пассажирах заданного рейса, для которых средний вес одной вещи отличается не более чем на 0,3 кг от общего среднего веса вещи всех пассажиров;

б) создать массив сведений о пассажирах, багаж которых совпадает по количеству вещей и различается по весу не более чем на 0,5 кг;

в) создать массив сведений о пассажирах, багаж которых не меньше багажа каждого из остальных пассажиров одного и того же рейса и по количеству вещей, и по весу;

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

2. Сведения об ученике состоят из его фамилии, имени и названия класса (года обучения и буквы), в котором он учится. Дан массив, содержащий сведения об учениках школы.

а) создать массив сведений об однофамильцах школы;

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

в) создать массив сведений об однофамильцах одного класса;

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

д) создать массив сведений об учениках школы, поместив вначале сведения об учениках класса 1а, затем 1б, и т.д., затем 2а, 2б и т.д..

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

4. Сведения об автомобиле состоят из его марки, номерного знака, фамилии владельца и даты проведения технического осмотра. Дан массив регистрации, содержащий сведения о нескольких автомобилях.

а) создать массив сведений о количестве автомобилей каждой марки;

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

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

6. Сведения о кубике состоят из длины ребра в сантиметрах, его цвета и названия материала, из которого он изготовлен. Дан массив сведений о кубиках. Создать массив сведений о количестве и суммарном объеме кубиков каждого из цветов.

7. Сведения о веществе состоят из его названия, удельного веса и типа проводимости (проводник, полупроводник, изолятор). Дан массив сведений о некоторых веществах. Создать массив сведений о проводниках и упорядочить их по убыванию удельных весов.

ТЕМА 12. АЛГОРИТМЫ РАБОТЫ С ФАЙЛАМИ

Цель – знакомство с текстовыми и типизированными файлами, их описанием, алгоритмами решения некоторых задач обработки файлов; реализация алгоритмов средствами языка Pascal.

Задание. Сведения об экспортируемом товаре состоят из даты отправки, наименования товара, страны, импортирующей товар и объема поставляемой партии в штуках (см. задание предыдущей темы 11). Создать типизированный файл EXPORT.DAT, содержащий сведения о некоторых экспортируемых товарах. Для заданного наименования товара создать типизированный файл результатов EXPORT.REZ из сведений о странах и объеме экспортируемого товара по каждой стране. Вывести на экран содержимое файла EXPORT.REZ и подсчитать общий объем экспорта. Исходные данные находятся в текстовом файле EXPORT.TXT текущего каталога, причем сведения об одном товаре занимают одну строку.

Решение. Используем типы записей TData для сведений об экспортируемом товаре и TDataB для результата из предыдущего задания. Выберем файловые переменные ftext, fdat, frez для файлов EXPORT.TXT , EXPORT.DAT и EXPORT.REZ соответственно. Для работы с файлом EXPORT.DAT используем переменную А типа TData, а для файла EXPORT.REZ – переменную В типа TDataВ.

Алгоритм решения аналогичен рассмотренному в предыдущем задании (см. тему 11), но вместо элементов массивов мы будем использовать переменные типа запись А и В.

Будем считать, что в текстовом файле EXPORT.TXT название товара отделяется от значения года только одним пробелом и содержит 20 символов (если название товара короче, то оно дополняется пробелами); название страны-импортера содержит 15 символов (включая необходимые пробелы) и идет сразу же после названия товара; объем экспорта может отделяться от предшествуюшего названия страны любым количеством пробелов (или не отделяться вовсе). С помощью редактора Турбо-Паскаля откроем файл EXPORT.TXT и наберем исходную информацию в виде:

01 03 2004 ЗАЗ-Таврия Грузия 30

20 10 2004 Т-80 Пакистан 50

15 11 2004 Су-24 Россия 5

01 04 2004 ЗАЗ-Таврия Россия 100

10 09 2004 ЗАЗ-Таврия Грузия 50

В конце последней строки нажимать на клавишу ввода не нужно, т.к. после сохранения набранного текста (File/Save или F2) запишется признак конца файла с кодом #26.

Следует помнить, что каждое арифметическое значение в строке ввода отделяется от следующего за ним другого данного хотя бы одним пробелом, при этом пробелы-разделители не входят в последовательность символов изображения числа. Если не принять мер предосторожности, пробел между годом и названием товара присоединится (“приклеется”) к названию товара, а ставший теперь лишним последний символ названия товара присоединится к названию страны, что, в свою очередь, приведет к появлению последнего символа названия страны в поле для объема экспорта. Если этот лишний символ окажется не пробелом, то возникнет ошибка преобразования числового данного (“Error 106. Invalid numeric format”) и программа будет снята. Даже если такое сообщение и не появится, все равно программа содержит ошибку, т.к. при вводе заданного товара мы вряд ли начнем его название с пробела. Для разрешения данной ситуации воспользуемся переменной ch символьного типа для считывания (“сбрасывания”) пробела-разделителя между годом и названием товара.

Программа примет вид:

Program FilOfZap;

Type

TData=Record

Data:Record

Day,Month:Byte;

Year:Word

End;

Name:String[20];

Country:String[15];

Size:LongInt

End;

TDataB=Record

Country:String[15];

SumSize:LongInt

End;

Var

ftext: Text;

fdat: File Of TData;

frez: File Of TdataB;

A: TData;

B: TDataB;

L,i,k,N:Word;

Itogo:LongInt;

Nam1:String[20];

ch:char;

Begin

{ Назначения для файлов}

Assign(ftext,'EXPORT.TXT');

Assign(fdat,'EXPORT.DAT');

Assign(frez,'EXPORT.REZ');

Reset(ftext); { Открыть для чтения }

ReWrite(fdat); { Открыть для записи }

While Not EOF(ftext) Do { Пока не конец файла ftext, выполнять ...}

Begin

With A.Data Do Read(ftext, Day, Month,Year); {Читать дату}

Read(ftext, ch); {"Сбросить" пробел-разделитель}

With A Do

ReadLn(ftext, Name, Country, Size); {Продолжить чтение строки}

Write(fdat, A) { Писать запись А в файл fdat }

End; {формирования файла fdat }

Close(ftext); {Закрыть текстовый файл ftext}

Write('Введите название данного товара ');

ReadLn(Nam1); {Ввести с клавиатуры название данного товара }

For i:=Length(Nam1)+1 To 20 Do

Nam1:=Nam1+' '; {Дополнение пробелами до 20 символов}

Itogo:=0;

L:=0;

Reset(fdat); { Открыть для чтения }

N:=FileSize(fdat); {Количество записей в файле fdat}

ReWrite(frez); {Создание пустого нового файла результатов}

Reset(frez); {Открыть для чтения, но при этом можно и писать в файл!}

For i:=1 To N Do

Begin

Read(fdat, A); {Читать файл fdat в запись А}

If A.Name=Nam1 Then

Begin Itogo:=Itogo+A.Size;

k:=0;

Seek(frez, 0); {Установить указатель файла на начало}

While (Not EOF(frez)) and (k=0) Do

Begin

Read(frez, B);

If B.Country=A.Country Then {Если страны совпадают, то}

k:=FilePos(frez); { k:= позицию следующей после}

{ текущей записи файла}

End;

If k0 Then

Begin Seek(frez, k-1); { Установить указатель файла на }

{ текущую запись }

B.SumSize:=B.SumSize+A.Size;

End

Else

Begin

B.Country:=A.Country;

B.SumSize:=A.Size;

End;

Write(frez, B); { Записать обновленную или новую запись }

{в файл frez }

Inc(L);

End

End; {Файл fdat обработан}

If L=0 Then WriteLn('Данный товар не экспортируется')

Else

Begin

WriteLn('--------------------------------');

WriteLn('Страна-импортер : Объем поставок');

WriteLn('--------------------------------');

Seek(frez, 0);

While Not EOF(frez) Do

Begin Read(frez, B); {Читать файл frez в запись B}

With B Do WriteLn(Country:15,' : ',SumSize:13);

End;

WriteLn('--------------------------------');

WriteLn(' Итого : ',Itogo:13)

End

End.

Для указанного выше содержимого файла EXPORT.TXT и товара ЗАЗ-Таврия результат выполнения программы совпадает с приведенным в теме 11.

Варианты заданий берутся из приведенных в теме 11 со следующими изменениями:

1) исходные данные расположены в некотором текстовом файле *.ТХТ, причем каждая запись занимает одну строку;

2) по текстовому файлу создается типизированный файл исходных данных *.DAT;

3) в процессе обработки типизированного файла исходных данных создается типизированный файл результатов *.REZ;

4) содержимое результирующего файла выводится на экран в виде соответствующей таблицы.

ТЕМА 13. АЛГОРИТМЫ РАБОТЫ СО СВЯЗНЫМИ СПИСКАМИ

Цель – знакомство с динамическими структурами данных – линейными списками и основными операциями над ними; моделирование линейных списков с помощью связных списков; разработка алгоритмов решения некоторых задач обработки связных списков и их реализация средствами языка Pascal.

Задание. Сведения об экспортируемом товаре состоят из даты отправки, наименования товара, страны, импортирующей товар и объема поставляемой партии в штуках (см. задание темы 11). Создать связный список с указателем EXPORT, содержащий сведения о некоторых экспортируемых товарах. Для заданного наименования товара создать связный список результатов REZ из сведений о странах и объеме экспортируемого товара по каждой стране. Вывести на экран содержимое связного списка REZ и подсчитать общий объем экспорта. Исходные данные находятся в текстовом файле EXPORT.TXT текущего каталога, причем сведения об одном товаре занимают одну строку.

Решение. Для удобства будем считать, что оба списка имеют одинаковую структуру: информационное поле D типа TData и поле next для связи с последующим узлом. Это позволит использовать общую процедуру Push для добавления нового узла в начало списка. Пусть TList – тип узла списка, а PtrList – тип ссылки на узел. Тогда определение этих типов примет вид:

Type

PtrList=^TList;

TList=Record

D: TData;

next: PtrList

End;

Следует обратить внимание на то, что при определении типа ссылки PtrList используется еще неопределенный тип TList. Это единственное исключение из правил описания языка Pascal. Определение типа TList должно располагаться ниже в этом же блоке.

Алгоритм процедуры Push для добавления нового узла с данными dat в начало списка First состоит из четырех шагов:

1) выделить из «кучи» область памяти для нового узла со ссылкой Р;

2) заполнить информационное поле D нового узла значением dat;

3) заполнить поле next нового узла значением ссылки First на старое начало списка;

4) установить ссылку First на новое начало списка (на новый узел со ссылкой Р).

Алгоритм решения задачи аналогичен рассмотренным в предыдущих заданиях (см. темы 11, 12). Для доступа к текущему узлу списка EXPORT используем указатель А, а для REZ – указатель В.

Программа примет вид:

Program ListOfZap;

Type TData=Record

Data:Record

Day,Month:Byte;

Year:Word

End;

Name:String[20];

Country:String[15];

Size:LongInt

End;

PtrList=^TList;

TList=Record

D: TData;

next: PtrList

End;

Var

ftext: Text;

dat: TData;

EXPORT, REZ, A, B, k: PtrList;

Itogo:LongInt;

Nam1:String[20];

ch:char;

i:integer;

Procedure Push(Var First: PtrList; dat: TData);

Var P: PtrList;

Begin

New(P); {Выделить из "кучи" область памяти для нового узла}

{ со ссылкой Р}

P^.D:=dat; { Заполнить информационное поле D нового узла}

{ значением dat }

P^.next:=First; { Заполнить поле next нового узла значением }

{ ссылки First }

First:=P { Установить First на новое начало списка }

End; {процедуры добавления нового узла в список}

Begin

Assign(ftext,'EXPORT.TXT'); { Назначениe для файлa}

Reset(ftext); { Открыть для чтения }

EXPORT:= Nil; { Инициировать пустой список EXPORT }

While Not EOF(ftext) Do { Пока не конец файла ftext, выполнять ...}

Begin

With dat.Data Do Read(ftext, Day, Month,Year); {Читать дату}

Read(ftext, ch); {"Сбросить" пробел-разделитель}

With dat Do

ReadLn(ftext, Name, Country, Size); {Продолжить чтение строки}

Push(EXPORT, dat) { Добавить узел с данными dat в список EXPORT}

End; {формирования списка EXPORT }

Close(ftext); {Закрыть текстовый файл ftext}

Write('Введите название данного товара ');

ReadLn(Nam1); {Ввести с клавиатуры название данного товара }

For i:=Length(Nam1)+1 To 20 Do

Nam1:=Nam1+' '; {Дополнение пробелами до 20 символов}

Itogo:=0;

REZ:=Nil; { Инициировать пустой список REZ }

A:=EXPORT;

While ANil Do {Пока не найден конец списка EXPORT}

Begin

If A^.D.Name=Nam1 Then

Begin Itogo:=Itogo+A^.D.Size;

k:=Nil; {Предположим, что в списке REZ нет узла со сведениями}

{ по текущей стране списка EXPORT }

B:=REZ;

While (BNil) and (k=Nil) Do

Begin

If B^.D.Country=A^.D.Country { Если страны совпадают, }

Then k:=B; { то k:= ссылку на текущий}

{узел списка REZ }

B:=B^.next; { Перейти на следующий узел списка REZ }

End;

If kNil Then

k^.D.Size:=k^.D.Size+A^.D.Size {Увеличить объем экспорта по}

{данной стране}

Else Push(REZ, A^.D); {Добавить узел с данными A^.D }

{в список REZ}

End;

A:=A^.next; { Перейти на следующий узел списка EXPORT }

End; { Список EXPORT обработан}

If REZ=Nil Then WriteLn('Данный товар не экспортируется')

Else

Begin

WriteLn('--------------------------------');

WriteLn('Страна-импортер : Объем поставок');

WriteLn('--------------------------------');

B:=REZ;

While (BNil) Do

Begin

With B^.D Do WriteLn(Country:15,' : ',Size:13);

B:=B^.next

End;

WriteLn('--------------------------------');

WriteLn(' Итого : ',Itogo:13)

End

End.

Для указанного в теме 12 содержимого файла EXPORT.TXT и товара ЗАЗ-Таврия результат выполнения программы аналогичен приведенному в теме 11.

Варианты заданий берутся из приведенных в теме 11 со следующими изменениями:

1) исходные данные расположены в некотором текстовом файле *.ТХТ, причем каждая запись занимает одну строку;

2) по текстовому файлу создается связный список исходных данных;

3) в процессе обработки связного списка исходных данных создается связный список результатов;

4) содержимое результирующего списка выводится на экран в виде соответствующей таблицы.

Литература

1. Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию. М., Наука, 1988.

2. Абрамов А.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. М., Наука, 1988.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.

4. Вирт Н. Алгоритмы и структуры данных. М., Мир, 1989.

5. Епанешников А., Епанешников В. Программирование в среде Turbo Pascal 7.0. М., Диалог-Мифи. 1993.

6. Д.Прайс. Программирование на языке Паскаль /практическое руководство /пер. с анг. М., Мир, 1987.

7. Турбо Паскаль 7.0. К., изд. Группа BHV, 2000 – 432с.

8. Турбо Паскаль 5.0. Справочное руководство. Калинин, 1989 (в 5-ти томах).

9. Меженный О.А. Turbo Pascal: учитесь программировать. – М., изд. Дом "Вильямс", 2001 – 448с.

10. Turbo Pascal: практикум. Немюгин С.А. СПб.: Питер, 2002 – 256с.

Учебное издание

МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению лабораторных работ

дисциплина ОП.05. «Основы программирования»

специальности 09.02.03 «Программирование в компьютерных системах»,

Донецк: ГПОУ «ДОНПЭК», 2015, с. 56

Волков Влалимир Александрович

________________________________________________________________

Подписано в печать 25.09.2015 г.. Формат 60х90 / 16. Бумага типографская. Офсетная печать. Условных. печать. л. 4,25. Тираж 50 экз.

________________________________________________________________

Издательство ГПОУ«ДОНЕЦКИЙ ПРОМЫШЛЕННО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»

г. Донецк, ул. Кобозева, 62

Напечатано: Центр информационных и компьютерных технологий

Донецкого национального университета, г. Донецк, ул. Университетская, 24

37