Question

1. Даны два натуральных числа M и N – числитель и знаменатель дроби M/N. Требуется сократить дробь, насколько это возможно.

Answer 1

Var n,m,q,i:integer;f:boolean;
begin
read(m,n);
f:=true;
while f=true do begin
f:=false;
if m>n then q:=n else q:=m;
for i:=2 to q do begin
if (m mod i = 0) and (n mod i = 0) then begin m:=m div i;n:=n div i;f:=true;end;
end;
end;
writeln(m,'/',n);
end.

По идее так, не проверял.

Answer 2

Для сокращения дроби M/N нужно найти их наибольший общий делитель (НОД) и разделить числитель и знаменатель на этот НОД.

Для нахождения НОД можно воспользоваться алгоритмом Евклида. Алгоритм Евклида заключается в последовательном делении большего числа на меньшее с получением остатка. Процесс продолжается до тех пор, пока не будет получен ноль. Наименьшее из чисел, которое дало ноль, и будет НОД.

Пример:

Пусть M = 24, N = 36.

Шаг 1: 36 / 24 = 1 (остаток 12) Шаг 2: 24 / 12 = 2 (остаток 0)

Ноль получен на втором шаге, поэтому НОД(24, 36) = 12.

Теперь делим числитель и знаменатель на НОД:

M / НОД = 24 / 12 = 2 N / НОД = 36 / 12 = 3

Итак, исходная дробь M/N = 24/36 была сокращена до 2/3.

Важно отметить, что НОД может быть равен 1, в таком случае дробь не может быть дальше сокращена.