Разработка и анализ программ
.pdf6 |
Выход из 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