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

Ниже записана программа. Получив на вход число , эта программа печатает два числа, и . Укажите наибольшее из таких чисел , при вводе которых алгоритм печатает сначала 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. для решения задачи необходимо понять, что делает эта программа; повторяя рассуждения из предыдущего примера, выясняем, что

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

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

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

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

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

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

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

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

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

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

8. ответ: 428.