Главная Посты Курсы Связь О сайте

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



Сегодня разберём древний и красивый Алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел, и запрограммируем его на языке 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();
        }
    }
}

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






02-12-2019 в 20:49:52





Похожая статья:

Сортировка простым выбором C#

Привет! Сегодня рассмотрим cортировку методом простого выбора (простог...

Категория: Алгоритмы  Подкатегория: Сортировка
Дата: 15-01-2018 в 16:47:34 0