Задача про Сортировку дробей. В коде есть какая-то ошибка, но я не понимаю какая. Пожалуйста подскажите

count = int(input())

ls = []
for _ in range(count):
    line = input()
    ls.append(list(map(int, line.split('/'))))

ls.sort(key=lambda x: x[0]/x[1])

for i1, i2 in ls:
    print('%d/%d' % (i1, i2))

введите сюда описание изображения

введите сюда описание изображения


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

Автор решения: Stanislav Volodarskiy

Чтобы добавить второе условие достаточно переделать лямбду lambda x: (x[0] / x[1], x[0]). Питон сравнивает кортежи слева направо. Если первые элементы разные, они определят порядок, иначе порядок определят вторые элементы. Вот и всё...

... но есть маленький шанс что этого мало.

Ясно что

  n     n + 1
----- > -----
n - 1     n

потому что n2 > (n - 1)(n + 1) = n2 - 1.

Но вот пример:

$ python
...
@>>> n = 91566432
@>>> n / (n - 1) > (n + 1) / n
False
@>>> n * n > (n + 1) * (n - 1)
True

Неравенство с делениями вычисляется с ошибкой. Операция / в Питоне возвращает вещественное число конечной точности. Тут точности не хватает. Неравенство с умножениями всегда вычисляется правильно - Питон умножает целые числа точно. Чтобы сравнивать дроби через умножения потребуется написать процедуру сравнения руками:

import functools


def cmp_(f1, f2):
    n1, d1 = f1
    n2, d2 = f2
    diff = n1 * d2 - n2 * d1
    if diff != 0:
        return diff
    return n1 - n2


fractions = [tuple(map(int, input().split('/'))) for _ in range(int(input()))]
fractions.sort(key=functools.cmp_to_key(cmp_))
for n, d in fractions:
    print(f'{n}/{d}')
→ Ссылка