Question

Составить программу нахождения наименьшего общего кратного(НОК) двух чисел m и n, используя формулу n*m=НОД(m,n)*НОК(n,m). Разработать тесты для проверки правильности работы программы.

Answer 1

В программе на Питоне реализован алгоритм Евклида для нахождения НОД и найдено НОК из формулы из условия. Большая часть тестов для проверки использует случайные числа, для которых, например, проверяется, что НОК и НОД от (x, y) не изменяются, если их искать от (y, x), и т.д. (assert expr выбрасывает исключение, если expr ложно, так что если test сработало без ошибок, значит, всё ок)

def gcd_lcm(a, b):

   x, y = a, b

   while x != 0 and y != 0:

       x, y = y % x, x

   gcd = x + y

   lcm = a // gcd * b

   return gcd, lcm

def test():

   from random import randint

   x, y, z = [randint(1, 1000) for _ in range(3)]

   xx = gcd_lcm(x, x)

   xy = gcd_lcm(x, y)

   yx = gcd_lcm(y, x)

   yz = gcd_lcm(y, z)

   x1 = gcd_lcm(x, 1)

   zx_y = gcd_lcm(z * x, y)

   zx_zy = gcd_lcm(z * x, z * y)

   gcd_xy_z = gcd_lcm(xy[0], z)[0]

   gcd_x_yz = gcd_lcm(x, yz[0])[0]

   assert xx == (x, x)

   assert xy == yx

   assert xy[1] % xy[0] == 0

   assert xy[1] % x == 0

   assert xy[1] % y == 0

   assert x % xy[0] == 0

   assert y % xy[0] == 0

   assert x1[0] == 1

   assert x1[1] == x

   assert zx_y[0] % xy[0] == 0

   assert zx_y[1] % xy[1] == 0

   assert zx_zy[0] == z * xy[0]

   assert zx_zy[1] == z * xy[1]

   assert gcd_xy_z == gcd_x_yz

   assert gcd_lcm(2**7 * 3**15, 3**4 * 5**3) == (3**4, 2**7 * 3**15 * 5**3)

   assert gcd_lcm(7 * 917887, 7 * 850177) == (7, 7 * 850177 * 917887)

if __name__ == "__main__":

   for _ in range(100):

       test()

Answer 2

Ответ:

Если на паскале, то вот:

Объяснение:

var

   a, b: integer;

function nod(a, b: integer): integer;

begin

   while a * b <> 0 do

       if a > b then

           a := a mod b

       else

           b := b mod a;

   

   nod := a + b;

end;

begin

   readln(a, b);

   write('NOK = ', a * b / nod(a, b));

end.

Answer 3

Для нахождения наименьшего общего кратного (НОК) двух чисел m и n с использованием формулы n * m = НОД(m, n) * НОК(n, m), нам понадобится функция для нахождения наибольшего общего делителя (НОД). Мы можем использовать алгоритм Евклида для этой цели.

Вот программа на Python для вычисления НОК и функция тестирования с несколькими тестами:

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

def lcm(m, n):
    return (m * n) // gcd(m, n)

def test_lcm():
    test_cases = [
        (12, 18, 36),
        (8, 5, 40),
        (25, 15, 75),
        (7, 9, 63),
        (1, 1, 1),
        (0, 10, 0),
    ]

    for m, n, expected_result in test_cases:
        result = lcm(m, n)
        assert result == expected_result, f"Ошибка: НОК({m}, {n}) = {result}, ожидается {expected_result}"
    print("Все тесты пройдены успешно!")

if __name__ == "__main__":
    test_lcm()

Этот код содержит функцию lcm(m, n), которая вычисляет НОК двух чисел m и n, используя формулу n * m = НОД(m, n) * НОК(n, m), и функцию gcd(a, b), которая находит НОД двух чисел a и b с помощью алгоритма Евклида. Функция test_lcm() запускает несколько тестовых случаев и проверяет правильность работы функции lcm().

При запуске программы, если выводится "Все тесты пройдены успешно!", это означает, что программа успешно прошла все тесты и работает правильно для предоставленных случаев.