Анализ программы с циклами и ветвлениями
Задание на анализ программы с циклами и ветвлениями может содержать
· оператор x:=div(x,10), выполнение которого в цикле способствует отбрасыванию последней цифры в числе;
· операцию mod(x,10), которая определяет последнюю цифру в числе;
Таким образом можно выделить все цифры в числе и найти их сумму, произведение, максимальную, минимальную цифру числа. В задаче могут быть реализованы различные алгоритмы, в том числе алгоритм Евклида, другие операции, например при условии четности или нечетности цифры в числе. Необходимо протестировать алгоритм на каком-нибудь числе, определить, что происходит с переменными в алгоритме и применить алгоритм согласно условиям задачи.
Рассмотрим несколько таких задач более подробно:
Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 11, а потом 7.
var x, a, b, c: integer;
begin
readln(x);
a := 0; b := 0;
while x>0 do
begin
c := x mod 10; определение последней цифры в числе
a := a+c; в переменной а хранится сумма цифр числа
if c>b then b := c; в переменной b хранится максимальная цифра числа
x := x div 10 отбрасывание последней цифры в числе
end;
writeln(a); write(b)
end.
Максимальная цифра в числе по условию равна 7, сумма цифр 11, поэтому наименьшее число x будет равно 47. Возможно введение чисел 74, 137, 317 и др. которые также будут давать искомый результат, но они >47.
Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное число x, этот алгоритм печатает число R. Укажите такое число x, при вводе которого алгоритм печатает двузначное число, сумма цифр которого равна 14. Если таких чисел x несколько, укажите наименьшее из них.
var
x,d,R: longint;
begin
readln(x);
R := 0;
while x>0 do
begin
d := x mod 10;
R := 10*R + d;
x := x div 10
end;
writeln(R)
end.
Алгоритм выделяет цифры числа и составляет число, обратное исходному. Например для числа 123, число R будет иметь вид 321. Наименьшее двузначное число, сумма цифр которого равна 14 равно 59.
Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наименьшее число x, при вводе которого алгоритм печатает сначала 3, а потом 6.
var x, L, M: integer;
begin
readln(x);
L := 0;
M := 0;
while x > 0 do
begin
M := M + 1; количество "витков" цикла
if x mod 2 <> 0 then
L := L + 1; количество раз, когда число х становится нечетным в результате работы алгоритма
x := x div 2; замена числа на результат целочисленного деления его на 2
end;
writeln(L);
writeln(M);
end.
Т.к по условию количество витков цикла равно 6, то можно предположить, что число целочисленно делилось на два 6 раз. При этом в процессе работы алгоритма оно становилось нечетным три раза.
Начнем свой анализ с числа 32, т.к. 32=25, для него промежуточные значения будут равны соответственно 16,8,4,2,1. Из них только последнее число 1 будет нечетным. Попробуем увеличивать число, возьмем 33, получим те же самые промежуточные значения 16,8,4,2,1, но L уже будет равно 2 (два числа 33 и 1 будут нечетными). Число 34 сформирует цепочку 17,8,4,2,1 и L также будет равно 2. А вот число 35 дает нам L=3.