Как найти нод с помощью программы

НОД – это математический термин, обозначающий наибольший общий делитель, который может идеально разделить два числа. НОД также известен как наибольший общий фактор(HCF).

Например, HCF / GCD двух чисел 54 и 24 равен 6. Поскольку 6 – это наибольший общий делитель, который полностью делит 54 и 24.

Разберемся как найти НОД двух чисел в Python. 

НОД с использованием функции gcd()

gcd() в python – это встроенная функция, предлагаемая математическим модулем для поиска наибольшего общего делителя двух чисел.

Синтаксис:

 
gcd(a, b) 

Где a и b – два целых числа, которые передаются в качестве аргумента функции gcd().

Давайте создадим программу для печати НОД двух чисел, используя встроенную функцию math.gcd() в python.

math_fun.py

 
# create a program to print the gcd of two number in python using the math.gcd() function. 
import math 
print(" GCD of two number 0 and 0 is ", math.gcd(0, 0)) #math.gcd(a, b), a and b are the two integer number 
print(" GCD of two number 0 and 48 is ", math.gcd(0, 48)) 
a = 60 # assign the number to variable a 
b = 48 # assign the number to variable b 
print(" GCD of two number 60 and 48 is ", math.gcd(a, b)) # pass the variable a and b to math.gcd() function. 
print(" GCD of two number 48 and -12 is ", math.gcd(48, -12)) # pass the integer number 
print(" GCD of two number -24 and -18 is ", math.gcd(-24, -18)) 
print(" GCD of two number -60 and 48 is ", math.gcd(-60, 48)) 

Выход:

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

НОД с использованием рекурсии

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

Псевдокод алгоритма

Шаг 1: Возьмите два входа, x и y, от пользователя.

Шаг 2: Передайте входной номер в качестве аргумента рекурсивной функции.

Шаг 3: Если второе число равно нулю(0), возвращается первое число.

Шаг 4: В противном случае он рекурсивно вызывает функцию со вторым числом в качестве аргумента, пока не получит остаток, который делит второе число на первое число.

Шаг 5: Вызовите или назначьте gcd_fun() переменной.

Шаг 6: Отобразите НОД двух чисел.

Шаг 7: Выйдите из программы.

Разберемся с программой для нахождения НОД двух чисел с помощью рекурсии.

gcdRecur.py

 
# write a program to understand the GCD of two number in python using the recursion. 
def gcd_fun(x, y): 
    if(y == 0): # it divide every number 
        return x  # return x 
    else: 
        return gcd_fun(y, x % y) 
x =int(input("Enter the first number: ")) # take first no.  
y =int(input("Enter the second number: ")) # take second no.  
num = gcd_fun(x, y) # call the gcd_fun() to find the result 
print("GCD of two number is: ") 
print(num) # call num 

Выход:

Нахождение НОД с помощью цикла

Давайте создадим программу для нахождения НОД двух чисел в Python с помощью циклов.

gcdFile.py

 
def GCD_Loop( a, b): 
    if a > b:  # define the if condition 
        temp = b 
    else: 
        temp = a 
    for i in range(1, temp + 1): 
        if(( a % i == 0) and(b % i == 0 )): 
            gcd = i 
    return gcd 
x = int(input(" Enter the first number: ") ) # take first no.  
y =int(input(" Enter the second number: ")) # take second no.  
num = GCD_Loop(x, y) # call the gcd_fun() to find the result 
print("GCD of two number is: ") 
print(num) # call num 

Выход:

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

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

Алгоритм Евклида – эффективный метод нахождения наибольшего общего делителя двух чисел. Это самый старый алгоритм, который делит большее число на меньшее и берет остаток. Опять же, он делит меньшее число от остатка, и этот алгоритм непрерывно делит число, пока остаток не станет 0.

Например, предположим, что мы хотим вычислить HCF двух чисел, 60 и 48. Затем мы делим 60 на 48; он возвращает остаток 12. Теперь мы снова делим число 24 на 12, а затем он возвращает остаток 0. Таким образом, мы получаем HCF равным 12.

Псевдокод алгоритма Евклида

Шаг 1: Есть два целых числа, например a и b.

Шаг 2: Если a = 0, то НОД(a, b) равен b.

Шаг 3: Если b = 0, НОД(a, b) равен a.

Шаг 4: Найти mod b.

Шаг 5: Предположим, что a = b и b = R.

Шаг 6: Повторяйте шаги 4 и 3, пока mod b не станет равным или большим 0.

Шаг 7: GCD = b и затем распечатайте результат.

Шаг 8: Остановите программу.

Найдем HCF или GCD двух чисел, используя алгоритм Евклида в python.

Euclid.py

 
# Create a program to find the GCD of two number in python using the Euclid's Algorithm. 
def find_hcf(a,b): 
    while(b): 
        a, a = b, a % b 
        return a 
a = int(input(" Enter the first number: ") ) # take first no.  
b = int(input(" Enter the second number: ")) # take second no.  
num = find_hcf(a, b) # call the find_hcf() to get the result 
print("  The HCF of two number a and b is ") 
print(num) # call num 

Выход:

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

Для начала разберемся, что это и как это работает. Алгоритм Евклида позволяет найти нам наибольший общий делитель чисел. Как это работает:
Пусть a = 18, b = 30.
Цикл: a!=0 and b!=0
Если a > b, то a = a % b, если меньше, то b = b % a, таким образом мы сначала находим остаток деления, а потом повторяем действия. У нас a < b, значит, ищем остаток деления b % a (30 % 18) = 12, присваиваем b = 12, повторяем цикл но теперь у нас уже a > b(b = 12)
значит выполняем a % b (18 % 12) = 6? снова переходим к циклу, теперь снова b > a, значит выполняем b % a (30 % 6), остаток от деления 0, на этом мы прекращаем наш цикл и узнаем, что наибольший общий делитель 18 и 30 = 6. и выводим a + b (b = 0, a = 6).

Python

#!/usr/bin/env python
a = 18
b = 30
 
while a!=0 and b!=0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print (a+b)

Perl:

 sub nod
 {
 return  $_[0] != 0  ?  nod ( ( $_[1] % $_[0] ), $_[0] )  :  $_[1];
 }

C:

 int gcd(int a, int b) {
   int c;
   while (b) {
      c = a % b;
      a = b;
      b = c;        
   }
   return abs(a);
 }

Pascal:

  function nod( a, b: longint): longint; 
  begin
   while (a <> 0) and (b <> 0) do
     if a >= b then 
       a:= a mod b 
     else 
       b:= b mod a;
   nod:= a + b;
  end;

Java:

public class GCD {
    public static int gcd(int a,int b) {
        while (b !=0) {
            int tmp = a%b;
            a = b;
            b = tmp;
        }
        return a;
    }
}

C#:

int gcd(int a, int b)
{
    while (b != 0)
        b = a % (a = b);
    return a;
}

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

Математические алгоритмы также являются очень важной темой для собеседований по программированию. В этой статье вы узнаете, как найти 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 и т. Д.

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

Напишите программу для вычисления наибольшего общего делителя двух целых чисел. Задачу решим двумя способами: используя оператор repeat, используя оператор while.

Примечание: наибольшим общим делителем (сокращенно пишут НОД) двух натуральных чисел m и n называется наибольший из их общих делителей. Обозначение: НОД(m, n).

Например, найдем НОД(12, 8):
Выпишем все делители числа 12: 1, 2, 3, 4, 6, 12;
Выпишем все делители числа 8: 1, 2, 4, 8;
Выпишем все общие делители чисел 12 и 8: 1, 2, 4. Из них наибольшее число – 4. Это и есть НОД чисел 12 и 8.

Решение

Воспользуемся так называемым алгоритмом Евклида нахождения НОД, который выведен с помощью математических методов. В самом простейшем случае для заданных чисел m и n он выглядит так:

1) Если m неравно n, перейти к шагу 2, в противном случае вывести m и закончить алгоритм;
2) Если m > n, заменить m на m − n, в противном случае заменить n на n − m;
3) Перейти на шаг 1

Как видим, в шаге 2 большее из двух текущих чисел заменяется разностью большего и меньшего.

Приведем пример для чисел 12 и 8:

1) Так как 12 > 8, заменим 12 на 12 − 8 = 4;
2) Так как 8 > 4, заменим 8 на 8 − 4 = 4;
3) 4 = 4, конец.

1 способ

С использованием оператора while.

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

1) Ввод m и n;
2) Запуск цикла с предусловием m < > n. В цикле:
   Если m > n, то переменной m присвоить m − n, иначе переменной n присвоить n − m;
3) Вывод m:

Код:

program nod1;
var
   x, y: integer;
   nod: integer;
begin
   writeln (‘m=’);
   readln (m);
   writeln (‘n=’);
   readln (n);
   while m<>n do
     if m>n then m:=m-n
      else n:=n-m;
     nod:=m;
     writeln(‘НОД = ‘, nod)
end.

2 способ

С использованием оператора repeat.
Код:

program nod2;
var
   x, y: integer;
   nod: integer;
begin
   writeln (‘m=’);
   readln (m);
   writeln (‘n=’);
   readln (n);
   repeat
     if m>n then m:=m-n;
     if m<n then n:=n-m
   until m=n;
   nod:=m;
   writeln(‘НОД = ‘, nod)
end.

Опубликовано: 25.03.2018
Обновлено: 12.03.2020