Как найти наибольший общий делитель программа

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

Исходный код программы:

var a,b,c: integer; //Описание переменных
begin //Начало программы
  writeln('Введите a,b: '); //Диалог с пользователем
  read(a,b);  //Чистывание чисел
  while b<>0 do //Вход в цикл while, пока b не равно 0
  begin
    c := a mod b; //Присваивание с остатка деления a/b
    a := b; 
    b := c;
  end;
  writeln('Наибольший Общий Делитель = ',a); //Вывод делителя
end.//конец программы

Скачать:

nod.pas

Дата: 2012-04-07 18:52:48   Просмотров: 46717

Теги: Паскаль исходник Pascal WHILE циклы

Задача:

Найти наименьшее общее кратное для всех элементов массива — минимальное число, которое делится на все элементы массива без остатка. Также, найти НОД всех элементов массива.

Решение:

Вот тут приведены алгоритмы расчета НОК и НОД для двух чисел. Ясно, что наиболее эффективный алгоритм расчета НОК двух чисел — это произведение чисел поделить на их НОД. По содержимому статьи ясно что НОК(а1, а2, а3, ... аN) равен НОК(НОК(НОК(А1, А2), А3)..., АN). Таким образом, для расчета НОК массива чисел надо многократно расчитывать НОД двух чисел, реализация этой функции на С++ взята тут.

Реализация на Си (функции чуть-чуть изменены, так как добавлена самописная функция swap):

#include <stdio.h>
#include <stdlib.h>

void read_array(int n, int** values) {
    for (int i = 0; i < n; ++i) {
        printf("values[%d] = ", i);
        scanf("%d", &((*values)[i]));
    }
}

void print_array(int n, int* values) {
    for (int i = 0; i < n; ++i) {
        printf("values[%d] = %dn", i, values[i]);
    }
}

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

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

int gcd_n(int n, int* values) {
    if (n == 0)
        return -1;
    if (n == 1)
        return values[0];
    int gcd_value = gcd(values[0], values[1]);
    for (int i = 2; i < n; ++i) {
        gcd_value = gcd(gcd_value, values[i]);
    }
    return gcd_value;
}

int lcm(int a, int b) {
    return (a*b)/gcd(a, b);
}

int lcm_n(int n, int* values) {
    if (n == 0)
        return -1;
    if (n == 1)
        return values[0];
    int lcm_value = lcm(values[0], values[1]);
    for (int i = 2; i < n; ++i) {
        lcm_value = lcm(lcm_value, values[i]);
    }
    return lcm_value;
}

int main() {
    int n;
    int *values;
    
    printf("n: ");
    scanf("%d", &n);
    
    values = malloc(sizeof(int) * n);
    
    read_array(n, &values);
    
    printf("lcm: %d", lcm_n(n, values));
    
    free(values);
    return 0;
}

Курс по 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

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

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

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