Как решить 22 задачу егэ информатика

Содержание:

• Объяснение задания 22 ЕГЭ по информатике
  • Алгоритмизация и программирование: циклы и ветвления
• Решение 22 заданий ЕГЭ по информатике
  • Работа с цифрами чисел в различных системах счисления
  • Задания на алгоритм Евклида и поиск НОД

22-е задание: «Программирование: циклы и ветвления»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 7 минут.

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

НОД (14, 21) = 
НОД (14, 21-14) = 
НОД (14, 7) = 
НОД (7, 7) = 7

Реализация на Паскале:

1
2
3
4
5
6
7

function NOD (a, b: integer): integer;
begin
 while a <> b  do
   if a > b then a := a - b
   else          b := b - a;
 NOD := a;
end;

22_1:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13

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.

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

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

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:

1 2 3 4 5 6 7 8 9 10

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

Результат: 15

22_9:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13

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.

22_2:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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.

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

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

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

11110002 = 12010
первая единица будет стоять всегда, она не участвует в итерациях цикла

Проверка:
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 = 510 = 1012, то D mod 2 = 1 (101)

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

если было D = 510 = 1012, то стало D = 102

• условие цикла: пока 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:

111000

• важно не забыть крайнюю слева цифру 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 = 12010

Результат: 120

22_3:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13

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.

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

Рассмотрим алгоритм работы с 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.

Результат: 88

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.

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

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

В цикле:

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

например, если было x = 510 = 1012, 
то if x mod 2 <> 0 проверяет if 1 <> 0

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

если было, например, x = 510 = 1012, то стало x = 102

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

10011112 = 64 + 8 + 4 + 2 + 1 = 7910

  
✎ Способ 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.

Результат: 79

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

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

1
2
3
4
5
6
7
8
9
10
11
12

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.

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

22_7:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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.

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

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

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

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

2. x := x div 8 - "отсекание" младшего разряда числа в 8-й системе счисления
т.е., например: x = 4610 = 568
тогда  x := x div 8 -> x = 510 = 58
 

• Таким образом, в цикле рассматриваются цифры числа в 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 = 10678

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

10678 = 56710

Результат: 567

22_8:

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

1
2
3
4
5
6
7
8
9
10
11
12

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.

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

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

2. n := n div 8 - "отсекание" младшего разряда числа в 8-й системе счисления
т.е., например: n = 4610 = 568
тогда  n := n div 8 -> n = 510 = 58
 

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

Например:  n = 2568
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-ю систему счисления:

nmin = 1010 = 128
nmax = 9910 = 1438
 

• Выберем суммы цифр чисел в диапазоне от 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.

Ответ: 13

22_10:

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

Паскаль:

1
2
3
4
5
6
7
8
9
10
11
12
13

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

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;
}

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

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

• если нечетное, то переменная b умножается на остаток от деления числа x на 9;
• x целочисленно делится на 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-ю:

3139 = 3 * 92 + 1 * 9 + 3 = 25510

Ответ: 255

22_4:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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.

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

• В начале программы запрашивается 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.
• Проверим по алгоритму:

L  M

45 5
40 5
35 5
30 5
25 5
20 5
15 5
10 5
5  5 

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

Результат: 45