Задача «Наибольший общий делитель». Пример решения

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

 Постановка задачи. Дано два целых положительных числа x и y. Наибольшее число, на которое делятся оба числа без остатка, называют наибольшим общим делителем (НОД). Наверно, это вам известно из школьного курса математики. Зачем он нужен? Например, для упрощения дробей: 26/39=2/3, т.к. НОД(x,y)=13. Или для нахождения простых чисел, которые используются в алгоритмах защиты информации.

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

Реализация. Придерживаясь принципа проектирования «сверху-вниз», объявим в классе Program метод  static int НОД(int x, int y), а ввод и вывод результата выполним в Main(). Тогда:

// Нахождение наибольшего общего делителя (НОД) двух целых чисел
// Алгоритм Евклида,  300 год до н. э.  -  Функция НОД(x,y)
using System;
namespace НаибольшийОбщийДелитель
{
    class Program
    {
        static void Main(string[] args)
        {
            int x, y;
            Console.Write("x= ");
            x = Convert.ToInt32(Console.ReadLine());
            Console.Write("y= ");
            y = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("НОД = {0}",НОД(x,y));
            Console.ReadKey();
        }
        //  Функция НОД(x,y)
        static int НОД(int x, int y)
        {
            while (x != y)
            {
                if (x > y)
                    x = x - y;
                else
                    y = y - x;
            }
            return x;
        }
    }
}

Результат:

2195

Замечание. При разработке алгоритмов решения массовых (часто выполняющихся при различных исходных данных) задач имеет значение их эффективность. Под этим понимаются время выполнения и объем требуемой памяти. С этой точки зрения алгоритм Евклида является образцом для программиста.

Далее планируется дополнять этот раздел новыми примерами, в том числе предложенными вами

Вам предлагаются задачи для самостоятельного решения с использованием навыков, приобретаемых при творческом освоении основ языка C#.


NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.


Понравилась статья? Поделиться с друзьями:
0 0 голоса
Рейтинг статьи
Подписаться
Уведомить о

0 комментариев
Новые
Старые Популярные
Межтекстовые Отзывы
Посмотреть все комментарии
0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x