ЕГЭ-информатика-22

Образец решения

Задание № 1. Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 21, а потом 3.

Бейсик

DIM X, L, M AS INTEGER
 INPUT X
 L = 1
 M = 0
 WHILE X > 0 
    M = M + 1 
     IF X MOD 2 <> 0 THEN
      L = L * (X MOD 8)  
     END IF 
 X = X \ 8
 WEND
 PRINT L
 PRINT M

Python

x = int(input())
 L = 1
 M = 0
 while x > 0: 
      M = M + 1 
      if x % 2 != 0: 
           L = L * (x % 8) 
      x = x // 8
 print(L)
 print(M)

Паскаль

var x, L, M: integer;
 begin 
     readln(x);
     L := 1; 
     M := 0;
     while x>0 do 
    begin
         M :=M+1;
         if x mod 2 <> 0 then 
            L := L * (x mod 8); 
         x := x div 8; 
    end;
    writeln(L)
    writeln(M)
 end.

Алгоритмический язык

алг
нач
     цел x, L, M 
     ввод x 
     L := 1 
     M := 0 
    нц пока x > 0 
        M := M + 1 
         если mod(x,2) <> 0 
            то
             L := L * mod(x,8) 
        все 
        x := div(x,8) 
     кц 
     вывод L, нс, M 
 кон

С++

#include <iostream> 
using namespace std;
 
 int main(){ 
     int x, L, M; 
     cin >> x; 
     L = 1; 
     M = 0; 
     while (x > 0) { 
          M = M + 1; 
          if(x % 2 != 0) { 
             L = L * (x % 8); 
          }
          x = x / 8; 
        }
        cout << L << endl << M << endl; 
        return 0;
 }

Решение:

1. Переводим программу на человеческий язык. Выбираем программу, написанную на любом языке. Я выберу Python:

• x = int(input()) — введите число х;
• L = 1 — начальное значение числа L, при выполнении алгоритма оно будет меняться;
• M = 0 — начальное значение числа L, при выполнении оно будет меняться;
• while x > 0:     - цикл будет выполняться пока х>0;
• M = M + 1     - если число х>0, то значение числа М увеличивается на 1;
• if x % 2 != 0:   - если остаток от деления числа х на 2 не равен 0 (то есть число не делится на 2 нацело), то  L = L * (x % 8)   - новое значение числа L получается при умножении старого значения L на остаток от деления числа х на 8;
• если остаток от деления числа х на 2 равен 0 (х-четно), то изменений с L не происходит;
• x = x // 8 — числу х присваивается новое значение, которое равно целой части от деления предыдущего значения числа х на 8;
• print(L) — вывод на экран значения L (по условию задачи — 21)
• print(M) — вывод на экран значения М (по условию задачи — 3).

2. Анализируем условие:

• так как М возрастает от 0 до 3, цикл выполняется 3 раза, то есть делить число х на 8 мы будем 3 раза.
• что мы знаем про L
  • получается в результате умножения остатков от деления Х на 8;
  • равно 21,
  • значит множители должны быть равны 3 и 7;
  • то есть остатки от деления должны быть равны или 3, или 7. 

3. От какого числа будем отталкиваться в решении:

• число должно будет 3 раза разделиться на 8, поэтому искать нужно около числа 8•8•8=512.
• число 512 не подходит, так как все остатки при делении на 8 будут равны 0, а нам нужны или 3, или 7.
• так как по условию нужно найти большее число, то проверим числа чуть большие 512; возьмем числа 515 (даст остаток 3) и 519 (даст остаток 7). 

3. Составим таблицу результатов выполнения алгоритма для 515:

• вывод: третьим шагом мы не получим L=21;
• делаем так же вывод, что большие числа не дадут возможности получить третьим шагом L=21 (для неверующих совет, просто просчитайте несколько бОльших чисел, так же поступите на экзамене — это нормально).

4. Будем брать числа меньшие 512, начнем с 511 (остаток от деления на 8 = 7) и 507 (остаток от деления на 8 = 3). Составляем таблицы:

• вывод: третьим шагом мы не получим L=21;

• вывод: третьим шагом мы не получим L=21.

5. Составим таблицу результатов выполнения алгоритма для чисел 503 (остаток от деления на 8 = 7) и 499 (остаток от деления на 8 = 3):

• вывод: третьим шагом мы не получим L=21.

• вывод: третьим шагом мы получили L=21;
• четвертого шага не будет, так как целая часть от деления 7 на 8 равно 0, то есть следующее значение х=0, но условие выполнения алгоритма х>0;
• так как алгоритм больше не выполняется, то на экран выводятся числа 21 и 3.

Ответ: 499.