Алгоритм Евклида (упрощенная версия)

@CDRV · Регистрация: 23.11.2019

Студворк — интернет-сервис помощи студентам

Решите задачу одним циклом while, допускается применение условных операторов.

Наибольшим общим делителем (НОД) двух целых чисел a и b называется наибольший из их общих делителей. Например, для чисел 70 и 105 наибольший общий делитель равен 35.

С давних времен известен следующий алгоритм нахождения наибольшего общего делителя двух неотрицательных целых чисел: пока оба числа строго положительны надо из большего числа вычесть меньшее. Результатом работы (наибольшим общим делителем) является большее число после окончания описанной серии вычитаний или 0, если оба числа в конце равны 0.

Вам заданы целые неотрицательные числа a и b (0≤a,b≤107). Напишите программу, которая выведет количество вычитаний при работе такого алгоритма и результат его работы.

Входные данные
Единственная строка входных данных содержит записанные через пробел целые числа a, b (0≤a,b≤107).

Выходные данные
Выведите количество вычитаний в ходе работы алгоритма и результат его работы через пробел.

Пример
входные данные
70 105
выходные данные
3 35

Python
1
2
3
4
5
6
7
8
9
10
a, b=[int(x)for x in input(). split()]
x=0
while a != b:
    if a > b:
        a = a - b
        x=x+1
    else:
        b = b - a
        x=x+1
print(x+1, a)

Превышено ограничение времени на тесте 5 - не понимаю почему...

@eaa · 23.11.2019, 21:18

Сообщение от CDRV

0≤a,b≤107

107 или 10⁷ ?

@CDRV · 24.11.2019, 08:25 **[ТС]**

10⁷

@eaa · 24.11.2019, 09:44

во первых вы не учитываете 0
при вводе 0 100 у ваша программа зациклится.
во вторых тут нужен другой алгоритм Евклида использовать (деления с остатком)
если ввести 1 10000000 ваша программа выполнит 10 миллионов раз тело цикла, хотя можно подсчитать всего за 3.

@CDRV · 24.11.2019, 15:22 **[ТС]**

Ну и как программу то написать?

@Dax · 24.11.2019, 18:35

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    print(a)
 
 
if __name__ == '__main__':
    a = int(input())
    b = int(input())
    gcd(a, b)

@CDRV · 24.11.2019, 20:42 **[ТС]**

Количество вычитаний при работе еще найти надо

@Viktorrus · 25.11.2019, 05:11

Сообщение от CDRV

Количество вычитаний при работе еще найти надо

Добавьте счетчик и считайте количество циклов.

@CDRV · 25.11.2019, 19:28 **[ТС]**

А как этот счетчик добавить, а то я такую форму написания программы ещё пока не знаю.

@Viktorrus · 25.11.2019, 22:00

CDRV, перед циклом while инициируете счетчик со значением 0

Python
1
count = 0

На каждом шаге цикла, в конце его прибавляете к счетчику 1

Python
1
count += 1

При выходе из цикла выводите на печать значение счетчика.
Если хотите это значение использовать за пределами функции, то возвращаете его из функции с помощью return

@CDRV · 26.11.2019, 21:11 **[ТС]**

Программа выдаёт ошибку, а также нет счетчика вычитаний!!!

@codcw · 26.11.2019, 21:42

CDRV, только-что проверил

Python
1
2
3
4
70
105
35
>>>

никакой ошибки нет, счётчик добавьте сами, вам же уже объяснили как это сделать

Добавлено через 1 минуту
единственное что будет ошибка при вводе в одну строку, но тут вам просто нужно заменить метод ввода на тот что использовался в вашем коде

@CDRV · 01.12.2019, 09:22 **[ТС]**

Опять превышено ограничение по времени!

@eaa · 01.12.2019, 09:42

я Вам еще в посте #4 описал как это сделать. Не вижу ни одной Вашей попытки. Или за Вас написать?

@CDRV · 01.12.2019, 09:52 **[ТС]**

Вы понимаете, что нужно использовать вычитания по условию, а не деление с остатком.

@eaa · 01.12.2019, 09:59

Сообщение от CDRV

использовать вычитания по условию

этого нигде не сказано.

Сообщение от CDRV

Решите задачу одним циклом while, допускается применение условных операторов.

в программе будет только один while, условных операторов можно избежать вообще.

@CDRV · 01.12.2019, 10:01 **[ТС]**

Ладно, тогда какая будет программа, я уже запуталась

@eaa · 01.12.2019, 11:36

Python
1
2
3
4
5
6
a, b = map(int, input().split())
k = 0
while b:
    k += a//b
    a, b = b, a % b
print(k, a)

Новые блоги и статьи Все статьи Все блоги /
Программный отбор элементов справочника Номенклатура по группе 1С Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор под наименованию группы (на. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	Программный отбор элементов справочника Сотрудники по перечислениям 1С Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит предопределенное значение перечислений. Процедура. . .
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .

@CDRV 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 71
	24.11.2019, 08:25 [ТС]
	10⁷ 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.11.2019, 09:44
	во первых вы не учитываете 0 при вводе 0 100 у ваша программа зациклится. во вторых тут нужен другой алгоритм Евклида использовать (деления с остатком) если ввести 1 10000000 ваша программа выполнит 10 миллионов раз тело цикла, хотя можно подсчитать всего за 3. 0

@CDRV 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 71
	24.11.2019, 15:22 [ТС]
	Ну и как программу то написать? 0

@CDRV 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 71
	24.11.2019, 20:42 [ТС]
	Количество вычитаний при работе еще найти надо 0

@CDRV 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 71
	25.11.2019, 19:28 [ТС]
	А как этот счетчик добавить, а то я такую форму написания программы ещё пока не знаю. 0

@CDRV 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 71
	26.11.2019, 21:11 [ТС]
	Программа выдаёт ошибку, а также нет счетчика вычитаний!!! 0

@CDRV 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 71
	01.12.2019, 09:22 [ТС]
	Опять превышено ограничение по времени! 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	01.12.2019, 09:42
	я Вам еще в посте #4 описал как это сделать. Не вижу ни одной Вашей попытки. Или за Вас написать? 0

@CDRV 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 71
	01.12.2019, 09:52 [ТС]
	Вы понимаете, что нужно использовать вычитания по условию, а не деление с остатком. 0

@CDRV 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 71
	01.12.2019, 10:01 [ТС]
	Ладно, тогда какая будет программа, я уже запуталась 0