Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 26.
| Бейсик | Python |
|---|---|
DIM X, L, M AS INTEGER INPUT X L = X M = 65 IF L MOD 2 = 0 THEN M = 52 ENDIF WHILE L <> M IF L > M THEN L = L – M ELSE M = M – L ENDIF WEND PRINT M
| x = int(input()) L = x M = 65 if L % 2 == 0: M = 52 while L != M: if L > M: L = L - M else: M = M - L print(M)
|
| Паскаль | Алгоритмический язык |
var x, L, M: integer; begin readln(x); L := x; M := 65; if L mod 2 = 0 then M := 52; while L <> M do if L > M then L := L - M else M := M – L; writeln(M); end.
| алг нач цел x, L, M ввод x L := x M := 65 если mod(L,2)=0 то M := 52 все нц пока L <> M если L > M то L := L – M иначе M := M – L все кц вывод M кон |
| Си++ | |
#include <iostream> using namespace std; int main() { int x, L, M; cin >> x; L = x; M = 65; if (L % 2 == 0) M = 52; while (L != M){ if(L > M) L = L - M; else M = M - L; } cout << M << endl; }
| |
В теле цикла числа M и L уменьшаются, пока не станут равными. Чтобы в итоге было напечатано 26, оба числа в какой-то момент должны быть равны 26. Пойдем от конца к началу: на предыдущем шаге одно число было 26, а другое 26 + 26 = 52. Еще на шаг раньше 52 + 26 = 78 и 52. До того 78 + 52 = 130 и 52. То есть наименьшее возможное число 130. А поскольку найденное число четное, то M будет присвоено значение 52, что и приведет к необходимому результату.
Ответ: 130.
Приведем другое решение.
Заметим, что используемый в программе цикл представляет собой нахождение наибольшего общего делителя чисел M и L. Этот наибольший общий делитель должен быть равен 26. Если число L четное, то находится наибольший общий делитель чисел L и 52. Наименьшее четное число, которое больше 100 и при этом делится на 26, равно 130. Если же L нечетное, то находится наибольший общий делитель чисел L и 65, но он не может быть равен 26, поскольку 65 не делится на 26. Следовательно, число L равно 130.
Приведём другое решение на языке Python.
for i in range(100, 1000):
x = i
L = x
M = 65
if L % 2 == 0:
M = 52
while L != M:
if L > M:
L = L - M
else:
M = M - L
if M == 26:
print(i)
break