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

@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)

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@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