Форум » Циклы и ветвления » 20-81 » Ответить
20-81
timsc1: 81) Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 35. var x, L, M: integer; begin readln(x); L := x-20; M := x+15; while L <> M do if L > M then L := L - M else M := M – L; writeln(M); end. Кто-нибудь решал такую задачу??? Помогите решить, пожалуйста!!!
Ответов - 7
Поляков: timsc1 пишет: Кто-нибудь решал такую задачу??? Помогите решить, пожалуйста!!! Во-первых, нужно узнать алгоритм Евклида для вычисления наибольшего общего делителя (НОД). Дальше - излагайте свой путь решения, обсудим.
timsc1: В последний момент оба числа равны 35. Предыдущий шаг: 35+20=55 и 35-15=20; 55+20=75 и 20-15=5... Я думал в этом направлении, но попал в тупик...
Поляков: timsc1 пишет: Я думал в этом направлении, но попал в тупик... Повторюсь - нужно узнать алгоритм Евклида. Обратной прокруткой решить проблемно. Алгоритм Евклида находит наибольший общий делитель чисел M и L.
timsc1: то, что там алгоритм Евклида, я заметил сразу... Не могу это связать с +20 и -15 и что там вообще делать...
Поляков: timsc1 пишет: что там алгоритм Евклида, я заметил сразу... Не могу это связать с +20 и -15 и что там вообще делать... Тогда получается, что числа x+20 и x-15 делятся на 35: [pre2] x+20 = a*35 x-15 = b*35[/pre2]Первое подходящее число, которое > 100, равно 125.
polyakovss: Подробно так: НОД(L,M)=35; Тогда L/35=n; M/35=k, где n и k - целые числа, т.е. числа x-20 и x+15 делятся на 35. L = x-20; (x-20)/35=n; x=35*n+20; x>100; 35*n+20>100; M = x+15; (x+15)/35=k; x=35*k-15; x>100; 35*k-15>100; Требуется найти наименьшее x. Ему будет соответствовать наименьшее целое значение n, найденное из 35*n+20>100, так как n < k; n=3; x=35*3+20=125; Нужно проверить это значение x=125: НОД(L,M)=НОД((125-20),(125+15))=НОД(105,140)=35; Задача решена. В других аналогичных задачах проверка x при найденном n может не дать нужного значения НОД(L,M). Тогда следует взять для n значение на единицу больше и снова проверить x. Обычно этого достаточно.
timsc1: polyakovss , спасибо!!!
полная версия страницы