Эврика!

Как найти нод и нок чисел

Содержание

  1. Инструкция

Как найти нод и нок чисел

Целые числа – множество математических чисел, имеющих большое применение в повседневной жизни. Неотрицательные целые числа используются при указании количества любых объектов, отрицательные числа - в сообщениях о прогнозе погоды и пр. НОД и НОК – это натуральные характеристики целых чисел, связанные с операциями деления.

Инструкция

  • Наибольший общий делитель (НОД) двух целых чисел – это наибольшее целое число, на которое делятся оба исходных числа без остатка. При этом хотя бы одно из них должно быть отличным от нуля, как и НОД.
  • НОД легко вычислить по алгоритму Евклида или бинарному методу. По алгоритму Евклида определения НОД чисел a и b, одно из которых не равно нулю, существует такая последовательность чисел r_1 > r_2 > r_3 > … > r_n, в которой элемент r_1 равен остатку от деления первого числа на второе. А другие члены последовательности равны остаткам от деления предпредыдущего члена на предыдущий, а предпоследний элемент делится на последний без остатка.
  • Математически последовательность можно представить в виде:
    a = b*k_0 + r_1
    b = r_1*k_1 + r_2
    r_1 = r_2*k_2 + r_3

    r_(n - 1) = r_n*k_n,
    где k_i – целочисленный множитель.
    НОД (a, b) = r_n.
  • Алгоритм Евклида называют взаимным вычитанием, поскольку НОД получается при последовательном вычитании меньшего из большего. Нетрудно предположить, что НОД (a, b) = НОД (b, r).
  • Пример.
    Найдите НОД (36, 120). По алгоритму Евклида отнимите от 120 число, кратное 36, в данном случае это 120 – 36*3 = 12. Теперь отнимите от 120 число, кратное 12, получится 120 – 12*10 = 0. Следовательно, НОД (36, 120) = 12.
  • Бинарный алгоритм нахождения НОД основан на теории сдвига. Согласно этому методу НОД двух чисел обладает следующими свойствами:
    НОД (a, b) = 2*НОД (a/2, b/2) для четных a и b
    НОД (a, b) = НОД (a/2, b) для четного a и нечетного b (наоборот верно НОД (a, b) = НОД (a, b/2))
    НОД (a, b) = НОД ((a - b)/2, b) для нечетных a > b
    НОД (a, b) = НОД ((b - a)/2, a) для нечетных b > a
    Таким образом, НОД (36, 120) = 2*НОД (18, 60) = 4*НОД (9, 30) = 4* НОД (9, 15) = 4*НОД ((15 - 9)/2=3, 9) = 4*3 = 12.
  • Наименьшее общее кратное (НОК) двух целых чисел – это наименьшее целое число, которое делится на оба исходных числа без остатка.
    НОК можно вычислить через НОД: НОК (a, b) = |a*b|/НОД (a, b).
  • Второй способ вычисления НОК – каноническое разложение чисел на простые множители:
    a = r_1^k_1*…*r_n^k_n
    b = r_1^m_1*…*r_n^m_n,
    где r_i – простые числа, а k_i и m_i – целые числа ≥ 0.
    НОК представляется в виде тех же простых множителей, где в качестве степеней берутся максимальные из двух чисел.
  • Пример.
    Найдите НОК (16, 20):
    16 = 2^4*3^0*5^0
    20 = 2^2*3^0*5^1
    НОК (16, 20) = 2^4*3^0*5^1 = 16*5 = 80.

Как вычислить объем пирамиды
Как вычислить объем пирамиды
Как найти диагональ осевого сечения цилиндра
Как найти диагональ осевого сечения цилиндра
Как определить критический объем продаж
Как определить критический объем продаж
Что такое регресс
Что такое регресс
Как построить лекало
Как построить лекало
Что такое симбиоз
Что такое симбиоз

© CompleteRepair.Ru