Как найти нод в информатике

Время на прочтение
8 мин

Количество просмотров 19K

Алгоритмы – одна из центральных тем в программировании, они повсюду (особенно на собеседованиях, ха-ха).

(Разве можно обойтись в таком посте без «баяна»?)

Одним из самых известных является так называемый алгоритм Евклида – пожалуй, самый распространенный способ нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел. С него также зачастую любят начинать изучение (и обучение) соответствующих разделов математики и информатики.

А Дональд Кнут, небезызвестный автор трактата “Искусство программирования” (и не только), и вовсе считает алгоритм первым в истории (по крайней мере, относительно современных определений). Потому что, не смотря на то, что алгоритм был придуман и использовался еще до, собственно, Евклида, который жил в IV-III вв. до нашей эры (он упоминается уже у Аристотеля, жившего веком ранее), Евклид описывает процесс итеративно, что согласуется с современным значением слова.

Само слово “алгоритм” восходит к имени персидского математика Аль-Хорезми, жившего примерно в VIII-IX вв. уже нашей эры. А началом его использования в смысле, близком современному, считается уже лишь XX век, точнее – его первые десятилетия, восход информационных технологий.

Алгоритм Евклида

Любопытства ради предлагаю ознакомиться с евклидовским описанием алгоритма в редактуре Кнута. Оно довольно длинное, поэтому спрятано под катом:

Описание приводит два способа нахождения НОД – вычитанием и делением. Собственно, и в наши дни широко известны эти два способа реализации алгоритма.

Вот пример функции, написанной на «Swift», реализации первого способа:

func subtractionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int {
    if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) {
        return simpleGCD
    }

    var firstNumber = firstNumber
    var secondNumber = secondNumber
    while firstNumber != 0, secondNumber != 0 {
        if firstNumber > secondNumber {
            firstNumber = firstNumber - secondNumber
        } else {
            secondNumber = secondNumber - firstNumber
        }
    }

    return firstNumber + secondNumber // One of them is 0.
}

Здесь, переиспользования ради, я вынес в отдельную функцию случаи поиска НОД, когда он известен сразу, без необходимости следования какому-либо алгоритму:

func simpleCasesGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int? {
    if firstNumber == secondNumber {
        return firstNumber // Any.
    }

    if firstNumber == 0 {
        return secondNumber
    }
    if secondNumber == 0 {
        return firstNumber
    }

    return nil
}

(Если два числа равны, то, естественно, их НОД также равен им. Если какое-то из чисел равно нулю, то НОД будет равняться второму числу, т.к. ноль делится любым числом (с результатом, понятное дело, тоже ноль).)

В качестве входных данных могут использоваться только неотрицательные значения. Соответственно, для отрицательных можно использовать те же методы, но взяв числа по модулю. (Да, общий делитель может быть и отрицательным, но мы ищем именно НОД, а положительные числа, очевидно, всегда больше отрицательных.)

А вот так может выглядеть реализация версии алгоритма делением:

func divisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int {
    if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) {
        return simpleGCD
    }

    var firstNumber = firstNumber
    var secondNumber = secondNumber
    while firstNumber != 0, secondNumber != 0 {
        if firstNumber > secondNumber {
            firstNumber = firstNumber % secondNumber
        } else {
            secondNumber = secondNumber % firstNumber
        }
    }

    return firstNumber + secondNumber // One of them is 0.
}

Вторая версия в наши дни считается предпочтительней, так как содержит в себе, в среднем, ощутимо меньшее количество шагов. Тем не менее, во времена, когда компьютеры были большие и медленные, операция деления могла быть сама по себе сложной процедурой. И тогда первая версия алгоритма могла оказаться эффективней.

Чтобы немного их сравнить, я произвел несколько замеров с использованием любимого мной метода measure(_:) класса XCTestCase «нативного» фреймворка для тестирования кода в Xcode-проектах XCTest.

В качестве входных данных я использовал массив пар случайных чисел. Замеры производились, естественно, с использованием одного и того же массива для каждого способа. Разброс чисел для пар я взял от нуля до 9999. Замеры производились на количестве вычислений (пар чисел): одно, десять, 100, 1000, 10000, 100000, 1000000 и 10000000. Последнее заставляло ожидать результата уже несколько минут, поэтому на нем я решил остановиться.

Вот простой код генерации входных данных:

let pairs = (0..<100).map { _ in (Int.random(in: 0..<10000), Int.random(in: 0..<10000)) } // Generates 100 pairs.

Сам замер выглядит, например, так:

func testSubstractionGCDPerformance() {
    measure() {
        _ = pairs.map { substractionGCD($0, $1) }
    }
}

А вот так выглядят результаты запуска на моем компьютере:

(Subtraction – вычитание, division – деление.)

В общем, очень хорошо видно, как сильно на современных компьютерах проигрывает метод вычитания.

«Улучшенная» версия алгоритма Евклида

В литературе можно встретить версию алгоритма, в которой одно из чисел на каждом шаге вместо остатка от деления на второе заменяется на разность между этим отстатком и вторым числом, но только в случае, если остаток от деления больше половины второго числа. Реализация этой версии может выглядеть так:

func improvedDivisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int {
    if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) {
        return simpleGCD
    }

    var firstNumber = firstNumber
    var secondNumber = secondNumber
    while firstNumber != 0, secondNumber != 0 {
        if firstNumber > secondNumber {
            let firstNumberClaim = firstNumber % secondNumber
            if firstNumberClaim > secondNumber / 2 {
                firstNumber = abs(firstNumberClaim - secondNumber)
            } else {
                firstNumber = firstNumberClaim
            }
        } else {
            let secondNumberClaim = secondNumber % firstNumber
            if secondNumberClaim > firstNumber / 2 {
                secondNumber = abs(secondNumberClaim - firstNumber)
            } else {
                secondNumber = secondNumberClaim
            }
        }
    }

    return firstNumber + secondNumber // One of them is 0.
}

Такая модификация сокращает количество шагов алгоритма, но, судя по результатам замеров на моем компьютере, дополнительные вычисления и проверки на каждом шаге, нейтрализуют это преимущество и даже более:

(Improved – «улучшенная» версия.)

Еще немного о значимости алгоритма Евклида

Алгоритм имеет также геометрическую версию (для нахождения наибольшей меры двух отрезков).

Алгоритм был, конечно, обощен и для нахождения НОД любого количества чисел, не только двух. В двух словах идея такова: если обозначить функцию поиска НОД двух чисел как gcd(a, b), то, скажем, НОД трех чисел gcd(a, b, c) равен gcd(gcd(a, b), c). И так далее, для любого количества чисел НОД находится последовательным вычислением НОД НОД-а предыдущей пары чисел и следующего числа. Хотя, конечно, это касается поиска НОД вообще, а не только алгоритма Евклида.

Существует также обощение алгоритма для нахождения НОД полиномов. Но это уже выходит за рамки этого несложного поста, а в некоторой степени, и моих познаний в математике.

Сложность алгоритма Евклида

Временная сложность алгоритма исследовалась давно, не быстро и гораздо более учеными мужами, чем ваш покорный слуга. Тем не менее, вопрос давно закрыт и ответ получен. Собственно, еще в середине позапрошлого века. Габриэлем Ламе.

Если коротко, то ответ формулируется, собственно, теоремой Ламе, связанной с этим алгоритмом. Количество шагов алгоритма будет равно порядковому номеру ближайшего большего числа Фибоначчи наименьшему из двух чисел входных параметров минус 2. Оперируя чуть более традиционно-математическими обозначениями, то если u > v (и v > 1), то число проходов алгоритма будет равняться n — 2 при v < Fn (Fn – это некое ближайшее v число Фибоначчи, а n – это его порядковый номер).

Числа Фибоначчи растут экспоненциально, соответственно, имеем логарифмическую функцию времени выполнения алгоритма (от меньшего из двух входных чисел).

Те же самые выкладки показывают, что наихужшие для алгоритма входные данные – это два последовательных числа Фибоначчи.

Бинарный метод поиска НОД

Говоря о поиске НОД, стоит быть упомянутым алгоритм, предложенный уже в 60-е годы прошлого столетия неким Джозефом Стейном, о котором я не нашел в Сети вообще никакой информации. Он (алгоритм) ориентирован на двоичную арифметику и не содержит операций деления. Алгоритм оперирует только проверками четности и делением пополам, что осуществимо возможностями одной лишь бинарной арифметики.

Алгоритм основывается на четырех фактах:

1. Если u и v оба четны, то gcd(u, v) = 2 * gcd(u / 2, v / 2);
2. Если u четно, а v – нет, gcd(u, v) = gcd(u / 2, v);
3. gcd(u, v) = gcd(u — v, v) (это следует из алгоритма Евклида);
4. Если u и v оба нечетны, то u — v – четно и |u — v| < max(u, v)

На «Wikipedia» можно посмотреть рекурсивную версию алгоритма (на современных языках программирования записывается в несколько строк), я не стал ее переписывать на «Swift». А здесь я приведу вариант итеративной реализации:

func binaryGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int {
    if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) {
        return simpleGCD
    }

    var firstNumber = firstNumber
    var secondNumber = secondNumber

    var shift = 0
    while (firstNumber | secondNumber) & 1 == 0 {
        shift += 1
        firstNumber >>= 1
        secondNumber >>= 1
    }
    while firstNumber & 1 == 0 {
        firstNumber >>= 1
    }
    repeat {
        while secondNumber & 1 == 0 {
            secondNumber >>= 1
        }
        if firstNumber > secondNumber {
            swap(&firstNumber, &secondNumber)
        }
        secondNumber -= firstNumber
    } while secondNumber != 0

    return firstNumber << shift
}

Сделав замеры на тех же данных, к сожалению, этот мудреный алгоритм на моем компьютере не оправдал возложенных на него надежд. Конечно, он все еще работает в два раза быстрее евклидова алогоритма вычитанием, но заметно уступает классической его версии с делением. Полная таблица сводных данных:

(Binary – бинарный алгоритм.)

(Не исключаю, что алгоритм можно записать более эффективно, чем это сделал я, и это повлияет на результат, но на что же нам тогда нужны компиляторы?!)

Кстати, этот алгоритм, безусловно, получивший свои 15 минут славы уже в век информационных технологий (в более раннюю его часть, чем текущая), был известен еще в Древнем Китае. Его описание обнаружено в трудах, датируемых I в. н.э. Конечно, в терминах вроде «половинного деления» и вычитания. А также в контексте сокращения дробей.

Заключение

Честно говоря, этим простеньким «исследованием» я не собирался ничего доказывать и не хотел делать какие-то революционные умозаключения (и ведь не сделал же!). Я всего лишь хотел удовлетворить свое любопытство, посмотреть на работу разных подходов для решения классической задачи и слегка размять пальцы. Тем не менее, я надеюсь, наблюдать результаты было любопытно и вам!

Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления.

Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3. А далее находим НОК (наименьшее) общее кратное). Которое будет равно 30.

Для небольших чисел это легко вычисляется в уме. Но вот с пятиначными числами, так легко не получится. Поэтому предлагаю обратиться к алгоритму Евклида. Математические выкладки и детали в данной статье затрагивать не буду, хотя там много есть интересного.

Но суть достаточно простая. Их двух чисел выбираем большее и аычитаем из него меньшее. Далее выбираем снова большое и вычитаем из него снова, до тех пор пока разница не будет равна одному из чисел. Это и будет искомое число. Предлагаю проверить сперва на очевидных примерха.

Мы с вами уже находили НОД для 6 и 15. И у нас также получилось 3.

Теперь возьмём числа побольше. Я конечно могу сказать, что беру случайные числа, но по факту могы их проверить.

Пусть будут числа 195 и 1450. Очевидно, что они точно деляться на 5, но я предлагаю проверить.

И действительно 195 = 3*5*13, а 1450 = 2*5*5*29.

А теперь рассмотрим как найти НОК (наименьшее общее кратное). Рассмотрим сперва на простом примере. Числа 15 и 6.

Есть такая замечательная формула НОК = (A*B) / НОД.

Теперь проверим это выражение. НОК = (15*6)/3=30.

Оказывается, что всё достаточно просто. Если рассмотреть числа 195 и 1450, то для них НОК будет 195*1450/5=56550 или 2*3*5*5*13*29.

То есть без калькулятора можно свободно найти НОД и НОК. Естественно что для программиста эта задача становится очень простой.

Для начала разберем алгоритм через блок-схему.

Подробнее можно увидеть на видео:

У меня всё, благодарю за внимание.

———————————————————————-

Делюсь другими материалами:

Сериал Дистанционка от коллег в А1: Дистанционка. Серия 1. Дистанционка. Серия 2. Дистанционка. Серия 3.

Материалы по Scratch.

Математика – важная часть программирования и информатики. Это ядро ​​любого хорошего алгоритма, обеспечивающее аналитические навыки, необходимые для программирования.

Математические алгоритмы также являются очень важной темой для собеседований по программированию. В этой статье вы узнаете, как найти GCD и LCM двух чисел с помощью C ++, Python, C и JavaScript.

Как найти НОД двух чисел

Наибольший общий делитель (GCD) или наивысший общий делитель (HCF) двух чисел – это наибольшее положительное целое число, которое идеально делит два заданных числа. Вы можете найти НОД двух чисел, используя алгоритм Евклида.

В алгоритме Евклида большее число делится на меньшее число, затем меньшее число делится на остаток от предыдущей операции. Этот процесс повторяется до тех пор, пока остаток не станет 0.

Например, если вы хотите найти НОД 75 и 50, вам необходимо выполнить следующие действия:

• Разделите большее число на меньшее и возьмите остаток.

 75 % 50 = 25

• Разделите меньшее число на остаток от предыдущей операции.

 50 % 25 = 0

• Теперь остаток становится 0, таким образом, НОД 75 и 50 равны 25.

Программа на C ++ для поиска НОД двух чисел

Ниже приведена программа на C ++ для поиска НОД двух чисел:

 // C++ program to find GCD/HCF of 2 numbers
 #include <iostream>
 using namespace std;
 // Recursive function to find GCD/HCF of 2 numbers
 int calculateGCD(int num1, int num2)
 {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 // Driver Code
 int main()
 {
 int num1 = 34, num2 = 22;
 cout << "GCD of " << num1 << " and " << num2 << " is " << calculateGCD(num1, num2) << endl;
 int num3 = 10, num4 = 2;
 cout << "GCD of " << num3 << " and " << num4 << " is " << calculateGCD(num3, num4) << endl;
 int num5 = 88, num6 = 11;
 cout << "GCD of " << num5 << " and " << num6 << " is " << calculateGCD(num5, num6) << endl;
 int num7 = 40, num8 = 32;
 cout << "GCD of " << num7 << " and " << num8 << " is " << calculateGCD(num7, num8) << endl;
 int num9 = 75, num10 = 50;
 cout << "GCD of " << num9 << " and " << num10 << " is " << calculateGCD(num9, num10) << endl;
 return 0;
 }

Выход:

 GCD of 34 and 22 is 2
 GCD of 10 and 2 is 2
 GCD of 88 and 11 is 11
 GCD of 40 and 32 is 8
 GCD of 75 and 50 is 25

Программа Python для поиска НОД двух чисел

Ниже приведена программа Python для поиска НОД двух чисел:

 # Python program to find GCD/HCF of 2 numbers
 def calculateGCD(num1, num2):
 if num2==0:
 return num1
 else:
 return calculateGCD(num2, num1%num2)
 # Driver Code
 num1 = 34
 num2 = 22
 print("GCD of", num1, "and", num2, "is", calculateGCD(num1, num2))
 num3 = 10
 num4 = 2
 print("GCD of", num3, "and", num4, "is", calculateGCD(num3, num4))
 num5 = 88
 num6 = 11
 print("GCD of", num5, "and", num6, "is", calculateGCD(num5, num6))
 num7 = 40
 num8 = 32
 print("GCD of", num7, "and", num8, "is", calculateGCD(num7, num8))
 num9 = 75
 num10 = 50
 print("GCD of", num9, "and", num10, "is", calculateGCD(num9, num10))

Выход:

 GCD of 34 and 22 is 2
 GCD of 10 and 2 is 2
 GCD of 88 and 11 is 11
 GCD of 40 and 32 is 8
 GCD of 75 and 50 is 25

Программа на C для поиска НОД двух чисел

Ниже приведена программа на языке C для поиска НОД двух чисел:

 // C program to find GCD/HCF of 2 numbers
 #include <stdio.h>
 // Recursive function to find GCD/HCF of 2 numbers
 int calculateGCD(int num1, int num2)
 {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 // Driver Code
 int main()
 {
 int num1 = 34, num2 = 22;
 printf("GCD of %d and %d is %d ⁠⁠n" , num1 , num2, calculateGCD(num1, num2));
 int num3 = 10, num4 = 2;
 printf("GCD of %d and %d is %d ⁠⁠n" , num3 , num4, calculateGCD(num3, num4));
 int num5 = 88, num6 = 11;
 printf("GCD of %d and %d is %d ⁠⁠n" , num5 , num6, calculateGCD(num5, num6));
 int num7 = 40, num8 = 32;
 printf("GCD of %d and %d is %d ⁠⁠n" , num7 , num8, calculateGCD(num7, num8));
 int num9 = 75, num10 = 50;
 printf("GCD of %d and %d is %d ⁠⁠n" , num9 , num10 , calculateGCD(num9, num10));
 return 0;
 }

Выход:

 GCD of 34 and 22 is 2
 GCD of 10 and 2 is 2
 GCD of 88 and 11 is 11
 GCD of 40 and 32 is 8
 GCD of 75 and 50 is 25

Программа на JavaScript для поиска НОД двух чисел

Ниже приведена программа на JavaScript для поиска НОД двух чисел:

 // JavaScript program to find GCD/HCF of 2 numbers
 // Recursive function to find GCD/HCF of 2 numbers
 function calculateGCD(num1, num2) {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 // Driver Code
 var num1 = 34, num2 = 22;
 document.write("GCD of " + num1 + " and " + num2 + " is " + calculateGCD(num1, num2) + "<br>");
 var num3 = 10, num4 = 2;
 document.write("GCD of " + num3 + " and " + num4 + " is " + calculateGCD(num3, num4) + "<br>");
 var num5 = 88, num6 = 11;
 document.write("GCD of " + num5 + " and " + num6 + " is " + calculateGCD(num5, num6) + "<br>");
 var num7 = 40, num8 = 32;
 document.write("GCD of " + num7 + " and " + num8 + " is " + calculateGCD(num7, num8) + "<br>");
 var num9 = 75, num10 = 50;
 document.write("GCD of " + num9 + " and " + num10 + " is " + calculateGCD(num9, num10) + "<br>");

Выход:

 GCD of 34 and 22 is 2
 GCD of 10 and 2 is 2
 GCD of 88 and 11 is 11
 GCD of 40 and 32 is 8
 GCD of 75 and 50 is 25

Как найти НОК двух чисел

Наименьшее общее кратное (НОК) двух чисел – это наименьшее положительное целое число, которое полностью делится на два заданных числа. Вы можете найти НОК двух чисел, используя следующую математическую формулу:

 num1 * num2 = LCM(num1, num2) * GCD(num1, num2)
 LCM(num1, num2) = (num1 * num2) / GCD(num1, num2)

Чтобы найти НОК двух чисел программным способом, вам нужно использовать функцию, чтобы найти НОД двух чисел.

Программа на C ++ для поиска НОК двух чисел

Ниже приведена программа на C ++ для поиска НОК двух чисел:

 // C++ program to find LCM of 2 numbers
 #include <iostream>
 using namespace std;
 // Recursive function to find LCM of 2 numbers
 int calculateGCD(int num1, int num2)
 {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 int calculateLCM(int num1, int num2)
 {
 return (num1 / calculateGCD(num1, num2)) * num2;
 }
 // Driver Code
 int main()
 {
 int num1 = 34, num2 = 22;
 cout << "LCM of " << num1 << " and " << num2 << " is " << calculateLCM(num1, num2) << endl;
 int num3 = 10, num4 = 2;
 cout << "LCM of " << num3 << " and " << num4 << " is " << calculateLCM(num3, num4) << endl;
 int num5 = 88, num6 = 11;
 cout << "LCM of " << num5 << " and " << num6 << " is " << calculateLCM(num5, num6) << endl;
 int num7 = 40, num8 = 32;
 cout << "LCM of " << num7 << " and " << num8 << " is " << calculateLCM(num7, num8) << endl;
 int num9 = 75, num10 = 50;
 cout << "LCM of " << num9 << " and " << num10 << " is " << calculateLCM(num9, num10) << endl;
 return 0;
 }

Выход:

 LCM of 34 and 22 is 374
 LCM of 10 and 2 is 10
 LCM of 88 and 11 is 88
 LCM of 40 and 32 is 160
 LCM of 75 and 50 is 150

Программа Python для поиска НОК двух чисел

Ниже приведена программа Python для поиска НОК двух чисел:

 # Python program to find LCM of 2 numbers
 def calculateGCD(num1, num2):
 if num2==0:
 return num1
 else:
 return calculateGCD(num2, num1%num2)
 def calculateLCM(num1, num2):
 return (num1 // calculateGCD(num1, num2)) * num2
 # Driver Code
 num1 = 34
 num2 = 22
 print("LCM of", num1, "and", num2, "is", calculateLCM(num1, num2))
 num3 = 10
 num4 = 2
 print("LCM of", num3, "and", num4, "is", calculateLCM(num3, num4))
 num5 = 88
 num6 = 11
 print("LCM of", num5, "and", num6, "is", calculateLCM(num5, num6))
 num7 = 40
 num8 = 32
 print("LCM of", num7, "and", num8, "is", calculateLCM(num7, num8))
 num9 = 75
 num10 = 50
 print("LCM of", num9, "and", num10, "is", calculateLCM(num9, num10))

Выход:

 LCM of 34 and 22 is 374
 LCM of 10 and 2 is 10
 LCM of 88 and 11 is 88
 LCM of 40 and 32 is 160
 LCM of 75 and 50 is 150

Программа на C для поиска НОК двух чисел

Ниже приведена программа на языке C для поиска НОК двух чисел:

 // C program to find LCM of 2 numbers
 #include <stdio.h>
 // Recursive function to find LCM of 2 numbers
 int calculateGCD(int num1, int num2)
 {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 int calculateLCM(int num1, int num2)
 {
 return (num1 / calculateGCD(num1, num2)) * num2;
 }
 // Driver Code
 int main()
 {
 int num1 = 34, num2 = 22;
 printf("LCM of %d and %d is %d ⁠n" , num1 , num2, calculateLCM(num1, num2));
 int num3 = 10, num4 = 2;
 printf("LCM of %d and %d is %d ⁠n" , num3 , num4, calculateLCM(num3, num4));
 int num5 = 88, num6 = 11;
 printf("LCM of %d and %d is %d ⁠n" , num5 , num6, calculateLCM(num5, num6));
 int num7 = 40, num8 = 32;
 printf("LCM of %d and %d is %d ⁠n" , num7 , num8, calculateLCM(num7, num8));
 int num9 = 75, num10 = 50;
 printf("LCM of %d and %d is %d ⁠n" , num9 , num10 , calculateLCM(num9, num10));
 return 0;
 }

Выход:

 LCM of 34 and 22 is 374
 LCM of 10 and 2 is 10
 LCM of 88 and 11 is 88
 LCM of 40 and 32 is 160
 LCM of 75 and 50 is 150

Программа на JavaScript для поиска НОК двух чисел

Ниже приведена программа на JavaScript для поиска НОК двух чисел:

 // JavaScript program to find LCM of 2 numbers
 // Recursive function to find LCM of 2 numbers
 function calculateGCD(num1, num2) {
 if(num2==0)
 {
 return num1;
 }
 else
 {
 return calculateGCD(num2, num1%num2);
 }
 }
 function calculateLCM(num1, num2)
 {
 return (num1 / calculateGCD(num1, num2)) * num2;
 }
 // Driver Code
 var num1 = 34, num2 = 22;
 document.write("LCM of " + num1 + " and " + num2 + " is " + calculateLCM(num1, num2) + "<br>");
 var num3 = 10, num4 = 2;
 document.write("LCM of " + num3 + " and " + num4 + " is " + calculateLCM(num3, num4) + "<br>");
 var num5 = 88, num6 = 11;
 document.write("LCM of " + num5 + " and " + num6 + " is " + calculateLCM(num5, num6) + "<br>");
 var num7 = 40, num8 = 32;
 document.write("LCM of " + num7 + " and " + num8 + " is " + calculateLCM(num7, num8) + "<br>");
 var num9 = 75, num10 = 50;
 document.write("LCM of " + num9 + " and " + num10 + " is " + calculateLCM(num9, num10) + "<br>");

Выход:

 LCM of 34 and 22 is 374
 LCM of 10 and 2 is 10
 LCM of 88 and 11 is 88
 LCM of 40 and 32 is 160
 LCM of 75 and 50 is 150

Узнать больше о математических алгоритмах

Математические алгоритмы играют жизненно важную роль в программировании. Целесообразно знать о некоторых основных программах, основанных на математических алгоритмах, таких как ситовые алгоритмы, простое факторизация, делители, числа Фибоначчи, вычисления nCr и т. Д.

В настоящее время функциональное программирование находится на вершине тенденций программирования в Интернете. Парадигма функционального программирования рассматривает вычисления как математические функции, и эта концепция очень полезна в программировании. Вы должны знать о функциональном программировании и о том, какие языки программирования поддерживают его, чтобы стать наиболее эффективным программистом.

Курс по Python: https://stepik.org/course/100707

На этом занятии я
хочу показать вам пример использования функций для решения одной частной задачи
– нахождения наибольшего общего делителя (НОД) для двух натуральных чисел a и b. Причем, мы не
просто напишем алгоритм, а еще выполним его тестирование с применением
тестирующей функции. То есть, это будет полноценный пример, показывающий
принцип разработки программ с использованием функций и тестов.

Но, вначале пару
слов о самом алгоритме Евклида, о принципе его работы. Сначала рассмотрим его
медленный, но простой вариант.

Например, пусть
даны два натуральных числа: a = 18 и b = 24. Чтобы
определить для них НОД, будем действовать, следующим образом. Из большего
значения вычтем меньшее и результат сохраним в переменной с большим значением,
то есть, в b. Фактически,
это означает, что мы выполняем операцию: b = b – a. Теперь у нас
два значения a = 18, b = 6. Для них
повторяем тот же самый процесс. Здесь большее уже переменная a, поэтому,
корректируем ее значение, вычитая меньшее. Получаем новую пару a = 12, b = 6. Опять
повторяем этот процесс и видим, что a = 6, b = 6 –
переменные равны. В этом случае останавливаем алгоритм и получаем, что НОД(18,
24) = 6, что, в общем то, верно.

Весь этот
алгоритм можно представить следующим псевдокодом:

Давайте его
опишем с помощью, следующей функции:

def get_nod(a, b):
    """Вычисляется НОД для натуральных чисел a и b
        по алгоритму Евклида.
        Возвращает вычисленный НОД.
    """
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
 
    return a

Смотрите, здесь
вначале идет многострочная строка с описанием работы функции. Так рекомендуется
делать для ключевых функций программы, чтобы другие программисты могли быстро
понимать, как их применять на практике. А, далее, после описания следует сам
алгоритм Евклида.

Выполним эту
функцию со значениями аргументов 18 и 24:

res = get_nod(18, 24)
print(res)

Видим в консоли верное
значение 6. Вот пример правильного оформления ключевых функций программы. Мало
того, встроенная функция:

позволяет
выводить описание указанных функций. И мы видим в консоли наше сформированное сообщение.
Это очень удобно, особенно при групповой работе над проектом.

После того, как
функция определена, ее следует протестировать и убедиться в корректности
возвращаемых результатов. Для этого тестировщик создает свою вспомогательную
функцию. Используя наши текущие знания, мы ее опишем, следующим образом:

def test_nod(func):
    # -- тест №1 -------------------------------
    a = 28
    b = 35
    res = func(a, b)
    if res == 7:
        print("#test1 - ok")
    else:
        print("#test1 - fail")
 
    # -- тест №2 -------------------------------
    a = 100
    b = 1
    res = func(a, b)
    if res == 1:
        print("#test2 - ok")
    else:
        print("#test2 - fail")
 
    # -- тест №3 -------------------------------
    a = 2
    b = 10000000
 
    st = time.time()
    res = func(a, b)
    et = time.time()
    dt = et - st
    if res == 2 and dt < 1:
        print("#test3 - ok")
    else:
        print("#test3 - fail")

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

Далее, выполним
импорт нужного нам модуля time для вызова
функции time():

и в конце вызовем
тестирующую функцию для тестирования get_nod:

Смотрите, у нас
первые два теста прошли, а третий – не прошел, так как функция слишком долго
вычисляла результат.

Давайте поправим
ее и ускорим алгоритм Евклида. Как это можно сделать? Смотрите, если взять два
числа a = 2 и b = 100, то по
изначальному алгоритму мы будем делать многочисленные вычитания из b a, пока значения
не сравняются. То есть, мы здесь, фактически, вычисляем остаток от вхождения
двойки в сотню, а это есть не что иное, как операция:

b = b % a = 0

И никаких
циклических вычитаний! Это, очевидно, будет работать много быстрее. При этом,
как только получаем остаток равный нулю, то НОД – это значение меньшей
переменной, то есть, в нашем примере – a = 2.

То же самое для
предыдущих значений a = 18, b = 24. Получаем серию таких
вычислений:

b = 24 % 18 = 6

a = 18 % 6 = 0

Значит, НОД(18,
24) = 6. Видите, как это быстро и просто! На уровне псевдокода быстрый алгоритм
Евклида можно описать так:

пока
меньшее число больше 0

        
большему числу присваиваем остаток от деления на меньшее число

выводим большее
число

Реализуем его в
виде функции:

def get_fast_nod(a, b):
    """Вычисляется НОД для натуральных чисел a и b
        по быстрому алгоритму Евклида.
        Возвращает вычисленный НОД.
    """
    if a < b:
        a, b = b, a
 
    while b != 0:
        a, b = b, a % b
 
    return a

Предлагаю, в
качестве самостоятельного задания, вам самим в деталях разобраться, как она
работает. А мы ее сразу протестируем:

Как видите, она
проходит все три наших теста.

Надеюсь, из
этого занятия мне удалось донести до вас общий принцип разработки и
тестирования ключевых программных функций. А также объяснить работу алгоритма
Евклида. Если все это понятно, то смело переходите к следующему уроку.

Курс по Python: https://stepik.org/course/100707