Уведомления

Группа в Telegram: присоединиться

#1 Май 16, 2019 09:39:00

MNadezhda
Зарегистрирован: 2019-05-16
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Помогите найти ошибку в цикле while

Всем привет!
Это мой второй в жизни код с циклом, я прямо совсем новичковый новичок, и видимо не понимаю какую-то очевидную вещь.

Задача: Программа должна считывать числа a и b (целые, положительные), каждое число вводится на отдельной строке, и выводит наименьшее число d, которое делится на оба этих числа без остатка.

 a,b=int(input()),int(input())
d=1 
n=1
while d==1:
    if n%a==0 and n%b==0:
        d=n
        print(d)
    n+=1

Test input:
7
5
Test output:
35
Теоретические вроде работает, но есть какая-то ошибка (код не проходит тесты на правильность на образовательном сайте). Буду очень благодарна за объяснение!

Отредактировано MNadezhda (Май 16, 2019 09:54:01)

Офлайн

#2 Май 16, 2019 10:32:16

FishHook
От:
Зарегистрирован: 2011-01-08
Сообщения: 7118
Репутация: +  480  -
Профиль   Отправить e-mail  

Помогите найти ошибку в цикле while

MNadezhda
1) Что будет с вашим алгоритмом, если a = b = 1 ??
2) Алгоритм не эффективен, поскольку нет смысла искать n на значениях меньше max(a, b). Представим, что a = 777777, b=99999999999. Вы начинаете цикл с единицы, очевидно, что никакое число меньшее 99999999999 не поделится на него нацело.
3) Алгорит не эффективен ибо:
Допустим, a = 12, b = 21. Очевидно что никакие значения кроме членов последовательности 21, 42, 63, 84, 105, 126, 147… не могут быть ответом. Зачем вы итерируетесь с шагом 1?

4) Открываем википедию и читаем:
Нахождение НОК:

lcm(a,b)=|a * b| / gcd(a,b)
где gcd - наибольший общий делитель
Теперь применяем алгоритм Евклида для нахождения gcd.





Отредактировано FishHook (Май 16, 2019 10:32:40)

Офлайн

#3 Май 16, 2019 11:49:18

MNadezhda
Зарегистрирован: 2019-05-16
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Помогите найти ошибку в цикле while


@FishHook! Спасибо большое! Я поняла! Про единичку как-то вообще не подумала проверить. И теперь все получилось! Еще раз спасибо!

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version