0

Всем привет. Задачка с CodeWars "Kids and candies". С условием можете ознакомиться по ссылке https://www.codewars.com/kata/56cca888a9d0f25985000036/python . Суть в том, что нужно найти НОК для всех чисел попарно из диапазона (1, n). Вот мой код:

def candies_to_buy(amount_of_kids_invited):
    def nod(nok,i):
        a = 0
        ost = []
        if nok >= i:
            ost.append(nok)
            ost.append(i)
        else:
            ost.append(i)
            ost.append(nok)
        while ost[-1] !=0:
            ost.append(ost[-2]%ost[-1])
        return (ost[-2])
    
    nok = 1
    for i in range(1,amount_of_kids_invited+1,1):
        if (nok/i) - int(nok/i) != 0:
            nok = (nok*i)/nod(nok,i)
    return (int(nok))

функция nod возвращает НОД для текущего числа из диапазона и промежуточного значения НОК, если оно не является истинным значением НОК. Если же НОК истинно - возвращаем его как результат. Код работает для чисел n порядка 10**6. Дальше начинаются проблемы. Тестирование кода проваливается, когда правильный ответ не помещается по длине экрана: 1533421328177138432 should equal 7041757898200960193617914702466542659236800. Что делать в такой ситуации?

1
  • В вашем коде все деления вещественные. Нужны целочисленные: / -> //. 29 мая 2022 в 8:59

1 ответ 1

2

Что-то как-то у вас страшно, но ощущение по результатам - что у вас деление где-то не целочисленное. Разбираться с вашим решением сложновато, посмотрите на такое:

def candies_to_buy(amount_of_kids_invited):
    def gcd(a,b):
        while( a != 0 and b != 0):
            if (a < b):
                b = b % a
            else:
                a = a % b
        return a + b
    
    def lcm(a,b):
        return a *b//gcd(a,b)
        
    g = 1
    for i in range(1,amount_of_kids_invited+1):
        g = lcm(i,g)
        
    return g
1
  • Спасибо. Убрал у себя условие if (nok/i) - int(nok/i) != 0: (предполагалось, что искать НОК не нужно для числа, если оно и так делится, а также добавил целочисленное деление. Все заработало. Пока не понимаю, в чем дело, но видимо в представлении дробного числа в памяти компьютера. 29 мая 2022 в 9:15

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.