Высота дроби, оптимизация кода

Question

Высота обыкновенной дроби — это сумма модуля числителя и знаменателя этой дроби. Высота рационального числа — это сумма модуля числителя и знаменателя несократимой обыкновенной дроби, соответствующей этому числу. Надо написать программу, которая напечатает все рациональные числа высотой n (её значение введёт пользователь), лежащие между 0 и 1.

Вот один из вариантов такой программы:

def gcd(a, b):
    """Функция нахождения наибольшего общего делителя"""
    while b:
        a, b = b, a % b
    return a

# Запрашиваем у пользователя высоту
height = int(input("Введите высоту рациональных чисел: "))

# Перебираем все возможные значения числителей
for numerator in range(1, height):
    denominator = height - numerator
    # Проверяем, что дробь несократимая
    if gcd(numerator, denominator) != 1:
        continue
    # Проверяем, что дробь лежит между 0 и 1
    if numerator/denominator > 1 or numerator/denominator < 0:
        continue
    # Если все условия выполнены, печатаем дробь
    print(f"{numerator}/{denominator}")

Помогите, пожалуйста, этот код оптимизировать. Например, в данном варианте на каждом шаге цикла производится проверка несократимости дроби, а также проверка на возлежание дроби между 0 и 1. Может, можно как-то уменьшить количество таких проверок?

P. S.

Девятилетняя ученица одной из моих знакомых вообще использовала два цикла вместо одного, но в её возрасте такое простительно:

def gcd(a, b):
    """Функция нахождения наибольшего общего делителя"""
    while b:
        a, b = b, a % b
    return a

# Запрашиваем у пользователя высоту
height = int(input("Введите высоту рациональных чисел: "))

# Перебираем все возможные пары числителей и знаменателей
for numerator in range(1, height+1):
    for denominator in range(1, height+1):
        # Проверяем, что числитель и знаменатель не равны высоте
        if numerator + denominator != height:
            continue
        # Проверяем, что дробь несократимая
        if gcd(numerator, denominator) != 1:
            continue
        # Проверяем, что дробь лежит между 0 и 1
        if numerator/denominator > 1 or numerator/denominator < 0:
            continue
        # Если все условия выполнены, печатаем дробь
        print(f"{numerator}/{denominator}")

Answer 1

Вот мой вариант, объединил условия. Ещё проверяю ручками

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

height = int(input("Введите высоту рациональных чисел: "))

for numerator in range(1, height):
    denominator = height - numerator
    if gcd(numerator, denominator) == 1 and 0 < numerator/denominator < 1:
        print(f"{numerator}/{denominator}")

input("Нажмите Enter для выхода")

Answer 2

Как было сказано в комментариях, можно идти не до height + 1, а до height // 2 + 1, тогда можно будет убрать проверку на то, что число лежит в (0, height]. Также лучше использовать math.gcd, он быстрее вашей реализации, т.к. он написан на c.

n = int(input())

for x in range(1, n // 2 + 1):
    if math.gcd(x, n - x) == 1:
        print(x, n - x)

Еще можно заменит n - x, на просто n. Получаем math.gcd(x, n) == 1.

В итоге:

n = int(input())

for x in range(1, n // 2 + 1):
    if math.gcd(x, n) == 1:
        print(x, n - x)

Если посмотреть на реализую функции Эйлера:

k = 0
for x in range(1, k):
    if math.gcd(x, k) == 1:
        k += 1

Различия только в диапозоне, и в том что в одном мы ищем пары, а во втором подсчитывается количество. Исходя из их сходство, вероятно, надо будет посмотреть на эффективную реализацию функции Эйлера

БЛОГ НА HUSL

Высота дроби, оптимизация кода

Ответы (2 шт):