Найти - Пользователи
Полная версия: Помогите найти ошибку в цикле while
Начало » Python для новичков » Помогите найти ошибку в цикле while
1
MNadezhda
Всем привет!
Это мой второй в жизни код с циклом, я прямо совсем новичковый новичок, и видимо не понимаю какую-то очевидную вещь.

Задача: Программа должна считывать числа 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
Теоретические вроде работает, но есть какая-то ошибка (код не проходит тесты на правильность на образовательном сайте). Буду очень благодарна за объяснение!
FishHook
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.



MNadezhda

@FishHook! Спасибо большое! Я поняла! Про единичку как-то вообще не подумала проверить. И теперь все получилось! Еще раз спасибо!
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB