Ниже на пяти языках программирования записан алгоритм. Получив на вход число х, этот алгоритм печатает число М. Известно, что х > 40. Укажите наименьшее такое (т. е. большее 40) число х, при вводе которого алгоритм печатает 2.
| Бейсик | Python |
|---|---|
DIM X, L, M AS INTEGER INPUT X L = X M = 12 IF L MOD 2 = 0 THEN M = 24 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 = 12 if L % 2 == 0: M = 24 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 := 12; 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, M ввод x L := x M := 12 если mod(L, 2) = 0 то M := 24 все нц пока 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 = 12; if (L % 2 == 0) M = 24; while (L != M) { if(L > M) L = L − M; else M = M − L } cout « M « endl;
| |
Цикл while — ничто иное, как алгоритм Евклида, то есть он ищет наибольший общий делитель чисел M и L. В конце работы цикла M = L = НОД(M, L).
Если x — чётное число, то L = x, M = 24. Если нечётное, то L = x, M = 12.
При этом, если x — нечётное число, то НОД(L, M) 
2. Поэтому x должен быть чётным.
Таким образом, нам нужно самое маленькое чётное число, которое больше 40 и не делится на 3 и 4 (тогда бы НОД(L, M) равнялся 6 или 4). Это число 46.
Ответ: 46.
Приведём другое решение на языке Python.
for i in range(41, 10000):
x = i
L = x
M = 12
if L % 2 == 0:
M = 24
while L != M:
if L > M:
L = L - M
else:
M = M - L
if M == 2:
print(i)
break