- Функциональный подход к анализу программ
- уметь анализировать программу, выполняя алгоритм пошагово (с использованием компьютера или вручную), определять результат выполнения алгоритма при заданных исходных данных с помощью функционального подхода
- уметь правильно подбирать способ анализа под конкретную задачу
- Для чего нужно анализировать алгоритм или программу?
- Какие способы анализа программ вам известны?
Функциональный подход к анализу программ
Для анализа и проверки правильности работы программы используют трассировочные таблицы (таблицы значений). Но в ситуации, когда требуется выполнить много действий (команд), составлять такую таблицу затруднительно, т. к. она получается слишком большой. В таких случаях вместо трассировочной таблицы принято использовать функциональный подход.
Функциональный подход позволяет отнестись к программе как к функции, которая что-то получает на вход и что-то выдаёт на выход («чёрный ящик»). Т. е., не вникая в каждый шаг, позволяет понять, как именно работает программа.
Алгоритм:
- Выясняется, какую функцию выполняет каждая переменная в программе.
- Анализируются циклы, условия выхода из циклов, сколько раз они выполняются.
- Вычисляется результат работы программы.
Пример 1
Определим значения переменной a, полученной в результате выполнения программы:
var
a, b :integer;
begin
a := 0;
b := 200;
while b < 500 do
begin
b := b+10;
a := a+2;
end;
writeln(a);
end.
Решение
Заметим, что в программе присутствует цикл while, который будет выполнять более 100 шагов, т. е. использовать трассировочную таблицу в данном случае невозможно.
Воспользуемся функциональным подходом.
- Попытаемся понять, какую функцию в программе выполняет каждая переменная. Начальное значение переменной a = 0. Далее она увеличивается на 2 при каждом повторе цикла. Т. е. если цикл выполняется один раз, то а = 2; если 2 раза, то а = 4; если 3 раза, то а = 6. Видим закономерность: а = 2 * k, где k — количество повторов цикла.
- Выясним, когда произойдёт выход из цикла. Переменная b отвечает за количество повторов цикла, т. к. она находится в условии продолжения цикла. Начальное значение b = 200, далее на каждом повторе к b добавляется 10. Т. е. при первом повторе b = 210; при втором — 220 и т. д., пока не дойдём до 500.
Рассчитаем количество повторов цикла. (500 − 200) / 10 = 30.
Т. о. результат работы программы будет 2 * 30 = 60.
Ответ: 60.
Упражнение 1
Определите значения переменной sum в результате выполнения следующей программы, используя функциональный подход:
Var sum,r : integer;
begin
sum := 1;
r := 800;
while r >= 50 do
begin
sum := sum + 2;
r := r - 20;
end;
writeln(sum);
end.
Пример 2
Определим минимальное значение переменной n, если в результате выполнения программы были выведены числа 3 и 7:
var
a,b,n :integer;
begin
readln(n);
a:=0;
b:=0;
while n>0 do
begin
a:=a+1;
b:=b + (n mod 10);
n:=n div 10;
end;
writeln(a);
writeln(b);
end.
Решение
Особенностью задачи является то, что движение идёт от конца к началу, т. к. нам известны переменные a и b, но неизвестно, какое именно число было введено изначально и его нужно найти.
Применим функциональный анализ. Определим функции переменных, входящих в программу. Переменная n вводится с клавиатуры, и далее меняется внутри цикла командой n:=n div 10. Т. е. при каждом повторе цикла переменная уменьшается в 10 раз и дробная часть отбрасывается. Т. е. число n «лишается» последней цифры справа.
Начальное значение переменной a = 0 и далее при каждом повторе цикла она увеличивается на единицу. Т. е. можно сказать, что переменная является счётчиком, фиксирующим количество повторов цикла и одновременно считающих количество «отделившихся» от n цифр. На выходе a = 3 (по условию задачи), значит цикл выполнился 3 раза. И значит наше начальное число n является трёхзначным.
Начальное значение переменной b = 0. При каждом повторе цикла переменная b меняется т. о.: b:=b + (n mod 10). Т. е. в переменной фиксируется сумма цифр числа n. На выходе b = 7. Остаётся найти минимальное трёхзначное число, сумма цифр которого равна 7.
Это число 106.
Ответ: 106.
Упражнение 2
- Для примера 2 определите максимальное значение переменной n, если в результате выполнения программы были выведены числа 3 и 7.
- Для примера 2 определите минимальное значение переменной n, если в результате выполнения программы были выведены числа 3 и 5.
Упражнение 3
Определите минимальное и максимальное значения переменной n, если в результате выполнения программы были выведены числа 3 и 5:
var
a,b,n :integer;
begin
readln(n);
a:=0;
b:=1;
while n>0 do
begin
a:=a+1;
b:=b * (n mod 10);
n:=n div 10;
end;
writeln(a);
writeln(b);
end.
Итоги
- Для анализа программы используют трассировочные таблицы, в которых фиксируется пошаговое выполнение программы. Но если шагов слишком много, рекомендуется использовать функциональный подход.
- Функциональный подход состоит в анализе переменных, их роли, циклов, условия выхода из циклов, на основе чего находится решение.
Контрольные вопросы
- В чём отличие анализа с помощью реализации трассировочной таблицы от функционального подхода?
- Какой способ анализа программы вы считаете более универсальным?
Упражнение 1
77
Упражнение 2
- 700 2. 104
Упражнение 3
115, 511
