Python

Решить задачу python

Дана правильная рациональная несократимая дробь a / b. С этой дробью выполняется следующая операция: к числителю и знаменателю дроби прибавляется 1, после чего дробь сокращается. Определите, можно ли при помощи таких операций из дроби a / b получить другую правильную дробь c / d.

Формат входных данных
Программа получает на вход четыре целых числа a, b, c, d, причём числа a и b взаимно простые, числа с и d взаимно простые, a / b ≠ c / d.

Формат выходных данных
Программа должна вывести одно натуральное число – сколько описанных операций нужно применить, чтобы из дроби a / b получить дробь с / d. Если это сделать невозможно, программа должна вывести число 0.

Примечания
Примечание к первому примеру:

Дана дробь 1 / 3. После первой операции получается дробь 2 / 4, которая сокращается до 1 / 2. После второй операции получается дробь 2 / 3.

Примечание ко второму примеру:

Получить из дроби 2 / 3 дробь 1 / 3 невозможно.

как узнать когда выводить ноль,а когда продолжать алгоритм? Какая есть закономергсть у дробей, невозможных к "перевоплащению" в данную. Важно именно в моем алгоритме исправить:

a = int(input())
b = int(input())
c = int(input())
d = int(input())

i = 1
y = True

while y == True:
a += 1
b += 1


if a % 2 != 0 and b % 2 == 0:
if b % a == 0:
a = 1
b = b / 2
else:
print(0)
break


if a % 2 == 0 and b % 2 == 0:
while a % 2 == 0 and b % 2 == 0:
a = int(a/2)
b = int(b/2)


if a == c and b == d:
print(i)

y = False

else:
i = i+1

заранее спасибо !!!
Артём Усманов
Артём Усманов
118
Примерно так:
 from math import gcd

def norm(x, y):

    s = y < 0

    return (x ^ -s) + s, (y ^ -s) + s

a, b, c, d = map(int, map(input, ('',) * 4))

a, b, c, d = *norm(a, b), *norm(c, d)

cnt = 0

while a * d < b * c:

    t = tuple(map(int.__add__, (a, b), (1, 1)))

    a, b = map(gcd(*t).__rfloordiv__, t)

    cnt += 1

print((0, cnt)[a == c and b == d])
Приводим дроби к положительному знаменателю (функцией norm, переносящей отрицательный знак в числитель). Прибавление единицы к числителю и знаменателю всегда увеличивает значение правильной дроби:
 a + 1   a   ab + b - ab - a    b - a

----- - - = --------------- = --------

b + 1   b       b(b + 1)      b(b + 1)
это - положительное число, т.к. b > a, и b > 0.
Отсюда легко выводится условие продолжения цикла. Пока a/b < c/d, пробуем применять указанную в задании операцию к дроби a/b. Сравнение, естественно, выполняем в целых числах, а не по-ламерски, в вещественных.
Когда цикл завершается, a/b == c/d или a/b > c/d. В первом случае мы достигли цели, во втором - нет.
Отдельно - об отрицательных дробях: чтобы из отрицательной дроби получить положительную, мы рано или поздно пройдём через дробь 0/b. НОД числителя и знаменателя в ней равен b, поэтому она будет приведена к 0/1, а дальше из неё можно получить дробь (b-1)/b для любого натурального b.

Алгоритм имеет линейно-логарифмическую сложность, что делает его достаточно медленным для поиска пути приведения к дробям порядка 999999999/1000000000.
Но легко видеть, что любая дробь рано или поздно будет приведена к виду (b-1)/b, из которой достижимы только дроби такого же вида. Это открывает нам простор для оптимизации:
 from math import gcd

def norm(x, y):

    s = y < 0

    return (x ^ -s) + s, (y ^ -s) + s

a, b, c, d = map(int, map(input, ('',) * 4))

a, b, c, d = *norm(a, b), *norm(c, d)

cnt = 0

while not b - a == d - c == 1 and a * d < b * c:

    t = tuple(map(int.__add__, (a, b), (1, 1)))

    a, b = map(gcd(*t).__rfloordiv__, t)

    cnt += 1

print((0, c - a + cnt)[(a == c and b == d) or (a
МТ
Михайл Терентьев
87 571
Лучший ответ
Михайл Терентьев P.S. Для второй оптимизации достаточно факторизовать разность b-a, её простые делители по возрастанию и будут теми числами, на которые будет последовательно сокращаться дробь. Если p(i) - очередной делитель b-a, и на него не делится a, то вычисляем поправку m(i) = (p(i) - a mod p(i)) и сразу прыгаем к дроби (a + m(i)) / (b + m(i)), которая сокращается на p(i). При этом, естественно, проверяем случай 0 < c - a == b - d < m(i).

Похожие вопросы