Разработка и анализ программ

6	Выход из pmax
11	Вызов pmax(c)						a
4	Вход в pmax						1
5	max < a FALSE
6	Выход из pmax
12	Вызов pmax(d)						a
4	Вход в pmax						10
5	max < a TRUE					10
6	Выход из pmax
13	Печать max(10)

Процедура, обменивающая значения двух переменных 1 program prim1;

2 var a, b: integer;

3 procedure swap(var c, d: integer);

4 var a: integer;

5begin

6a := c;

7c := d;

8d := a

9end;

10begin

11read(a, b);

12swap(a, b);

13write(a, b)

14end.

Таблица трассировки

№	Ход выполнения	a	b
10	Вход в prim1	?	?
11		1	20
12	Вызов swap(a, b)	c	d	a
5	Вход в swap
6				1
7		20
8			1
9	Выход из swap
13	Печать a, b (20, 1)
14	Выход из prim1

Определение максимального значения (пример с использованием функ-

11

ции)

program mmax4(input, output); var a, b, c, d, max: real; function fmax(a, b: real): real; begin

if a > b then fmax := a

else

fmax := b end;

begin

read(a, b, c, d);

max := fmax(fmax(fmax(a, b), c), d); write(‘max=’,max)

end.

Построение (разработка) программ

I.Спецификация

II.Метод пошагового уточнения (нисходящее проектирование)

III.Пример разработки программы. Таблица разработки.

I. Для того, чтобы начать писать программу, вам необходимо знать:

• назначение программы – точная, подробная формулировка задачи;

• какую информацию программа будет получать в качестве входных данных;

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

Последние два пункта описывают и приводят примеры входных и выходных данных.

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

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

1. Ввод входных данных.

2. Решение поставленной задачи.

3. Вывод результатов.

Далее достаточно сложные шаги, решение которых не очевидно, де-

12

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

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

–каждый раздел таблицы соответствует одному из этапов детализации;

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

–если вводятся в употребление новые переменные, они перечисляются в графе “Примечания” с указанием их типов и назначения.

Пример разработки программы.

Задача: Дан радиус окружности. Найти ее длину. Спецификация

1.Дан радиус окружности r. Составить программу для вычисления длины окружности по формуле l = 2 r.

2.Входные данные: вещественное число r, радиус окружности.

3.Выходные данные: вещественное число l, длина окружности.

Таблица разработки

Шаги разработки	Примечания
work1
begin
ввод входных данных
вычисление значения выражения
вывод результата
end.
ввод входных данных	переменная r (real) – ра-
read(r);	диус окружности
вычисление значения выражения	переменная L (real) –
L:=2*pi*r;	длина окружности
вывод результата
write (L)

Текст программы

1.Program work1;

2.var r, L: real;

3.begin

13

4.read(r);

5.L := 2 * pi * r;

6.write(L)

7.end.

5. Массивы

program array1(input, output);

{Поиск максимального элемента в массиве и его номера} const MaxLen = 5;

type vector = array[1..MaxLen] of real; var i, N, imax: integer;

max: real; a: vector;

begin

write(‘Размерность массива: ’); read(N);

writeln(‘Вводите элементы массива’); for i := 1 to N do

read(a[i]); max := a[1]; imax := 1;

for i := 2 to N do if a[i] > max then

begin

max := a[i]; imax := i

end;

writeln(‘Номер максимального элемента ’, imax); writeln(‘Значение максимального элемента ’, max:10:2) end.

program array2(input, output); {Определение суммы элементов массива} const MaxLen = 5;

type vector = array[1..MaxLen] of real; var i, N: integer;

Sum: real; a: vector;

begin

write(‘Размерность массива: ’); read(N);

14

writeln(‘Вводите элементы массива’); for i := 1 to N do

read(a[i]); Sum := 0.0;

for i := 1 to N do Sum := Sum + a[i]

writeln(‘Сумма элементов массива: ’, Sum:10:2) end.

program array3(input, output); {Произведение матриц} const MaxLen = 5;

type Matrix = array[1..MaxLen, 1..MaxLen] of integer; var N: integer;

A, B, C: Matrix;

procedure InputMatr(N: integer; var InMatr: Matrix); var i, j : integer;

begin

for i := 1 to N do for j := 1 to N do read(InMatr[i, j]); end;

procedure OutMatr(N: integer; Matr: Matrix); var i, j : integer;

begin

for i := 1 to N do begin

for j := 1 to N do write(Matr[i, j]:10); writeln

end end;

procedure MultMatr(M1, M2: Matrix; var Mrez: Matrix); var i, j, k, x : integer;

begin

for i := 1 to N do for j := 1 to N do begin

x := 0;

for k := 1 to N do

x := x + M1[i, k] * M2[k, j]; Mrez[i, j] := x

15

end end; begin

write(‘Размерность массивов: ’); read(N);

writeln(‘Вводите элементы матрицы A’); InputMatr(N,A);

writeln(‘Вводите элементы матрицы B’); InputMatr(N,B);

MultMatr(A, B, C); writeln(‘Результат:’); OutMatr(N, C); end.

Примеры реализации некоторых алгоритмов

Пример 1. Определить, принадлежит ли точка D треугольнику ABC. Треугольник задан координатами своих вершин A, B, C.

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

Таблица разработки

Шаги разработки	Примечания
Program Treug(input, output);
begin
Ввод данных;
Определение принадлежности точки треугольнику;
Печать результата
end.
Ввод данных	xA, yA, ..., xD, yD:
read(xA, yA);	real – координаты то-
read(xB, yB);	чек
read(xC, yC);
read(xD, yD)
Определение принадлежности точки треугольнику	OneSide() - функция,
+ печать результата	принимает в кач-ве
if OneSide((AB), C, D) AND OneSide((BC), A, D)	параметров коорди-
AND OneSide((AC), B, D) then	наты двух точек, об-
writeln(‘Точка принадлежит треугольнику’)	разующих прямую и
else	двух проверяемых

16

writeln(‘Точка не принадлежит треугольнику’)	точек. Возвращает
	логическое значение
	TRUE если точки
	нах-ся с одной сторо-
	ны прямой и FALSE
	в противном случае.
function OneSide(x1, y1, x2, y2, x3, y3, x4, y4: real):
Boolean
begin
Определение параметров прямой y = kx + b;
Проверка принадлежности точек одной полуплос-
кости
end
Определение параметров прямой y = kx + b	k, b: real
k := (y2 – y1) / (x2 – x1);
b := y1 – k * x1
Проверка принадлежности точек одной полуплос-
кости
OneSide := ((y3 >= k * x3 + b) AND (y4 >= k * x4 +
b)) OR ((y3 <= k * x3 + b) AND (y4 <= k * x4 + b))

Таким образом, программа будет выглядеть следующим образом: Program Treug(input, output);

var xA, yA, xB, yB, xC, yC, xD, yD: real;

function OneSide(x1, y1, x2, y2, x3, y3, x4, y4: real): Boolean; var k, b: real;

begin

k := (y2 – y1) / (x2 – x1); b := y1 – k * x1;

OneSide := ((y3 >= k * x3 + b) AND (y4 >= k * x4 + b)) OR ((y3 <= k * x3 + b) AND (y4 <= k * x4 + b))

end; begin

write(‘Координаты точки A: ’); read(xA, yA); write(‘Координаты точки B: ’); read(xB, yB); write(‘Координаты точки C: ’); read(xC, yC);

17

write(‘Координаты точки D: ’); read(xD, yD);

if OneSide(xA, yA, xB, yB, xC, yC, xD, yD) AND OneSide(xB, yB, xC, yC, xA, yA, xD, yD) AND OneSide(xA, yA, xC, yC, xB, yB, xD, yD) then

writeln(‘Точка принадлежит треугольнику’) else

writeln(‘Точка не принадлежит треугольнику’) end.

Пример 2. В вычислительной технике (в частности, в микрокалькуляторах) широко применяется следующий алгоритм вычисления квадратного корня из числа a. Берется какое-либо (обычно равное a) приближение xn. Следующее приближение xn+1 определяется по формуле:

		1			a
xn 1
			xn
	2				xn

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

Программа будет иметь следующий вид: Program Koren(input, output);

var a, x, xn, eps: real; begin

write(‘Задайте число ’); read(a);

write(‘Задайте точность ’); read(eps);

x := 0.0; xn := a;

while abs(x – xn) > eps do begin

x := xn;

xn := (xn + a/xn) / 2.0; end;

writeln(‘Квадратный корень равен ’, xn) end.

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

18

x

x3

x5

x7

x9

sinx

...

1!

3!

5!

7!

9!

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

Program sinus(input, output); var x, eps, sinx, xn: real;

n: integer; begin

write(‘Задайте число x ’); read(x);

write(‘Задайте точность ’); read(eps);

sinx := x; xn := x; n := 1;

while abs(xn) > eps do begin

xn := -1.0 * sqr(x) * xn / ((n + 1) * (n + 2)); n := n + 2;

sinx := sinx + xn end;

writeln(‘Значение синуса равно: ’, sinx) end.

Задание 1. Вычисления по формулам

Составить подробную спецификацию программы с примерами входных и выходных данных. Разработать программу, используя таблицы разработки. Выполнить трассировку программы. Ввести программу в компьютер, сравнить результаты трассировки и работы программы.

1.Дана длина ребра куба. Найти объем куба и площадь его боковой поверхности.

2.Даны два действительных положительных числа. Найти среднее ариф-

метическое и среднее геометрическое этих чисел.

3 Даны два действительных числа. Найти среднее арифметическое чисел и среднее геометрическое их модулей.

4.Даны катеты прямоугольного треугольника. Найти его гипотенузу и площадь.

5.Смешано v1 литров воды температуры t1 с v2 литрами воды температуры t2. Найти объем и температуру образовавшейся смеси.

6.Определить периметр правильного n-угольника, описанного около ок-

19

ружности радиуса r.

7.Три сопротивления R1, R2, R3 соединены параллельно. Найти эквивалентное сопротивление цепи.

8.Определить время падения камня на поверхность земли с высоты h.

9.Дана сторона равностороннего треугольника. Найти площадь этого треугольника.

10.Вычислить период колебаний маятника длины l.

11.Определить силу притяжения F между телами массой m1 и m2, находящимися на расстоянии r друг от друга.

12.Дана гипотенуза и катет прямоугольного треугольника. Найти второй катет и радиус вписанной окружности

13.Известна длина окружности. Найти площадь круга, ограниченного

этой окружностью

14.. Найти площадь кольца, внутренний радиус которого равен r1, а внешний – заданному числу r2 (r2 > r1).

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

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

17.Найти сумму членов арифметической прогрессии a, a + d, ..., a + (n – 1)d по данным значениям a, d, n.

18.Вычислить расстояние между двумя точками с координатами x1, y1 и

х2, у2

19.Найти площадь сектора круга, радиус которого равен r, а дуга содержит заданное число радиан .

20.Даны действительные положительные числа а, b, с. По трем сторонам с длинами a, b, c можно построить треугольник.. Найти углы треугольника.

21.Определить периметр правильного n-угольника, вписанного в окружность радиуса r.

Задание 2

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

Содержание отчета:

1.Задание

2.Текст программы

3.Таблица трассировки

20