Информатика ЕГЭ 22 задание разбор

22-е задание: «Программирование: циклы и ветвления»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 7 минут.

Проверяемые элементы содержания: Умение анализировать алгоритм, содержащий ветвление и цикл

До ЕГЭ 2021 года — это было задание № 20 ЕГЭ

Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ

Содержание:

Задания на работу с цифрами чисел в различных системах счисления
Задания на алгоритм Евклида и поиск НОД

Задания на работу с цифрами чисел в различных системах счисления

Задание 22_1:

22_1:

Ниже записан алгоритм.
Получив на вход число x, этот алгоритм печатает число L.

Укажите наибольшее нечетное число x, при вводе которого алгоритм печатает 53.

var x, L, M, D: integer;
begin
  readln(x);
  D:=x;
  L:=23;
  M:=141;
  while L<=M do
  begin
    L:=L+D;
    M:=M-3*D;
  end;
  writeln(L);
end.

Подобные задания для тренировки

Ответ: 15

✍ Показать решение:

✎ Решение с использованием программирования:
Pascal:

var
  x, L, M, D: longint;
 
begin
  x := 1000;
  while true do
  begin
    D := x;
    L := 23;
    M := 141;
    while L <= M do
    begin
      L := L + D;
      M := M - 3 * D;
    end;
    if (l = 53) and (x mod 2 <> 0) then 
    begin
      print(x); break;
    end;
    x -= 1;
  end;
end.

✎ Аналитическое решение:
Разберем решение по одному из возможных вариантов выполнения данного задания.
Рассмотрим алгоритм:

Результатом программы является вывод L.
Цикл перестанет работать, когда L станет больше M (т.к. while L<=M).
D в программе - это и есть искомый x (D:=x;).
В цикле оператор L:=L+D работает, как сумматор: L накапливает в себе сумму всех D, тогда как D в нашей задаче не меняется и равна введенному x.
Сумматор (L) до цикла обычно обнуляется, сделаем это: т.е. в строке 5 вместо L:=23 представим, что L:=0. Тогда и условие задачи поменяется: т.е. вместо указанного в условии числа 53 программа выводит L равное 53-23 = 30. А в условии цикла M также изменит свое значение на 141-23=118:

...
  L:=23;
  M:=141;
  while L<=M do // L<=118 для первой итерации
  begin
    L:=L+D;
    M:=M-3*D;
  end;
  writeln(L); // выводится L = 30
end.

Так как по заданию необходимо найти наибольший x, то представим, что он равен как раз 30:

L = L + D => L = 0 + 30 => L = 30

Но число 30 - четное, а по условие необходимо нечетное x.
Значит, одного прохождения цикла недостаточно.
Предположим, что цикл имеет две итерации. За два прохождения цикла L увеличится на 2*D, то есть нужно взять такое D, чтобы 2*D было равно 30:

30 / 2 = 15 
То есть D = x = 15

Проверим:

D=15         1 проход       2 проход      
L:=L+D:       0+15=15        15+15=30       
M:=M-3*D:   118-3*15=73    73-3*15 = 28   
L<=M:        да: 15<=73    нет: 30 > 28

Т.е. D=15 полностью подходит, и это наибольшее возможное число при данных условиях.

📹 Видео (теоретическое решение)

📹 Видеорешение на RuTube здесь

Задание 22_9:

22_9:

Ниже записан алгоритм.
Получив на вход число x, этот алгоритм печатает число L.

Укажите наибольшее нечетное число x, при вводе которого алгоритм печатает 125.

var x, L, M, D: integer;
begin
  readln(x);
  D:=x;
  L:=17;
  M:=70;
  while L<=M do
  begin
    L:=L+2*D;
    M:=M+D;
  end;
  writeln(L);
end.

Ответ: 27

Показать решение:

📹 Видео

📹 Видеорешение на RuTube здесь

Задание 22_2:

22_2:

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает S. Известно, что 100 ≤ x ≤ 200.

Укажите наибольшее допустимое число x, при вводе которого алгоритм распечатает 30.

var x,A,B,D,S: integer;
begin
  readln(x);
  B:= x;
  A:= 9;
  D:= x;
  S:= 0;
  while (D div 2)>0 do
  begin
    if (D mod 2) = 1 then
      S:= S + 1
    else
      S:= S + A;
    D:= D div 2;
  end;
  writeln(S);
end.

Подобные задания для тренировки

Ответ: 120

✍ Показать решение:

✎ 1 способ (аналитический):

В начале программы вводится x, две переменные - B и D присваивают значение введенного x. Переменной A присваивается значение 9, а переменная S обнуляется.
Далее следует цикл, который зависит от переменной D (равной x): пока x div 2 > 0 выполняется тело цикла. Т.е. пока x, деленный целочисленно на 2, больше нуля.
В теле цикла происходит увеличение переменной S либо на 9 (А:=9), либо на 1 в зависимости от четности значения D. Т.е. переменная S увеличивается на 9 в случае, если очередное значение D - четное и увеличивается на 1, если очередное значение D - нечетное.
В конце цикла D целочисленно делится на 2 (D := D div 2).
По условию программы S должно быть равно 30. Посчитаем максимальное количество итераций цикла: 2ⁿ <= 200, т.е. n = 7 (максимальное значение D - 200 - делим целочисленно на 2, пока это возможно). При этом минимальное количество итераций - 6 (2ⁿ >=100, т.е. n = 6)
За 7 или 6 итераций цикла необходимо получить S = 30, каждую итерацию цикла, увеличивая S либо на 1, либо на 9. Рассмотрим варианты:

30 = 9 + 9 + 9 + 1 + 1 + 1  ->  (получаем 6 итераций, что соответствует действительности)
30 =  9 + 9 + 12 * 1 (если взять две девятки, то цикл должен работать 14 раз 
(9 + 9 + [12 единиц]), а это невозможно)

Из 6 итераций имеем: 3 итерации с D - нечетным (когда s = s + 1) и 3 итерации с D - четным (когда s = s + 9)
Четность чисел в двоичной системе счисления зависит от младшего бита: если младший бит = 0, то число четное, если 1, то число нечетное. Поскольку нам необходимо найти наибольшее x, то необходимо в трех старших битах данного числа, выраженного в двоичной системе счисления, поместить 1, а в остальных трех битах разместить 0. При этом необходимо не забыть про еще один старший бит равный 1 (в итерациях его нет, т.к. это последняя единица, которая уже не удовлетворяет условию цикла: условие цикла ложно while (1 div 2) > 0 - ложь):

1111000₂ = 120₁₀
первая единица будет стоять всегда, она не участвует в итерациях цикла

Проверка:
120| 0  - соответствует s + 9
 60| 0  - соответствует s + 9
 30| 0  - соответствует s + 9
 15| 1  - соответствует s + 1
  7| 1  - соответствует s + 1
  3| 1  - соответствует s + 1
  1|

✎ 2 способ:

Значение искомого x присваивается сразу двум переменным B и D, но B более нигде не используется, поэтому забудем про нее. D - это x.

В цикле:

D mod 2 - это крайняя справа цифра числа в двоичной системе счисления (младший разряд); т.е.:

например, если D = 5₁₀ = 101₂, то D mod 2 = 1 (101)

в цикле есть сумматор S, результат которого выводится в программе (результат 30), и который накапливает в себя значения по следующему принципу:
если указанная крайняя цифра = 1, то в S добавляется 1, если крайняя цифра = 0, то в S добавляется 9 (А = 9);
последнее действие цикла D:= D div 2 - это отсечение крайнего младшего разряда числа D в двоичной системе счисления, т.е.:

если было D = 5₁₀ = 101₂, то стало D = 10₂

условие цикла: пока D при целочисленном делении на 2 больше 0 (while (D div 2)>0);
анализ алгоритма показывает, что вводимый x можно рассматривать в двоичной системе счисления. Поскольку сумматор S выводит в результате число 30, то можно понять, как накапливается это число в S:

30 = 9 + 9 + 9 + 1 + 1 + 1  ->  (получаем 6 итераций цикла)

поскольку цифра 9 прибавлялась 3 раза и единица прибавлялась 3 раза, значит, в двоичной записи исходного числа D было 3 цифры 0 и три цифры 1. Чтобы получить наибольшее x, как указано в задании, расположим в старших битах единицы, а в младших 0:

важно не забыть крайнюю слева цифру 1, которая останется не учтенной в цикле, так как условие при последней единице не выполняется:

при оставшемся D = 1 условие while (1 div 2) > 0 не работает, 
поэтому добавляем еще старший разряд "1"
таким образом, получаем число в двоичной системе: 1111000

переведем в десятичное представление:

64 32 16  8  4  2  1
1  1   1  1  0  0  0   = 64 + 32 + 16 + 8 = 120₁₀

📹 Видео 1 (долгий способ)
📹 Видеорешение на RuTube здесь

📹 Видео 2
📹 Видеорешение на RuTube здесь

Задание 22_3:

22_3:

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M.

Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 8.

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
      M:=x mod 10;
    x:=x div 10;
  end;
  writeln(L);writeln(M);
end.

Подобные задания для тренировки

Ответ: 88

✍ Показать решение:

Рассмотрим алгоритм работы с L:

В конце программы алгоритм выводит значение L, равное 2 (по условию). В цикле L - это счетчик, увеличивающийся каждую итерацию цикла (каждое прохождение цикла) на 1.
Таким образом, цикл работает два раза.
В цикле x постоянно уменьшается на 1 разряд, т.е. от него отсекается цифра справа (x:=x div 10):

например, x = 243
после выполнения x:=x div 10 получаем
х = 24

Так как цикл работает два раза, значит x - двухзначное число, т.е. после двух проходов (итераций) цикла условие цикла перестало работать (x стало <= 0).

Рассмотрим работу с M в цикле:

В первую итерацию цикла М всегда заменится на значение x mod 10, так как изначально М = 0.
Из предыдущего пункта имеем, что M - это наименьшая цифра числа:

например, x = 243
после выполнения M := x mod 10; получаем
1 шаг: М = 3
2 шаг: М = 3
3 шаг: М = 2

В результате работы программы на экран выводится М = 8.

Рассмотрим две цифры числа x путем подстановки:

Поскольку по условию нам нужно наибольшее x, то попробуем в единицы записать число 8:

? 9

В таком случае во второй итерации цикла условие в цикле M < (x mod 10) не будет работать, и программа распечатает 9 (вместо 8). Т.е. 9 не походит:

if M  < (x mod 10) then
      M:=x mod 10;
1 шаг: 
if 0  < (9) then
      M:=9;
2 шаг:
if 9 < (любая цифра) then ... 
Условие не работает, программа распечатает М = 9. Не подходит!

Поставим вместо разряда единиц число 8:

? 8

После первой итерации цикла M = 8 (по условию нам подходит):

if M  < (x mod 10) then
      M:=x mod 10;
1 шаг: 
if 0  < (8) then
      M:=8;

Теперь рассмотрим первую цифру числа x:

9 8
если она равна 9 (то есть число 98), 
то М станет = 9 (а нам необходимо, чтобы осталось 8):

1 шаг: 
if 0  < (8) then
      M:=8;
2 шаг:
if 8 < 9 then ... 
Условие работает, программа распечатает М = 9. Не подходит!

Возьмем цифру 8 (88):

8 8
1 шаг: 
if 0  < (8) then
      M:=8;
2 шаг:
if 8 < 8 then ... 
Условие не работает, программа распечатает М = 8. Подходит!

Наибольшее х = 88.

📹 Видео

📹 Видеорешение на RuTube здесь

Задание 22_5:

22_5. Демоверсия ЕГЭ 2018 информатика:

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M.

Укажите наименьшее число x, при вводе которого алгоритм печатает сначала 5, а потом 7.

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;
end;
writeln(L);
writeln(M);
end.

Типовые задания для тренировки

Ответ: 79

✍ Показать решение:

✎ Способ 1:

В цикле:

Наличие операторов x mod 2 и x div 2 говорит о том, что эту задачу можно решать, представляя x в двоичной системе счисления.
В цикле есть счетчик M, который увеличивается на единицу и в конце программы будет соответствовать количеству итераций цикла. Таким образом, имеем 7 проходов цикла.
Условие if x mod 2 <> 0 проверяет на нечетность младший разряд числа в двоичной системе:

например, если было x = 5₁₀ = 101₂, 
то if x mod 2 <> 0 проверяет if 1 <> 0

Если в младшем разряде стоит единица (в двоичной системе число состоит только из 1 и 0), то срабатывает счетчик L, который увеличивается на единицу.
В строке x := x div 2; отсекается младший разряд двоичного представления значения x, т.е.:

если было, например, x = 5₁₀ = 101₂, то стало x = 10₂

Таким образом, счетчик L подсчитывает количество единиц в двоичной записи числа. Так как в результате выводится L = 5, то в двоичной записи числа 5 единиц.
Так как цикл работает 7 раз, и в каждой итерации от числа в двоичной записи отсекается один разряд, то имеем 7 разрядов (цифр) в числе.
Итого, в двоичной записи 5 единиц и 2 нуля. Для получения наименьшего x (по заданию) расположим цифры следующим образом:

1001111₂ = 64 + 8 + 4 + 2 + 1 = 79₁₀

✎ Способ 2 (длительный, аналитический):

Для начала рассмотрим алгоритм программы:

В начале программы вводится x, и обнуляются две переменные - L и M.
Далее следует цикл, который зависит от переменной x: пока x > 0 выполняется тело цикла.
В теле цикла каждый его шаг происходит увеличение переменной M на единицу. Т.е. переменная M - это счетчик, соответственно, его значение по завершению работы цикла будет соответствовать количеству шагов (итераций) цикла.
В конце программы печатается сначала L, потом M. Т.е. L должно быть равно 5, а M = 7. Раз M будет равно 7, то из предыдущего пункта видим, что цикл имеет 7 шагов, т.е. 7 итераций.
L - это тоже счетчик, но из условия if x mod 2 <> 0 видим, что счетчик L подсчитывает количество нечетных промежуточных x. Т.е. x в цикле постоянно меняется, а L проверяет x и в случае нечетного значения увеличивается на единицу. В программе L должно стать 5.
В цикле x делится целочисленно на 2: x := x div 2
Поскольку цикл завершит работу, когда x = 0, то последним шагом будет x = 1 div 2 = 0. Т.е. в предпоследнем шаге x = 1.
Решим данную задачу с конца, проследив все итерации цикла. Получается, что из предыдущего шага в следующий шаг x изменяется по двум правилам, назовем их командами:

1. x*2 -> если предыдущий x - четный, 
например 4 div 2 - обратное действие 2*2 = 4

2. x*2+1 -> если предыдущий x - нечетный, 
например 5 div 2 - обратное действие 2*2+1 = 5

Так как L в результате равно 5, значит, в программе 5 команд № 2 и 2 команды №1 (7-5 = 2)
Нарисуем дерево команд и получающиеся значения, начиная с последней итерации цикла до начальной итерации. Т.е. начнем с завершения цикла, когда x стал = 0:

Вниз уходят команды, дающие четные значения x, а вверх - нечетные. Поскольку нам необходимо найти наименьший x, то "выгоднее" проследить нижние ветви дерева, т.к. они в результате дают меньшие значения.
Из дерева видим, что первая команда - это команда 2. В итоге осталось 4 команды № 2 и 2 команды № 1.
Нам выгодно с самого начала "двигаться" по дереву, используя команды №1 (чтобы x был наименьшим). Поэтому вторая и третья ветвь будут соответствовать команде №1. Поскольку первых команд должно быть только две, остальные команды будут №2.
Итого получаем следующий путь по дереву, в результате которого x становится равным 79.

📹 Видео 1(быстрый способ)

📹 Видеорешение на RuTube здесь

📹 Видео 2 (аналитическое решение)

📹 Видеорешение на RuTube здесь

Задание 22_6:

22_6: Досрочный егэ по информатике 2018, вариант 1:

Укажите наибольшее десятичное число, при вводе которого на экране сначала напечатается 3, а затем 6.

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

Типовые задания для тренировки

Ответ: 425

✍ Показать решение:

Результат: 425

📹 Видео

📹 Видеорешение на RuTube здесь

Задание 22_7:

22_7:

Получив на вход натуральное десятичное число х, этот алгоритм печатает два числа: L и М.
Укажите наименьшее число х, при вводе которого алгоритм печатает сначала 42, а потом 4.

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

Ответ: 567

✍ Показать решение:

В конце программы на экран выdодится сначала значение переменной L, затем M. Т.е. согласно заданию, получается что:

в конце программы: 
L = 42   M = 4

В цикле while две операции указывают на то, что данное задание проще рассматривать при работе с числом в 8-й системе счисления:

1. x mod 8 - младший разряд числа в 8-й системе счисления 
т.е., например: 56₈
тогда  x mod 8 - это цифра 6

2. x := x div 8 - "отсекание" младшего разряда числа в 8-й системе счисления
т.е., например: x = 46₁₀ = 56₈
тогда  x := x div 8 -> x = 5₁₀ = 5₈

Таким образом, в цикле рассматриваются цифры числа в 8-й системе счисления. В конце цикла, каждый раз от числа "отсекается" крайний разряд, тем самым число теряет цифру. Цикл выполняется до тех пор, пока есть цифры в числе (while x > 0).
М - это счетчик итераций, т.е. шагов цикла, т.к. М увеличивается каждый раз на единицу. Поскольку количество цифр числа уменьшается с каждой итерацией, то М в результате возвращает количество цифр числа - по заданию М = 4. Значит, число x - четырехзначное.
В условии if x mod 8 > 3 then проверяется каждая цифра числа: если она больше трех, то выполняется действие L := L * (x mod 8);. Дословно, это говорит о том, что L - это произведение цифр числа (в его 8-м представлении), которые больше трех.
Таким образом соберем все выводы:

М = 4 - количество цифр числа т.е.
x в 8-й системе счисления имеет 4 разряда: ? ? ? ?
L = 42 произведение цифр, которые больше трех.

По заданию нам необходимо найти наименьшее x. Теперь, зная, что х - четырехзначное, а 42 - произведение его цифр, больших трех, найдем, как получается 42:

42 = 6 * 7

Соответственно, для старшего разряда поставим единицу, а один разряд оставим равным 0:

x = 1067₈

Осталось перевести получившееся число в 10-ю систему счисления, чтобы найти исходный x:

1067₈ = 567₁₀

Результат: 567

Задание 22_8:

22_8:

Укажите количество двузначных натуральных чисел, при вводе которых приведенная ниже программа напечатает число 0.

var
  i, n: longint;
begin
  i := 0;
  readln(n);
  while (n > 0) do
  begin
    i := i + n mod 8;
    n := n div 8;
  end;
  writeln(i mod 7);
end.

Ответ: 13

Показать решение:

Один из вариантов решения:

В цикле while две операции указывают на то, что данное задание можно рассматривать при работе с числом в 8-й системе счисления:

1. n mod 8 - младший разряд числа в 8-й системе счисления 
т.е., например: 56₈
тогда  n mod 8 - это цифра 6

2. n := n div 8 - "отсекание" младшего разряда числа в 8-й системе счисления
т.е., например: n = 46₁₀ = 56₈
тогда  n := n div 8 -> n = 5₁₀ = 5₈

Таким образом, в цикле рассматриваются цифры числа в 8-й системе счисления. В конце цикла, каждый раз от числа "отсекается" крайний разряд, тем самым число теряет цифру. Цикл выполняется до тех пор, пока есть цифры в числе (while n > 0).
i - это сумматор, который аккумулирует (суммирует) цифры восьмеричного числа: поскольку n mod 8 - младшая цифра числа, и каждую итерацию цикла от числа отсекается цифра младшего разряда, то на каждом шаге в i добавляется очередная справа цифра числа:

Например:  n = 256₈
1) i := i + n mod 8; => i = 0 + 6 = 6  (256)
2) i := i + n mod 8; => i = 6 + 5 = 11  (256)
3) i := i + n mod 8; => i = 11 + 2  = 13 (256)

В конце программы распечатывается значение i mod 7, т.е. остаток от деления получившейся суммы на число 7.
Таким образом соберем все выводы:

i - сумматор цифр введенного числа n в его восьмеричном представлении
n - двузначные десятичные числа (по условию)
результат программы = i mod 7 = 0, т.е. остаток от деления итоговой суммы на 7 (= 0)

Поскольку в условии говорится о десятичных числах, т.е. вводятся двузначные десятичные числа. Рассмотрим максимальное и минимальное двухзначное десятичное число, преобразованное в 8-ю систему счисления:

n_min = 10₁₀ = 12₈
n_max = 99₁₀ = 143₈

Выберем суммы цифр чисел в диапазоне от 12 до 143 (исключая цифры большие 7, т.к. 8-я с.с):

16 = 1+6 = 7 (7 mod 7 = 0), 
25 = 2+5 = 7 (7 mod 7 = 0), 
34 = 3+4 = 7 (7 mod 7 = 0), 
43 = 4+3 = 7 (7 mod 7 = 0), 
52 = 5+2 = 7 (7 mod 7 = 0), 
61 = 6+1 = 7 (7 mod 7 = 0), 
70 = 7+0 = 7 (7 mod 7 = 0), 
77 = 7+7 = 14 (14 mod 7 = 0), 
106 = 1+6 = 7 (7 mod 7 = 0), 
115 = 1+1+5 = 7 (7 mod 7 = 0), 
124 = 1+2+4 = 7 (7 mod 7 = 0), 
133 = 1+3+3 = 7 (7 mod 7 = 0), 
142 = 1+4+2 = 7 (7 mod 7 = 0),

Посчитаем количество таких чисел - их 13.

Задание 22_10:

22_10:

Получив на вход натуральное число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее натуральное число, при вводе которого алгоритм печатает сначала 1, а потом 9.
Паскаль:

var x, a, b: longint;
begin
readln(x);
a := 0; b := 1;
while x > 0 do begin
  if x mod 2 = 0 then
     a := a + x mod 9
  else
     b := b * (x mod 9);
  x := x div 9;
end;
writeln(a); write(b);
end.

Бейсик:

INPUT x
a=0: b=1
WHILE x>0  
    IF x MOD 2 = 0 THEN
      a = a + x MOD 9
    ELSE
      b = b * x MOD 9
    END IF
    x = x \ 9
WEND
PRINT a
PRINT b
END

Python:

x = int(input())
a = 0
b = 1
while x > 0:
    if x % 2 == 0:
        a = a + x % 9
    else:
        b = b * (x % 9)
    x = x // 9
print(a)
print(b)

С++:

#include <iostream>
using namespace std;
int main()
  {
  int x, a, b;
  cin >> x;
  a = 0; b = 1;
  while (x > 0) {
    if (x%2 == 0) a += x%9;
    else b *= x%9;
    x = x / 9;
    }
  cout << a << endl << b;
  return 0;
}

Ответ: 255

Показать решение:

Программа получает на вход число x.
В цикле, пока число x больше 0, в зависимости от того, четное ли число x выполняются действия:
если четное, то в переменную a добавляется остаток от деления числа x на 9;

if x mod 2 = 0 then
  a := a + x mod 9

если нечетное, то переменная b умножается на остаток от деления числа x на 9;

else
  b := b * (x mod 9);

x целочисленно делится на 9.

x := x div 9;

Эти три действия в цикле - ни что иное, как работа с цифрами числа в 9-й системе счисления. Тогда, проверим значение x на четность в 9-й с.с.:
если четное, то в переменную a добавляется крайняя справа цифра числа (остаток от деления числа x на 9);
если нечетное, то переменная b умножается на крайнюю справа цифру числа x;
x целочисленно делится на 9: значит, отсекаем от x в 9-й с.с. крайнюю справа цифру.
Теперь попробуем подобрать наименьшее число x, рассматривая его пока в 9-й с.с.

Вспомним, что для систем счисления с нечётным основанием (наш случай, 9 - нечетное) справедливо утверждение, что число чётно тогда и только тогда, когда сумма всех его цифр чётна.

произведение цифр (b) должно быть равно 9 (если число x нечетное)
сумма цифр (a) должна быть равна 1 (если число x четное)

однозначное число:
минимальное 9, но цифры 9 в 9-й с.с. нет.
других вариантов получить 9 нет

двухзначное число:
минимальное 33
3 + 3 = 6 (четное) => a = 0 + 3 = 3, не подходит (т.к. а=1)
других вариантов получить 9 нет

трехзначное число:
1 случай:
минимальное 133
1 + 3 + 3 = 7 (нечетное) => b = 1 * 3 = 3
отсекаем: x = 13
1 + 3 = 4 (четное) => a = 0 + 3 = 3, не подходит (т.к. а=1)

2 случай:
следующее минимальное 313
3 + 1 + 3 = 7 (нечетное) => b = 1 * 3 = 3
отсекаем: x = 31
3 + 1 = 4 (четное) => a = 0 + 1 = 1
отсекаем: x = 3
3 (нечетное) => b = 3 * 3 = 9
отсекаем: x = 0, конец цикла

Результаты нас устраивают (a = 1, b = 9). Переведем число 313 из 9-й с.с. в 10-ю:

313⁹ = 3 * 9² + 1 * 9 + 3 = 255¹⁰

📹 Видео

📹 Видеорешение на RuTube здесь

Задания на алгоритм Евклида и поиск НОД

Задание 22_4:

22_4:

Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает число M.

Известно, что x>40. Укажите наименьшее такое (т.е. большее 40) число x, при вводе которого алгоритм печатает 5.

var x,L,M: integer;
begin
  readln(x);
  L:=x; 
  M:=5;
  if L mod 2 = 0 then
    M:=24;
  while L <> M do
    if L > M then
      L:=L-M
    else
      M:=M-L;
  writeln(M);
end.

Ответ: 45

✍ Показать решение:

Рассмотрим алгоритм:

В начале программы запрашивается x. Переменной L присваивается значение x, а переменной M - значение 5.
Затем в условии проверяется четность переменной L: если переменная четная, то M присваивается значение 24.
Далее следует цикл, зависящий от переменных L и M: цикл завершится, когда L сравняется с M, т.е. согласно условию, когда L = M = 5 (так как по завершению программы на экран выводится число 5):

По завершению программы:
L = M = 5

Кроме того, по условию известно, что x > 40.
В цикле из переменной большего значения вычитается переменная меньшего значения (алгоритм Евклида поиска наибольшего общего делимого):

НОД (a, b) = если a > b, то НОД (a-b, b) = если b > a, то НОД (a, b-a)

Поскольку в результате работы программы распечатывается значение M, равное 5, то можно утверждать, что если условие if L mod 2 = 0 не будет истинным, то в цикле постоянно будет происходить действие L:=L-M). Т.е. постоянно вычитается 5.
Исходя из предыдущего пункта, исходное число x должно быть кратно 5, так как в результате печатается 5 (M). А при M=24 алгоритм не выдаст в результате значение 5.
Первое наименьшее число, кратное 5 и большее 40 (по условию) - это 45.
Проверим по алгоритму:

Если следовать алгоритму Евклида, то число 5 (результат) - это наибольший общий делитель числа 5 (исходное значение M) и числа x (введенного числа). Поскольку x больше 40, то наименьшим значением для которого общим делителем с числом 5 будет само число 5 - это число 45.

📹 Видео

📹 Видеорешение на RuTube здесь