Как найти нод в си шарп

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

Евклид – древнегреческий учёный, философ, математик, живший в 3 веке до н. э.

Где применяется алгоритм Евклида ?

• Криптографический алгоритм с открытым ключом RSA.
• Является основным инструментом для доказательства теорем в современной теории чисел.

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

Например, для чисел 12 и 8 наибольший общий делитель (НОД) равен 4.

Алгоритм Евклида (метод вычитания)

Основное правило Алгоритма Евклида для метода вычитания:

Т.е. можно заменить большее число – разностью двух чисел, и НОД останется тем же.

Составим алгоритм:

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

Запрограммируем Алгоритм Евклида на языке C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp38
{
    class Program
    {
        static void Main(string[] args)
        {
            int m, n, nod;
            m = Convert.ToInt32(Console.ReadLine());
            n = Convert.ToInt32(Console.ReadLine());

            while(m != n)
            {
                if(m > n)
                {
                    m = m - n;
                }
                else
                {
                    n = n - m;
                }
            }

            nod = n;
            Console.WriteLine("НОД: " + nod);

            Console.ReadKey();
        }
    }
}

Алгоритм Евклида (метод деления)

Можно алгоритм Евклида написать и через остаток от деления!

Где символ % – это остаток от деления.

Запрограммируем метод деления Алгоритма Евклида на C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp38
{
    class Program
    {
        static void Main(string[] args)
        {
            int m, n, nod;
            m = Convert.ToInt32(Console.ReadLine());
            n = Convert.ToInt32(Console.ReadLine());

            while(m!= 0 && n!=0)
            {
                if(m > n)
                {
                    m = m % n;
                }
                else
                {
                    n = n % m;
                }
            }

            nod = m + n;
            Console.WriteLine("НОД: " + nod);

            Console.ReadKey();
        }
    }
}

На этом всё, удачи!

Сортировка слиянием (merge sort) на C#

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

Наибольший общий делитель

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

В качестве примера рассмотрим значения 320 и 120. НОД этих двух чисел – 40. Если процесс вычитания меньшего числа из большего числа повторяется, со временем одно из значений станет нулевым. В этот момент другое значение будет содержать НОД для исходной пары. Этот итерационный процесс для наших значений примера дает следующие результаты:

320 - 120 = 200
200 - 120 = 80
120 - 80 = 40
80 - 40 = 40
40 - 40 = 0

Окончательный расчет дает нулевой результат, который оставил бы два значения 40 и ноль. Следовательно, НОД – это значение 40.

Реализация алгоритма Евклида

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

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

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

Чтобы создать метод, добавьте следующий код:

        static int GetNOD (int val1, int val2)
{
    while ((val1 !=0) && (val2 != 0))
    {
        if (val1> val2)
            val1 -= val2;
        else
            val2 -= val1;
    }

    return Math.Max(val1, val2);
}

Чтобы проверить метод, попробуйте выполнить следующую команду. Это находит НОД 322328 и 122120. Результат должен быть равен 344.

int nod = GetNOD(322328, 122120); // 344

Нахождение НОД с использованием оператора модуля

Число итераций цикла в предыдущем примере кода может быть огромным. Если одно из двух значений намного больше другого, либо в начале процесса, либо позже, когда значения падают, одно и то же значение может быть вычтено много раз. Мы можем уменьшить число итераций, используя оператор модуля. Применение оператора модуля к двум значениям и замена большего значения результата приводит к одновременному применению нескольких вычитаний. Например, если два значения равны десяти и трем, три будут вычитаться три раза, чтобы уменьшить десять к одному. Используя модуль, мы получаем единицу в единственной итерации, как 10% 3 = 1.

Если результат модуля равен нулю, то найден НОД.

      public static int GetNODModul(int val1, int val2)
        {
            while ((val1!=0) && (val2!=0))
            {
                if (val1 > val2)
                    val1 %= val2;
                else
                    val2 %= val1;
            }
            return Math.Max(val1, val2);
        }

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

В окончательной версии алгоритма Евклида для получения результата используется рекурсия. Это полезно при использовании функциональных языков программирования, таких как F#. Тем не менее, я опишу его здесь, используя C# для полноты картины.

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

        public static int GetNODRecurs(int val1, int val2)
        {
            if (val2 == 0)
                return val1;
            else
                return GetNODRecurs(value2, val1 % val2);
        }

Автор этого материала – я – Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML – то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

заметки, си шарп, алгоритмы

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

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

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

Рекурсивная реализация поиска наибольшего общего делителя

Напишем два вспомогательных метода, которые возвращают минимальное и максимальное из двух чисел:

static int Min(int x, int y)
{
    return x < y ? x : y;
}

static int Max(int x, int y)
{
    return x > y ? x : y;
}

Нахождение НОД для двух чисел c использованием вычитания

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

static int GCD(int a, int b)
{
    if (a == 0)
    {
        return b;
    }
    else
    {
        var min = Min(a, b);
        var max = Max(a, b);
        //вызываем метод с новыми аргументами
        return GCD(max - min, min);
    }
}

Использование оператора остатка от деления % для вычисления НОД

Для уменьшения количества рекурсивных вызовов, при вычислении, можно воспользоваться оператором остатка от деления и вместо разницы, передавать в метод остаток от деления максимального числа на минимальное.
Чтобы ускорить алгоритм, достаточно изменить знак в строке возврата предыдущего метода с “-” на “%”:

return GCD(max % min, min);

Использование остатка очень ускоряет работу алгоритма поиска НОД. К примеру для пары чисел 1013 и 65 с использованием вычитания метод вызывается 27 раз, а с остатком от деления всего 7.

Вычисление НОД в циклах

Циклическое вычисление наибольшего общего делителя с вычитанием

static int GCD(int a, int b)
{
    if (a == 0)
    {
        return b;
    }
    else
    {
        while (b != 0)
        {
            if (a > b)
            {
                a -= b;
            }
            else
            {
                b -= a;
            }
        }

        return a;
    }
}

Циклический поиск наибольшего общего делителя с остатком от деления

static int GCD(int a, int b)
{
    while (b != 0)
    {
        var temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

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

Напишем программу, в которой будем использовать один из методов рассмотренных выше:

using System;

class Program
{
    static int GCD(int a, int b)
    {
        while (b != 0)
        {
            var t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static void Main(string[] args)
    {
        Console.WriteLine("Алгоритм Евклида");
        Console.Write("A = ");
        var a = Convert.ToInt32(Console.ReadLine());
        Console.Write("B = ");
        var b = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine("Наибольший общий делитель чисел {0} и {1} равен {2}", a, b, GCD(a, b));
        Console.ReadLine();
    }
}

Результат работы программы:

Для чисел 36 и 60 программа возвращает значение 12.

Наибольший общий делитель трех чисел

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

var n1 = GCD(GCD(15, 30), 75); //для трех параметров результат 15
var n2 = GCD(GCD(16, 36), GCD(585, 360)); //для четырех чисел результат 1

В первом примере сначала вычисляется НОД(15, 30) = 15, потом результат вычислений передается в качестве аргумента и вычисляется НОД(15, 75) = 15.
Во втором примере вычисляются НОД(16, 36) = 4 и НОД(585, 360) = 45, а результаты передаются в метод НОД(4, 45) = 1.