Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

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


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


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


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


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

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


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


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


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


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


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



StudLance.ru

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


Блок-схема алгоритма Евклида


Сначала вводятся числа 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();
        }
    }
}

На этом всё. До новых встреч!





02-12-2019 в 20:49:52





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

Задача на логику на уроке информатики. Пружина от будильника.

Сегодня рассмотрим логическую задачу от Жан-Клода Байифа (французского...

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



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



ОГЭ задание 1
Алгоритм Евклида





Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy