Алгоритм Евклида на 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);
        }