Тема №20 (время – 6 мин)

Тема: Анализ программы, содержащей подпрограммы, циклы и ветвления.

Что нужно знать:

· операции целочисленного деления (div) и взятия остатка (mod)

· как работают операторы присваивания, циклы и условные операторы в языке программирования

Пример задания:

Ниже записана программа. Получив на вход число , эта программа печатает два числа, и . Укажите наибольшее из таких чисел , при вводе которых алгоритм печатает сначала 3, а потом 7.

var x, L, M: integer;

Begin

readln(x);

L:=0; M:=0;

while x > 0 do begin

L:=L+1;

if M < (x mod 10) then begin

M:=x mod 10;

end;

x:= x div 10;

end;

writeln(L); write(M);

End.

Решение:

27) для решения задачи необходимо понять, что делает эта программа

28) если это не видно сразу, можно выполнить ручную прокрутку для какого-то простого числа, например, для числа 251:

29) можно догадаться, что в результате работы программы в переменной L окажется число цифр числа, а в переменной M – наибольшая цифра, но это предположение нужно постараться доказать

30) нужно вспомнить (и запомнить), что для целого числа остаток от деления на 10 (x mod 10) – это последняя цифра в десятичной записи числа, а целочисленное деление (x div 10) отсекает последнюю цифру, то есть из 123 получается 12

31) рассмотрим цикл, число шагов которого зависит от изменения переменной x:

while x > 0 do begin

...

x:= x div 10; { отсечение последней цифры }

end;

здесь оставлены только те операторы, которые влияют на значение x

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

33) на каждом шаге цикла переменная L увеличивается на 1:

L:=L+1;

других операторов, меняющих значение L, в программе нет; поэтому после завершения цикла в переменной L действительно находится количество цифр

34) теперь разберемся с переменной M, которая сначала равна 0; оператор, в котором она меняется, выглядит так:

if M < (x mod 10) then begin

M:=x mod 10;

end;

учитывая, что x mod 10 – это последняя цифра десятичной записи числа, получается что если эта цифра больше, чем значение M, она записывается в переменную M;

35) этот оператор выполняется в цикле, причем выражение x mod 10 по очереди принимает значения всех цифр исходного числа; поэтому после завершения циклам в переменной M окажется наибольшая из всех цифр, то есть наша догадка подтверждается

36) итак, по условию задачи фактически требуется найти наибольшее трехзначное число со старшей цифрой 7; очевидно, что это 777.

37) ответ: 777.

Ещё пример задания:

Ниже записана программа. Получив на вход число , эта программа печатает два числа, и . Укажите наибольшее из таких чисел , при вводе которых алгоритм печатает сначала 3, а потом 120.

var x, L, M: integer;

Begin

readln(x);

L:=0; M:=1;

while x > 0 do begin

L:=L+1;

M:= M*(x mod 8);

x:= x div 8;

end;

writeln(L); write(M);

End.

Решение:

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

а) переменная L с каждым шагом цикла увеличивается на 1

б) переменная x на каждом шаге цикла делится на 8 и остаток отбрасывается

поэтому можно сделать вывод, что в конце цикла переменная L будет равна количеству цифр введенного числа, записанного в восьмеричной системе счисления; таким образом, восьмеричная запись числа содержит ровно 3 цифры

2) выражение x mod 8 – это последняя цифра восьмеричной записи числа; на каждом шаге цикла переменная M умножается на эту величину, поэтому в результате в M будет записано произведение всех цифр восьмеричной записи введенного числа

3) по условию это произведение равно 120, то есть , где a, b и с – числа от 0 до 7 (которые в восьмеричной системе счисления записываются одной цифрой)

4) поскольку нам нужно наибольшее число, перебираем делители числа 120, начиная со старшей цифры – 7; видим, что 120 на 7 не делится, поэтому такой цифры в восьмеричной записи числа нет

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

6) делим 120 на 6, получаем 20; это число представляется как произведение 5 и 4, каждое из этих чисел записывается в виде одной восьмеричной цифры, то есть, они нам подходят

7) вспомним, что нас интересует максимальное число, поэтому цифры нужно выстроить в порядке убывания: 654₈

8) заметим, что мы получили число в восьмеричной системе, а ответ нужно дать в десятичной; переводим: 654₈ = 6·8² + 5·8¹ + 4·8⁰ = 492.

9) ответ: 492.

Поиск по сайту: